[Algorithm] Hash table

Hash Table 이란?

• (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 장점이 있다.
• 해시 테이블이 빠른 검색 속도를 제공하는 것은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 
• 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다.
• 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
• Ex) (key, value) = ("John Smith", "521-1234")를 크기가 16인 해시 테이블에 저장하면, 먼저 index = hash_function("John Smith") % 16으로 index를 구해서 array[index] = "521-1234"로 저장한다.
• 평균 시간 복잡도는 O(1)이다. 단, 충돌이 발생한 경우 연결된 리스트들을 검색해야 하므로 O(N)까지 증가할 수 있다.
• 테이블이 꽉 찬 경우 확장해주어야 하는데 이는 매우 심각한 성능의 저하를 불러오기 때문에 안해주도록 설계하는게 좋다.
• 자주 사용하게 되는 데이터를 cache에 적용하면 효율을 높일 수 있다. 자주 hit하게 된느 데이터를 캐시에서 바로 찾음으로써 해시 테이블의 성능을 향상시킬 수 있다.
• 단점: 순서가 있는 배열에는 어울리지 않는다. 공간 효율성이 떨어진다. hash function의 의존도가 높다.

해시 함수

대표적인 해시 함수는 다음과 같다.

1. Division Method: 입력값을 테이블의 크기로 나누어 계산한다. 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해서 효과가 좋다고 한다.
2. Digit Folding: 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용한다.
3. Multiplication Method: 숫자로 된 key값 k와 0과 1사이의 실수 A, m(보통 2의 제곱수)를 사용해서 h(k)=(kAmod1)xm을 해준다.
4. Universal Hashing: 다수의 해시 함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 방법이다.

충돌

서로 다른 키 값을 돌려서 같은 index가 나오는 경우 충돌했다고 한다. 해시 테이블의 크기(N) 대비, 키의 개수(K)를 적재율(K/N)이라고 한다. Direct Address Table은 키 값을 인덱스로 사용하기 때문에 적재율이 1 이하이지만, 적재율이 1 초과인 해시 테이블은 반드시 충돌이 발생한다.

 

해시 테이블의 구조를 개선해서 해결하는 방법이 2가지가 있다.

1. 분리 연결법 Separate Chaining 

   

   • 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장
   • 해시 테이블의 확장이 필요없고 간단하게 구현이 가능
   • 손쉽게 삭제할 수 있다.
   • 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져 캐시의 효율성이 감소한다.
2. 개방 주소법 Open Addressing
   • 추가적인 메모리를 사용하는 chaining과 다르게 비어있는 해시 테이블의 공간을 활용한다.
   • Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy space로 활용되는데, 그렇기 때문에 Hash table을 재정리 해주는 작업이 필요하다고 한다.
   • 구현하기 위한 대표적인 방법 3가지
     1. Linear Probing: 현재 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장
     2. Quadratic Probing: 해시의 젖아순서 폭을 제곱으로 저장. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2씩 옮긴다.
     3. Double Hashing Probing: 해시된 값을 한번 더 해싱해서 해시의 규칙성을 없애버리는 방식. 더 많은 연산 필요.

---

Reference

https://mangkyu.tistory.com/102

https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o