[자료구조] 해시셋(HashSet)
1. 해시란?
Set 자료구조의 특성을 살펴보기 전에 Hash의 개념을 먼저 정리해보겠습니다.
해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 매핑하기 전 입력 데이터의 값을 키(Key), 매핑 후 출력 데이터의 값을 해시코드(HashCode), 매핑하는 과정 자체를 해싱(Hashing)이라 부릅니다.
해시의 특징은 다음과 같습니다.
- 동일한 입력 값에 대해서는 항상 동일한 출력 값이 보장된다.
- 출력 데이터 값을 가지고 원본 입력 데이터의 값을 알아낼 수 없다.
- 일반적으로 해시 함수는 그리 복잡하지 않은 알고리즘으로 구현되기 때문에 CPU, 메모리 자원을 크게 소비하지 않는다.
- 입력 값의 범위보다 출력 값의 범위가 좁기 때문에 다른 입력 데이터에 대해 드물게 동일한 출력 값이 나올 수 있다. (충돌)
해시를 활용한 자료구조의 검색이 빠른 이유는 해싱을 통해 만든 해시코드를 내부적으로 배열의 인덱스로 활용하기 때문입니다. 별도의 정렬을 거치지 않고도 찾고자 하는 데이터의 인덱스를 해싱을 통해 바로 추출해낼 수 있다는게 포인트입니다. 반대로, 해시코드를 인덱스로 활용하여 자료가 분산되기 때문에 어떠한 기준으로 정렬하고자 할 때는 적합하지 않습니다.
해시 자료구조의 저장/조회시 버킷을 계산하는 방법
int index = (X.GetHashCode() & 0x7fffffff) % bucket._size;
// 또는
int index = Math.abs(X.GetHashCode() % bucket._size);GetHashCode()의 결과 값이 음수가 나올 수 있기 때문에 0x7fffffff 로 & 연산을 해주었습니다.
2. 충돌방지와 회피
해시 함수에서 입력값의 범위에 비해 출력값의 범위가 좁기 때문에 각기 다른 입력 데이터에 대해 동일한 출력값이 나오는, 이른바 '충돌'이 발생할 수 있습니다. 해시를 활용한 자료구조는 해싱을 거쳐 나온 해시코드를 배열의 인덱스로 활용한다고 했는데, 충돌이 발생하면 값을 저장해야할 인덱스 위치가 겹치는 문제가 발생하게 됩니다. 따라서, 이를 해결하기 위해 일반적으로 해당 버킷에 데이터가 이미 있다면, 체인처럼 노드를 추가하여 다음 노드를 가리키는 방식(연결리스트)으로 구현합니다.
쉽게 말해, 각각의 버킷에 여러 데이터가 저장될 수 있으니, 하나의 버킷 자체도 배열로 구성하는 것이죠.
3. 해시셋 (HashSet)
데이터의 중복을 허용하지 않는 자료구조로, 중복된 데이터를 제거하거나 이미 데이터가 추가되어 있는지를 검사할 때 주로 사용됩니다. 위 그림에서 보듯이, 저장되는 데이터가 해싱되어 나온 해시코드를 인덱스로 활용해 배열(버킷)에 할당하므로, 저장된 데이터의 순서를 파악하는건 불가능합니다.
Java/C#의 HashSet 작동 과정
- 저장하는 요소의 GetHashCode() 메서드가 반환하는 해시코드와 배열(버킷)의 크기를 나눈 나머지 값을 배열의 인덱스로 활용한다.
- 저장하는 요소의 Equals() 메서드를 이용해 중복 여부를 검사한다.
따라서, 직접 작성한 클래스의 HashSet 동작 방식을 커스터마이징해주고 싶다면, GetHashCode()와 Equals() 메서드를 재정의하거나, 형식 같음 비교자인 IEqualityComparer<T> 인터페이스의 구현체를 사용해야 합니다.
4. 해시 버킷(Bucket)의 동적 확장 (Resize)
배열(버킷)의 길이를 적게하면 메모리를 아낄 수 있는 반면, 해시코드 충돌로 인한 성능상 손실이 발생할 가능성이 커집니다. 이러한 이유로, 저장된 데이터의 갯수가 일정 갯수 이상이되면 버킷의 길이를 2배로 늘리는데요, 일반적으로 저장된 데이터의 갯수가 버킷의 길이의 1.25배가 되었을 때 확장합니다.
버킷의 동적 확장에서 가장 중요한 이슈는 버킷이 확장되었을 때 기존의 모든 데이터에 대해 해싱을 새로 해서 나온 위치값(해시코드 % 버킷길이)에 할당해줘야한다는 것입니다. 모든 데이터에 대해 해싱을 새로 해야하는 이유는 애초 인덱스를 구하는 과정이 (해시코드 % 버킷의 길이)였는데 이때 사용된 버킷의 길이가 바뀌었기 때문에 각각의 데이터가 저장되어야하는 인덱스 값 자체가 변하기 때문입니다.
5. Cache를 이용한 성능 향상
해시셋과 해시테이블은 다르지만, 해시테이블에 대한 성능 향상에 대해 정리해보겠습니다. 해시테이블에 대한 성능 향상 방법은 여러 가지가 있지만, 그 중 가장 간단한 방법은 get(key), put(key) 메서드에 캐시 로직을 추가하는 것입니다. 자주 hit하는 데이터에 대해 바로 데이터를 찾게 함으로써 간단히 성능을 향상시킬 수 있습니다.
6. 참고자료
'Data Structure' 카테고리의 다른 글
| [자료구조] 동적 배열(ArrayList) (0) | 2020.12.26 |
|---|