자료구조 - 해시테이블
1. 해시테이블(Hash Table)이란?
해시테이블(Hash Table)은 키(Key)-값(Value)의 쌍으로 데이터를 저장하는 자료구조다.
O(1)의 조회가 특징적인데, 이는 해시 함수(Hash Function)를 사용해 키를 배열의 인덱스로 변환해 저장하기 때문이다(이 인덱스를 이용해 해시테이블 내에서 해당 키-값 쌍이 저장될 위치를 결정하는 것)
키는 중복될 수 없으며, 데이터의 순서를 보장하지 않는다.
(파이썬에서는 딕셔너리가 이 해시테이블를 활용한 데이터 구조인데, 파이썬 3.7 이상부터는 딕셔너리가 데이터의 순서를 보장한다고 한다.)
2. 해시테이블 관련 개념
2.1 해시 함수(Hash Function)
해시테이블을 사용하기 위한 핵심 기능이라 볼 수 있다. 동일한 입력에 대해 항상 동일한 해시값을 반환한다. 매우 빠르게 연산하되, 해시 충돌의 가능성을 최소화하고 해시값을 해시테이블의 주소 공간에 균등하게 분포시키는 것이 중요하다.
2.2 해시 충돌(Hash Collision)
해시 충돌이란, 두 개 이상의 키가 동일한 해시 코드를 가지는 경우를 말한다.
해시테이블은 각 키를, 해시 함수를 통해 해시 값으로 변환하고 이 해시 값으로 데이터를 저장하거나 검색한다. 해시 함수가 서로 다른 키에 대해 동일한 해시 값을 반환하면 서로 다른 데이터를 동일한 위치에 저장하려 하게 되는데, 이를 충돌이라 표현하는 것.
해시 충돌을 최소화하는 방법 아래와 같은 것들이 있다.
‘좋은’ 해시 함수 사용
해시 함수는 해시테이블의 주소 공간에 키들을 가능한 한 균등하게 분포시켜야 한다. ‘좋은’ 해시 함수는 키의 작은 변화에도 해시 값에 큰 변화를 일으켜야 하며(높은 난수성), 모든 해시 값이 동일한 확률로 발생해야 한다.
해시테이블 크기 조정
해시테이블의 크기가 충분히 크면 아무래도 충돌 확률이 낮아진다. 그 외에 해시테이블의 크기가 소수(prime number)일 경우 충돌 확률을 줄일 수 있다고 하는데, 소수는 가장 작은 약수가 자기 자신과 1밖에 없기 때문에 해시 함수가 생성하는 해시 코드를 소수로 나눈 나머지 값이 0부터 소수-1 사이에 더 균등하게 분포될 가능성이 높기 때문이라고 한다.
충돌 해결 기법 사용
- 체이닝(Chaining): 각 해시 버킷(해시테이블 내에서 실제 데이터가 저장 되는 위치 값)에 연결 리스트나 다른 형태의 동적 데이터 구조를 사용하여, 동일한 버킷에 매핑되는 여러 키들을 저장한다. 충돌이 발생하면 해당 버킷의 리스트에 새로운 항목을 추가한다.
- 오픈 어드레싱(Open Addressing): 충돌이 발생했을 때, 다른 버킷에 키를 저장하는 방법. 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 방법이 있다.
2.3 로드 팩터(Load Factor)
해시테이블의 성능과 관련한 중요한 지표 중 하나로, 해시테이블 내의 총 항목 수와 해시테이블에 할당된 총 버킷 수의 비율을 나타낸다.
해시테이블에 현재 저장된 항목의 수/해시테이블의 총 버킷 수
로드 팩터의 중요성
로드 팩터는 해시테이블의 성능에 직접적인 영향을 미친다. 로드 팩터가 낮으면 해시 충돌의 확률이 감소하지만 메모리 사용이 비효율적일 수 있다. 반대로 로드 팩터가 높으면 메모리 사용은 효율적이지만 해시 충돌의 확률이 증가하여 성능 저하를 초래할 수 있다.
재해싱
일반적으로 해시테이블은 로드 팩터가 특정 임계값을 초과하면 크기를 조정하는데, 이를 재해싱이라 한다. 이 과정에서 모든 항목이 새로운 크기의 해시테이블로 재배치되기 때문에 조정 과정에서 비용이 발생하게 된다.
최적의 로드 팩터
최적의 로드 팩터는 해시테이블의 구현 방식과 사용 사례에 따라 달라질 수 있지만, 일반적으로 로드 팩터는 0.5에서 0.75 사이에서 균형을 이루는 것이 좋다고 한다.
3. 해시테이블의 연산
3.1 조회:
평균적인 경우: O(1)
키의 해시 값을 계산하고, 이를 인덱스로 사용하여 직접 값을 조회할 수 있다.
최악의 경우: O(n)
모든 키가 동일한 인덱스로 해시될 경우, 해시 충돌이 발생하고, 모든 항목을 순회해야 할 수도 있다. 이는 매우 드문 케이스라고 볼 수 있다.
3.2 삽입
평균적인 경우: O(1)
키의 해시 값을 계산하고, 이를 인덱스로 사용하여 값을 삽입한다.
최악의 경우: O(n)
해시 충돌로 인해 동일한 버킷에 여러 키가 삽입되는 경우, 또는 해시테이블의 크기를 동적으로 조정(리해싱)해야 하는 경우에 발생할 수 있다.
3.3 수정
평균적인 경우: O(1)
해당 키에 대한 해시 값을 계산하고, 이를 인덱스로 사용하여 기존 값을 새 값으로 업데이트한다.
최악의 경우: O(n)
해시 충돌로 인해 여러 키가 동일한 버킷에 존재하는 경우에 발생할 수 있다.
3.4 삭제
평균적인 경우: O(1)
키의 해시 값을 계산하여 해당 키와 연관된 값을 삭제한다.
최악의 경우: O(n)
해시 충돌로 인해 동일한 버킷 내에서 해당 키를 찾기 위해 여러 항목을 순회해야 하는 경우에 발생할 수 있다.
4. 주의점 - 추가적인 메모리 공간 사용
매우 큰 데이터 세트를 다룰 때는 주의해야할 필요성이 있다. 주로 추가적인 메모리가 사용되는 부분은 아래와 같다.
해시 버킷 배열과 해시 충돌 처리 매커니즘
이 배열은 해시테이블 내에 저장된 키-값 쌍을 담고 있으며, 각 배열의 요소는 보통 연결 리스트나 트리 구조로 구현된다. 따라서, 배열 자체와 배열의 각 요소에 대한 메모리가 필요하다.
해시 충돌을 처리하기 위해서도 추가적인 자료구조가 필요할 수 있다.
동적 크기 조정
해시테이블의 로드 팩터가 특정 임계값을 초과하면, 해시테이블의 크기를 동적으로 조정할 수 있다. 이 과정에서는 기존 버킷 배열의 크기를 늘리고, 모든 키-값 쌍을 새 배열에 재해싱하여 삽입해야한다.
4. 파이썬의 딕셔너리
딕셔너리 내에서 각 키는 고유해야하며, 키로 사용되는 객체는 변경 불가능해야한다.
Python 3.7부터는 삽입 순서가 유지되지만, 딕셔너리를 순서가 중요한 용도로 사용하는 것은 권장되지 않는다.