Today's topic
이번 posting에서는 hash table이라는 자료 구조에 대해 알아보고자 한다.
👉 What is hash table?
Hash table은 data를 빠르게 찾을 수 있는 특수한 자료 구조이며 key와 value의 쌍으로 이루어진 값의 list 이다.
위의 그림은 hash table의 예시이다. Key는 hash function을 거쳐 hashing 된 index에 value를 저장한다.
좀 더 자세히 말하면, 검색하고자 하는 키값을 입력받아서 해쉬 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조입니다.
👉 Why use hash table?
Hash table은 key에 대한 value를 효율적으로 찾을 수 있다는 장점이 있다. 해당 key value가 만약 array에서 찾으려면 하나 하나의 key value를 비교해야 한다. 그래서 만약 배열에 N개 이면 N개를 확인해야 하기에 O(N)이라는 시간이 걸린다. 하지만 Hash table은 하나의 key에 하나의 value가 matching되어 있기 떄문에 O(1)이라는 시간이 걸린다. 아직 O(N)에 대해서는 잘 알지 못하지만 O(1) < O(N) 인 것은 문맥상으로만 봐도 파악할 수 있다. O(N)에 대해서는 추후에 정리해 볼 것이다.
O(1)의 시간이 훨씬 짧은 시간이 걸리기에 hash table을 data 저장시 사용 한다.
👉 Hash table의 특징
- Key => value를 찾는 단방향으로만 진행이 가능하다.
Hash table은 key가 value의 위치를 결정한다는 대전제를 가지고 있다. 그렇기에 Key value에서 key를 가지고 value를 찾을 시 O(1)이라는 시간이 걸리지만, 반대의 경우에는 value가 N개의 key를 전체적으로 비교하며 찾아야 하기에 O(N)이라는 시간이 걸리게 된다. 그래서 hash table를 쓰는 빠른 찾기의 의미가 없게 된다.- 각 Key는 딱 하나만 존재할 수 있으나, value는 여러 instance가 존재 할 수 있다.
👉 Collision(충돌)
하나의 hash table에 하나의 key-value 값이 채워지면 문제가 없겠으나, 보통 한정된 table 내 저장을 하다보니 겹치는 경우가 생기게 된다. 이미 value가 들어가있는 cell에 값이 겹치게 되는 경우를 충돌이라 한다. 무한으로 저장할 수 있는 cell이 있지 않기에 이러한 충돌의 경우 해결할 수 있는 방법이 크게 2가지가 있다.
- 분리 연결법(Separate chaining)
Cell에 값이 겹치게 되면 cell에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.
- 장점
1. 구현이 단순하다.
2. 연결 리스트로 저장하기 때문에 table이 가득차지 않는다.
3. 해시 함수 및 적재율에 영향을 덜 받는다.
4. 키의 삽입 또는 삭제 횟수와 빈도를 알 수 없을 때 주로 사용한다.
- 단점
1. 연결 리스트를 사용해 키를 저장하므로 캐시 성능은 떨어진다.
2. 사용하지 않는 slot이 생길 수 있어 공간 낭비가 발생하게 된다.
3. 한 slot에 계속해서 저장된다면 체인이 길어져 최악의 경우 검색 시간이 O(N)이 될 수 있다.
- 개방 주소법(Opening addressing)
충돌이 일어난 키 값을 비어 있는 다른 주소를 찾아 저장하는 방법입니다.
모든 요소를 해시 테이블 자체에 저장하기 때문에 테이블의 크기는 키의 개수보다 크거나 같아야 한다.
개방 주소법 내에는 3가지 방법이 있다.
선형 탐색 (Linear Probing), 제곱 탐색 (Quadratic Probing), 이중 해시 (Double Hashing)
1. 선형 탐색(Liner Probing)
선형적인 형태로 충돌이 발생하면 1씩 증가하면서 빈 slot을 찾는 방식
2. 제곱 탐색(Quadratic Probing)
충돌이 발생하면 2차 함수 꼴로 증가하면서 빈 slot을 찾는 방식
3. 이중 해시 (Double Hashing)
이중 해싱은 탐사할 해시값의 규칙성을 제거해 clustering을 방지하는 기법
📖 출처 :
https://yoongrammer.tistory.com/82#%EB%82%98%EB%88%97%EC%85%88_%EB%B0%A9%EB%B2%95_(Division_method)
My opinion
Hashing은 보안으로만 사용되는지 알았는데 key-value 형태로 데이터 저장 목적으로 사용된다는 점이 새로웠다. Algorithms을 알면 알수록 신기하고 재미있는 것 같다.
