[Java] HashSet 구현

출처

ChatGPT

Java 1.8 소스코드

---

HashSetdms 자바 컬렉션 프레임워크에서 제공하는 클래스 중 하나로, 집합(Set) 자료 구조를 구현한다. HashSet은 중복 요소를 허용하지 않으며, 요소의 순서를 유지하지 않는다. 내부적으로 HashSet은 HashMap을 사용해 구현된다. 

 

1. HashSet의 개요

• HashSet은 Set 인터페이스를 구현하며, 중복되지 않은 요소를 저장한다.
• 내부적으로 HashMap을 사용해 데이터를 관리하낟.
• 요소는 해시 코드에 의해 관리되며, 빠른 검색, 추가, 제거가 가능하다.
• 삽입된 순서를 보장하지 않으며, 요소들은 무작위 순서로 저장된다.

2. HashSet의 내부 구조

• HashSet은 실제로 HashMap 객체를 사용해 데이터를 저장한다.
• HasgSet의 각 요소는 HashMap의 키로 저장되며, 해당 키의 값을 상수(PRESENT)로 설정된다.

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

 

• 관련 글 -> [Java] transient 예약어
• 관련 글 -> [Java] 왜 HashSet 내부에서 사용되는 HashMap은 transient 예약어를 써서 선언됐을까

 

3. HashSet의 주요 메소드 동작

add(E e)

요소를 HashSet에 추가한다. 내부적으로 HashMap의 put 메소드를 호출한다. 추가하려는 요소가 이미 존재하는 경우에는 기존의 키 값을 덮어쓰지 않고, 추가가 실패하며 false를 반환한다.

 

자바 1.8 HashSet 클래스 소스코드

 /**
* 지정된 요소가 아직 없는 경우 이 set에 추가합니다.
* 더 공식적으로는, 이 set에 e2가 없고 (e==null ? e2==null : e.equals(e2))인 경우
* 지정된 e를 이 set에 추가합니다.
* 이 세트에 이미 요소가 있는 경우 호출은 세트를 변경하지 않고
* false를 반환합니다.
*
* @param e 이 세트에 추가할 요소
* @return true 이 세트에 지정된 요소가 이미 없는 경우
*/

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

 

remove(Object o)

요소를 HashSet에서 제거한다. 내부적으로 HashMap의 remove 메서드를 호출해, 해당 키-값 쌍을 제거한다.

 

자바 1.8 HashSet 클래스 소스코드

/**
 * 지정된 요소가 있으면 이 세트에서 제거합니다.   
 * 더 공식적으로는 (o==null ? e==null : o.equals(e))인 요소 e를 제거합니다.
 * 이 세트에 해당 요소가 포함되어 있으면 true를 반환합니다
 * (또는 동등하게 이 세트가 호출의 결과로 변경된 경우).
 * (호출이 반환되면 이 세트는 요소를 포함하지 않습니다.)
 * 
 * 매개변수:o – 이 세트에서 제거할 객체(있는 경우)
 * 반환값:세트에 지정된 요소가 포함되어 있으면 true
 */
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

 

contains(Object 0)

특정 요소가 HashSet에 존재하는지 확인한다. 내부적으로 HashMap의 containsKey 메서드를 호출해, 키의 존재 여부를 확인한다.

 

자바 1.8 HashSet 클래스 소스코드

/**
 * 이 세트에 지정된 요소가 포함되어 있으면 true를 반환합니다. 
 * 더 공식적으로 말하면, 이 세트에 (o==null ? e==null : o.equals(e))인 
 * 요소 e가 포함되어 있는 경우에만 true를 반환합니다.
 * 
 * 매개변수: o – 이 세트에 존재하는지 테스트할 요소
 * 반환값: 이 세트에 지정된 요소가 포함되어 있으면 true
 */
public boolean contains(Object o) {
    return map.containsKey(o);
}

 

size()

HashSet에 저장된 요소의 개수를 반환한다. 내부적으로 HashMap의 size 메소드를 호출한다.

 

자바 1.8 HashSet 클래스 소스코드

/**
 * 이 세트의 요소 수(카디널리티)를 반환합니다
 *
 * 반환: 이 세트의 요소 수(카디널리티)
 */
public int size() {
    return map.size();
}

 

4. 해시 함수와 해시 버킷

• HashSet은 요소를 저장할 때 각 요소의 hashCode() 메소드를 호출해 해시 코드를 계산한다.
• 이 해시 코드는 HashMap에서 사용되는 해시 함수에 의해 특정 버킷(bucket)에 매핑된다.
• 동일한 해시 코드를 가진 요소들이 동일한 버킷에 저장될 수 있다. 이 경우 HashSet은 equals() 메서드를 사용해 요소가 동일한지 여부를 확인한다.

• 관련 글 -> [Java] 버킷 Butcket

 

5. 충돌 해결

• 만약 두 개의 서로 다른 객체가 동일한 해시 코드를 갖는 경우, 해시 충돌이 발생한다. 이 경우, HashMap은 내부적으로 해당 버킷에 있는 요소들을 링크드 리스트나 트리 구조로 관리해 충돌을 해결한다.
• 자바 8이후에는 버킷의 요소가 일정 수 이상이 되면 링크드 리스트에서 트리로 변환되어 성능을 개선한다.

 

6. 성능

• HashSet의 주요 연산(add, remove, contains)은 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 해시 함수를 이용해 직접적인 접근이 가능하기 때문이다.
• 하지만 해시 충돌이 많아지거나 해시 함수가 제대로 분포되지 않으면 성능이 저하될 수 있다.

 

7. 장단점

장점

중복 요소를 허용하지 않고, 빠른 검색, 추가, 제거 연산을 제공한다.

단점

요소들의 순서를 유지하지 않으며, 메모리 사용량이 TreeSet보다 더 많을 수 있다.

 

---

8. 출처

• 자바 표준 라이브러리의 HashSet 구현은 자바 언어 자체의 공식적인 코드이며, 이를 분석한 내용입니다. 해당 구현은 자바의 다양한 버전에서 조금씩 차이가 있을 수 있지만, 기본적인 동작 원리는 동일합니다.