[알고리즘] HashSet

특징: 내부적으로는 HashMap을 사용한다. add하는 값을 key로 사용한다.

중요: HashMap은 hashCode() method를 이용해서 key에 대한 해시코드를 구한다. 해시테이블은 이 코드를 해싱 함수를 이용해 버킷에 맵핑한다. Object 객체에서 구현되어 있는 hashCode()는 참조값을 사용한다.

 

Constructor

- HashSet(int initialCapacity): 초기 수용량을 줄 수 있다. 너무 크게 하면 iteration 시간이 비효율적이게 된다.

 

add(E e): O(1)

clear(): O(n)

contains(Object o): O(1)

isEmpty(): O(1)

iterator(): O(1)

remove(Object o): O(1)

size(): O(1)

spliterator(): O(1)

 

주의할 점: HashSet을 iteration할 때는 HashSet 객체의 사이즈(원소 개수)와 해시맵 객체의 수용량(버킷의 수)의 합에 비례하여 시간이 증가한다. 그러니까 모든 버킷을 다 돌기 때문에 비어 있는 버킷도 돌게 되어 비효율적이라는 것이다.