자료구조 - [ 해시 테이블 ]

해시 테이블

해시 테이블은 키와 값의 구조를 가진 데이터를 저장하며, 해시 함수를 이용하여 키 값을 해시값으로 변환 후, 해시값을 해시 테이블의 인덱스로 사용하는 자료구조이다. 평균적으로 시간 복잡도 O(1)의 탐색 성능을 가지고 있기 때문에 빠른 탐색이 필요할 때 사용한다.

 

해시 함수를 이용하므로 해시값의 충돌이 발생할 수 있다. 좋은 해시 함수는 충돌 가능성을 낮추므로 최대한 고른 값을 가진 함수를 만들어야 한다.

 

 

• 버킷 : 해시값을 인덱스로 접근할 수 있는 배열. key-value 쌍의 참조값을 가지고 있으며, 배열 접근의 시간 복잡도는 O(1)이다.
• 엔트리 : 해시 테이블은 키와 값을 저장하는 구조이므로 노드를 이용하여 키와 값을 저장할 수 있다.
• 해시 함수 : 해시 함수와 보조 해시 함수를 이용하여 해시값을 구할 수 있으며 좋은 해시 함수는 충돌 가능성을 줄여준다.

 

---

충돌에 대응하기 위한 방법

충돌 발생 시 대응하기 위한 방법으로 크게 체이닝(channing)과 직접 주소 개방(opoen-addressing)이 있다.

 

 

1. 체이닝

키와 데이터를 삽입 시 동일한 해시값의 키가 존재하는 경우 노드를 연결하는 방식으로 저장한다. 즉 엔트리에 key-value와 연결된 노드(동일한 해시값의 key-value)의 ref를 저장하는 방식이다.

노드 간의 연결이 많을 경우 탐색 시간이 늘어날 수 있다. 따라서 이 문제를 완화하기 위한 방법으로 적재율에 따라 버킷의 크기를 늘리거나 노드 간의 연결을 선형적 방식이 아닌 비선형적 구조로 변경할 수 있다.

 

---

2. 직접 주소 개방(open-addressing)

직접 주소 개방은 버킷에 키가 1:1로 저장되는 방식으로 체이닝과 달리 해시 테이블 외부에 연결된 노드가 존재하지 않으며, 이미 동일한 해시값으로 해시 테이블에 키가 저장되어 있는 경우 보조 해시 함수의 규칙에 의해 빈 공간을 조사(probing)하여 키를 저장한다. 만약 빈 공간이 존재하지 않으면 해시 테이블의 적재율을 체크하여 버킷의 크기를 늘릴 수 있다.

 

 

2-1. Linear probing

선형적인 특성을 가지고 있는 해시 함수를 이용하여 조사한느 방식을 Linear probing이라고 한다. 키를 찾거나 삽입할 위치를 찾거나 삭제할 키를 찾을 때 순차적으로 접근하는 방식을 택한다.

 

보조 해시 함수 h'(key)는 키를 0부터 m-1까지 범위의 해시값으로 변경하며, 해시 함수 h(key, i)를 이용하여 해시값을 구한다. 최초 조사시 T(h'(key)]에서 탐색 후, i를 1씩 증가시키며 조사하기 때문에 선형적인 방법으로 불린다. 또한 특정 영역에 키가 몰리는 군집 문제로 인해 탐색 성능이 떨어질 수 있다.

 

 

 

2-2. Quadratic probing

c1과 c2를 이용한 양의 보조 상수를 추가하여 비선형적으로 조사하는 방법이다.

최초 조사 시 T[h'(key)[에서 탐색 후 i를 1씩 증가시키되 c1과 c2값에 의해 두 번째 탐색 위치가 달라진다. 그러므로 적절한 c1과 c2의 값을 정해야 한다. 

Linear probing 방식보다 좀 더 가벼운 군집 문제를 겪는다.

 

 

2-3. Double hashibng

군집 문제를 완화하기 위해 두 개의 보조 해시 함수를 이용하여 최대한 균등하게 분포하는 방법이다.

최초 조사 시 T[h'(key)]에서 탐색 후 i를 1씩 증가시키되 h2(key) 보조 해시 함수에 의해 두 번째 탐색 위치가 달라진다.

Quadratic probing 방식보다 좀 더 가벼운 군집 문제를 겪는다.

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼