[Other] Hash Table

Byron·2021년 9월 9일

Other

목록 보기

12/13

Hashing

임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업.

Hash Table이란

해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블(Hash Table)이라고 함.

이미지 출처: https://medium.com/codex/hash-tables-hashing-and-collision-handling-8e4629506572
위 예시와 같이 해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키-밸류의 데이터를 저장하는 방식이다.

키(key) : 해시의 input이 되는 고유한 값
해시 함수(Hash Function) : 키를 해시로 바꿔줌. 해시 충돌의 확률을 최대한 줄이는 함수를 만드는 것이 중요.
값(value) : 저장소에 최종적으로 저장되는 값. 키와 매칭되어 저장, 삭제, 검색, 접근할 수 있어야 함

Hash Table의 메소드는 저장, 삭제, 검색으로, 평균적으로 O(1)의 시간복잡도를 갖는다.

Hash Collision(해시 충돌)

만약 'Pakumando' 와 'Sentry'를 해시 함수에 넣고 돌려 나온 값이 동일할 수 있다. 이를 해시 충돌이라고 하며, 이를 해결하는 방법은 여러 가지가 있다.

해시 테이블의 구조 개선-Chaning

이미지 출처: https://baeharam.netlify.app/posts/data%20structure/hash-table

체이닝은 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 연결된 리스트 형태로 저장하는 방법이다.
체이닝을 통해 해시테이블을 구현했을 때의 시간복잡도는, 저장의 경우 연결리스트에 추가하기만 하면 되기 때문에 상수 시간인 O(1)이지만 삭제 및 검색의 경우 최악일 시 키 값의 갯수인 O(n)이 걸릴 수도 있다.

Open Addressing

이미지 출처: https://baeharam.netlify.app/posts/data%20structure/hash-table

해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법이다.
위의 동일한 충돌에 대해 그 다음으로 비어있는 주소인 153을 이용하는 것을 볼 수 있다.
이 기법에서는 다음과 같이 동작한다.

저장: 계산한 해시 값에 대한 인덱스가 이미 차있는 경우 다음 인덱스로 이동하면서 비어있는 곳에 저장하며, 
     비어있는 자리를 탐색하는 것을 탐사(Probing)라고 한다.
검색: 계산한 해시 값에 대한 인덱스부터 검사하며 탐사를 해나가는데 이 때 '삭제' 표시가 있는 부분은 지나간다.
삭제: 검색을 통해 해당 값을 찾고 삭제한 뒤 “삭제” 표시를 한다.

또한, Open Addressing에는 선형탐사, 제곱탐사, 이중해싱 등의 충돌 처리기법이 사용된다.