HashSet은 내부적으로 HashMap을 사용하며 중복을 허용하지 않는 자료구조이다.
중요한 특징으로는 아래와 같다.
- 데이터를 중복없이 저장하며 null을 허용한다.
- 내부적으로 HashMap을 사용한다.
- 순서를 보장하지 않는다.
- 스레드 세이프하지 않다.
데이터 추가
add() 메서드를 통해 데이터를 추가한다.
public void test() {
Set<String> hashset = new HashSet<>();
hashset.add("Added");
}위에서 말했듯이 중복을 허용하지 않으므로 set에 값이 존재하지 않을 때에만 해당 값 추가가 가능하다.
데이터를 추가하는 과정은 아래와 같다.
1. 먼저 추가하려는 객체의 hashcode() 메서드를 호출하여 해시코드를 얻어낸다.
2. 그 해시코드에 해당하는 버킷의 슬롯에 값을 저장한다.
3. 만약 해당 위치에 값이 저장되어 있다면(즉 같은 해시코드값을 갖는다면) equals() 메서드로 두 객체를 비교하여 true일 경우에는 값을 저장하지 않는다.
HashSet에 데이터를 추가하는데 있어서 가장 중요한 것은 hashcode()와 equals()이다. Object 클래스의 메서드인 이 두 메서드를 적절히 overriding하여 사용해야만 애플리케이션이 우리의 예상대로 작동할 것이다.
간략한 HashMap 및 용어 설명
HashSet은 내부적으로 HashMap을 사용한다 했다. HashMap의 작동방식을 간략히 설명하자면 아래와 같다.
- HashMap은 16개의 기본 용량(capacity*)을 가진 버킷의 배열로 각 버킷은 각자 다른 해시코드값에 상응한다.
- 만약 여러 객체가 같은 해시코드값을 갖는다면 하나의 버킷에 저장되게 된다.
- 만약 로드팩터* 임계치에 도달하게 되면 기존 배열의 약 2배 사이즈의 배열이 새로 생성되고 모든 요소가 rehash*되어 새로운 버킷에 재분배된다.
- 값을 갖고 오기 위해서 키를 해시하여 해당 해시코드에 해당하는 버킷으로 찾아간다. 만약 해당 버킷에 하나 이상의 객체가 저장되어 있다면 그 객체들은 링크드리스트 형태로 저장되어 있기에 해당 링크드리스트를 순회하며 값을 찾는다.
용어설명
- capacity
HashMap 안에 있는 버킷의 수이다. HashMap의 디폴트 초기 용량은 16이다. - loadfactor
Map의 용량이 일정 수준으로 차면 용량을 늘린다고 했다. '용량이 어느정도 찼다'의 기준이 되는게 loadfactor이다. (데이터의 개수)/(저장공간) 으로 계산한다. 디폴트 loadfactor는 75%이다. - Rehashing
이미 저장되어있는 데이터들에 대해 해시코드를 재계산하는 작업을 말한다. 즉 Map의 저장 공간이 임계치에 다다르면(loadfactor에 다다르면), Map은 Rehash되고 버킷의 수는 약 2배 정도 늘어나게 된다.
HashSet은 어떻게 중복을 회피할까
위에서 잠깐 설명했듯이, HashSet에 객체를 넣으면 해당 객체의 hashcode 값을 사용하여 버킷을 찾고 해당 위치에 요소가 있는지 확인한다. 만약 특정 요소가 있고 우리가 넣고자 하는 객체과 같은 객체라 판단되면 저장하지 않고 끝난다.
하지만 특정 요소가 이미 있다고 무조건 우리의 객체를 저장하지 않는 것일까? 아니다. 서로 다른 객체라도 같은 hashcode 값을 가질 수 있다. 그러므로 hashcode로 찾아간 버킷에 이미 값이 있다면 equals() 메서드를 통해 비교하는 작업을 거친다. 만약 equals()가 false라면 링크드리스트의 형태로 해당 버킷에 값을 추가한다.
HashSet의 성능
HashSet의 성능은 초기 용량과 loadfactor가 좌지우지한다.
HashSet에 값을 추가하는 것의 시간복잡도는 보통 O(1)이나 최악의 경우(버킷이 하나밖에 존재하지 않을 때) O(n)까지도 늘어난다. 그러므로 적정한 HashSet 용량을 유지하는 것이 중요하다. 그리고 이를 위해선 hashcode()를 적절히 구현하는 것이 필요하다.
JDK 8 이후부터는 최악의 경우 시간복잡도는 O(log n)이다. 간략히 설명하자면, 같은 hashcode 값을 가진 객체를 하나의 버킷에 저장할 때 일정 수 까지는 링크드리스트를 이용하나 그 후에는 트리 형태로 저장하게 된다.
여튼 이러한 이유로 HashSet은 용량, 그리고 용량과 loadfactor를 미리 설정할 수 있게끔 생성자를 제공한다.
용량을 낮게 설정한다면 공간 복잡도를 낮출 수 있다. 그러므로 iteration을 하여 값을 가져올 때 유리하다. 하지만 그만큼 rehashing이 많이 일어나는 구조이고, 이 rehashing은 비용이 비싸므로 저장할 데이터가 많지 않을거라 예상될 때에만 용량을 낮게 설정하길 권장한다.
반면 용량을 높게 설정한다면 iteration에 시간이 많이 걸리고 초기 메모리 낭비도 심할 것이다. iteration이 상대적으로 적고 데이터양이 많은 경우에 용량을 높게 설정하길 권장한다.
참조
https://www.baeldung.com/java-hashset
https://www.baeldung.com/java-hashmap-load-factor
