[TIL] 해시 테이블

1. 해시 테이블의 정의

해시 테이블은 고정된 크기의 자료 구조로 처음에 크기가 정해진다. 

 

해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고, 키-값을 기반으로 자료를 얻을 수 있다. 자바스크립트에서 자바스크립트 객체는 해시테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.

 

해시 테이블

해시 테이블에는 put(), get() 이리ㅏ는 두 가지 주요 함수가 있다. put()은 자료를 해시 테이블에 저장하는데 사용하고, get()은 해시 테이블로부터 자료를 얻는 데 사용된다. 두 함수 모두 시간 복잡도가 O(1)이다. 

 

간단히 말하자면 해시 테이블은 인덱스가 해싱 함수에 의해 계산되는 배열과 매우 유사하다. 이때 인덱스는 메모리에서 유일한 공간을 식별하기 위한 것이다. 

 

2. 해싱 기법

 

해시 테이블에서 가장 중요한 부분은 해시 함수다. 해시 함수는 특정 키를 자료를 저장하는 배열의 인덱스로 변환한다. 좋은 해시 함수가 되기 위한 세 가지 주요 요구 사항은 다음과 같다. 

 

- 결정성: 동일한 키는 동일한 해시 값을 생성해야 한다.

- 효율성: 시간 복잡도가 O(1)이어야 한다.

- 균일한 분배: 배열 전체를 최대한 활용해야 한다.

 

1) 소수 해싱

 

해싱에서 소수는 중요하다. 소수를  사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성하기 때문이다(모듈러 나눗셈은 나중에 더 공부해야겠다).

 

완벽한 해싱 함수의 경우, 충돌이 일어나지 않는다. 하지만 충돌이 일어나지 않는 해싱은 거의 존재하지 않는다. 따라서 해시 테이블에는 충돌을 다루는 전략이 필요하다. 

 

2) 탐사

 

충돌이 발생하는 것을 피하기 위해 탐사 해싱 기법을 사용할 수 있다. 선형 탐사 기법은 증분 시도를 통해 다음으로 사용 가능한 인덱스를 찾음으로써 충돌을 해결한다. 반면 이차 탐사는 점진적으로 증분 시도를 생성하기 위해 이차 함수를 사용한다.

 

2-1) 선형 탐사

선형 탐사는 한 번에 한 인덱스를 증가시킴으로써 사용 가능한 인덱스를 찾는다. 선형 탐사의 주요 단점은 군집이 쉽게 발생한다는 것이다. 군집은 순회해야 할 자료를 더 많이 생성하기 때문에 좋지 못하다.

 

2-2) 이차 탐사

이차 탐사는 군집 문제를 해결하는데 좋은 기법이다. 이차 탐사는 매번 1씩 증가 시키는 대신 완전 제곱을 사용한다. 완전 제곱은 그림 11-5와 같이 사용 가능한 인덱스에 키를 균등하게 배분하는데 도움이 된다. 

 

3. 재해싱 / 이중 해싱

키를 균일하게 분배하는 또 다른 좋은 방법으로 이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이 있다. 다음은 좋은 두 번째 해싱 함수가 지녀야할 세 가지 주요 요구 사항이다.

- 달라야 함: 두 번째 해싱 함수가 키를 더 잘 분배하기 위해서는 첫 번째 해싱 함수와 달라야 한다. 

- 효율적이어야 함: 두 번째 해싱 함수의 시간 복잡도가 여전히 O(1)이어야 한다.

- 0이 아니어야 함: 두 번째 해싱 함수의 결과가 0이 되어서는 안 된다. 0 은 초기 해시 값을 결과로 내기 때문이다.

4. 요약

- 해시 테이블은 크기가 처음에 정의되는 고정된 크기의 자료구조다.

- 해시 테이블은 배열의 인덱스를 생성하는 해시 함수를 사용해 구현된다.

- 좋은 함수는 결정적이고 효율적이면서 균등하게 배분한다.

- 해시 충돌은 균등하게 분배하는 해시 함수를 사용해 최소화 돼야 한다. 하지만 일부 충돌이 발생하는 것은 피할 수 없다. 

- 대표적인 해시 충돌 처리 기법에는 선형 탐사와 이차 탐사, 이중 해싱이 있다.