HashSet은 내부가 어떻게 구현이 되어 있는가?

개요

 

---

 HashSet의 내부 구조를 알아보겠습니다. HashSet은 구현 시, HashMap을 이용합니다.

 

 

HashSet 특징

---

 HashSet 클래스는 Set 인터페이스를 구현하고, 내부적으로 hash table을 사용합니다(실제로는 HashMap입니다.) set의 저장 순서가 보장되지 않습니다. null 요소를 허용합니다

 해쉬 함수가 버킷에 요소를 적절하게 분배한다면, add, remove, contains, size 등에 시간 성능이 좋습니다. HashSet 순회는 요소의 개수와 버킷의 용량을 합친 만큼 시간이 듭니다. 따라서, 순회 성능이 중요하다면, 초기에 너무 높은 용랑을 설정하지 않도록 합니다.

 HashSet은 동기화가 되지 않습니다. 멀티 쓰레드 환경에서 동시에 접근하고, 최소한 1개의 쓰레드가 set을 변경시킨다면, 외부적으로 동기화를 해야 합니다. set에 의존하는 객체를 동기화하면 됩니다. 혹은, set을 Collections.syncrhonizedSet() 메서드로 "랩핑"할 수도 있습니다. set 생성 시에 동기화를 하면 비동기 접근을 예방할 수 있습니다.

 

 

HashSet의 코드 구현

---

HashSet은 Set을 구현합니다.

 

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

 

• 변수, 생성자

 HashSet은 HashMap에 의존합니다. Object PRESENT 변수는 주석에 따르면 Map에서 객체를 다루기 위한 임의의 값입니다.

 

 HashSet 인스턴스가 생성되면 내부적으로 HashMap 인스턴스를 생성합니다. 매개변수에 컬렉션을 넣는 경우에 해당 컬렉션 사이즈의 75% 크기 만큼 할당합니다.

 

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 HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

 

• add

 add()는 map의 put()을 사용합니다. 빈 객체를 가지는 PRESENT 변수를 value에 넣습니다. Set은 단순히 요소(value)만 가지고 있으므로, key와 value를 사용하는 map은 독립적으로 value를 저장하기 위해서 key를 구분자로 활용합니다.

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

 

• iterator

 hashSet은 hashMap처럼 get(Key key)나 List의 get(int index)를 제공하지 않습니다. HashSet의 요소를 조회하는 방법은 iterator를 사용하는 것입니다. hashSet에 있는 요소들은 map에서 key로 식별합니다. 따라서, map의 keySet()을 활용해 iterator를 합니다.

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

 

• size

public int size() {
    return map.size();
}

 

• isEmpty

public boolean isEmpty() {
     return map.isEmpty();
}

 

• contains

public boolean contains(Object o) {
    return map.containsKey(o);
}

 

• clear

public void clear() {
    map.clear();
}

 

이상으로 hashSet에서 지원하는 메서드가 모두 hashMap을 기반으로 하고 있다는 사실을 확인했습니다.

 

 

참고

 

https://www.java67.com/2014/01/how-hashset-is-implemented-or-works-internally-java.html

https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html