Hash Table

개요

Hash Table은 Hash 함수를 사용해 key - value를 저장하는 자료구조이다.

 

Hash 함수는 임의의 길이의 값을 고정된 크기의 값으로 변환해주는 함수이다.

위의 그림은 사람의 이름(key)를 hash 함수를 통해 두자리 숫자(index)로 변환한 뒤, 해당하는 bucket에 전화번호(value)를 넣어주는 예시이다.

 

일반적으로 hash Table은 탐색, 삽입, 삭제에 O(1)의 시간복잡도를 가진다.

key에 해당하는 value를 해시 함수로 구한 index로 바로 찾을 수 있기 때문이다.

하지만 적재율이 1 초과(키의 개수가 Hash table의 크기보다 클 경우)될 경우에는 반드시 충돌이 발생하게 된다.

충돌이 발생하면, 최악의 경우 O(n)의 시간복잡도를 가진다.

 

따라서 hash Table은 해시 함수를 통해 최대한 골고루 key - value를 연결해줄 필요가 있고, 또한 충돌 시 처리 방법을 개선해주는 것이 중요하다.

 

1. 좋은 해쉬함수 만들기 (key - value 골고루 연결하기)

일반적으로 가장 많이 쓰이는 해쉬함수 구현 방법은 나눗셈 방법이다.

해쉬 테이블의 크기를 N이라고 하면 값을 N으로 나눠 index를 구해준다.

하지만 특정 index로 key들이 쏠릴 수 있다.

예를 들어 해시 테이블의 크기가 10이고, 1, 11, 31 등을 나눗셈 법으로 key를 배정해준다고 하면

1 % 10, 11 % 10, 31 % 10의 값이 모두 1이기때문에 공간을 효율적으로 활용하지 못하게 된다.

따라서 좋은 해쉬함수를 만들어 골고루 연결해주는 것이 중요하다.

2. 충돌 처리

2-1. 가장 무난한 방법은 Chaining이다.

index에 따른 bucket을 한개만 쓰는 것이 아니라, 연결 리스트로 만들어줘서 여러개의 value를 담을 수 있게 한다. 

위 그림은 John Smith와 Sandra Dee의 index가 152로 겹치는데, bucket을 연결 리스트로 만들어 해결한 예시이다.

 

연결 리스트말고도 트리로도 구현할 수 있는데, 실제 JDK의 경우에는 index에 있는 노드 크기에 따라 저장하는 구조가 달라진다.

 

2-2. 다른 방법으로는 Open Addressing이 있다.

Open Addressing 방식은 추가적인 메모리 공간을 사용하지 않고, 다른 bucket의 빈 공간을 이용하는 방식이다.

위 그림은 아까처럼 index가 152로 동일한 두 key 중, 한 개의 key를 빈 자리를 찾아 다른 곳에 저장해주는 모습이다.

다른 곳에 저장할 때에도 여러 가지 탐색법이 있는데, 선형 탐사 및 제곱 탐사, 이중 해싱 등이 있다.

참조

https://bcho.tistory.com/1072

Hashtable의 이해와 구현 #1

https://baeharam.netlify.app/posts/data%20structure/hash-table

[DS] 해쉬 테이블(Hash Table)이란? - 배하람의 블로그