Java HashSet

BOJ 10815 - 숫자카드

Set을 사용하여 푸는 간단한 문제.
자바 컬렉션 프레임워크에서 Set은 인터페이스로 제공되고, 구현체로는
HashSet, LinkedHashSet, TreeSet 등이 있다.

HashSet

HashSet 구현체 코드를 뜯어보았다.

• 내부적으로 해시 테이블을 사용하여 저장한다 (실제로는 HashMap 인스턴스 소유)

• 삽입 순서를 보장하지 않는다.

• null 값을 허용한다.

• 해시 함수는 해시 값 버킷 전반에 원소를 고루 분포시킨다고 가정한다.
  이에 iterating은 HashSet의 size(원소 개수) + 내부 HashMap 인스턴스의 용량(버킷의 수)에 비례한다.
  따라서 iterator 성능이 중요할 경우 초기 capacity를 너무 높게 잡지 않아야 하며, load factor를 너무 낮게 잡아서도 안된다.

• Not Thread-safety

load factor란, 해시 테이블이 어느 정도 수준으로 찼을 경우 capacity를 늘릴 것인지 결정하는 값이다. 디폴트 값은 0.75이다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;

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

    /**
     * Constructs a new, empty set; the backing {@code HashMap} instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
	...

기본 생성자를 통해, 내부에 HashMap 인스턴스를 생성하는 것을 알 수 있다.
또한 add() 메서드 사용 시 dummy 값인 PRESENT Object 객체가 삽입된다.

HashMap의 디폴트 initial capacity는 16이다. 이전에 다루었던 ArrayDeque도 마찬가지로 초기 용량은 16이었다. 16이라는 수로 정한 이유가 무엇일까? 추후에 더 조사해봐야겠다.