해시 테이블

해시 테이블을 알기전 먼저 연관 배열 객체에 대해 알아야 한다.

해시 테이블은 고정된 크기의 자료구조로 처음에 크기가 정해진다. 해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고 키-값 쌍을 기반으로 자료를 얻을 수 있다.

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

해시 테이블의 요소

• 키(key)
  고유한 값. 해시의 input이 된다. 문자열로 이루어 지며, 무한한 가짓수를 가지고 있다. 메모리에서 유일한 공간을 식별하기 위한 것이다.

• 해시 함수(hash function)
  해시 함수는 특정 키를 자료를 저장하는 배열의 인덱스로 변환한다.

• 해시(hash)
  해시 함수의 결과물이며, 저장소에서 값과 매칭되어 저장된다.

• 값(value)
  저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

해시 테이블의 주요 함수

• put()
  자료를 해시 테이블에 저장하는 데 사용된다.

• get()
  해시 테이블로부터 자료를 얻는 데 사용된다.

해시 충돌(hash collision)

문자열 형태라 무한한 키에 비해 생성 처음부터 고정된 값을 가지는 유한한 해시 때문에 키가 유일하지 않은 것을 말한다.

해싱 기법

좋은 해시 함수가 되기 위한 요구 사항

• 결정성: 동일한 키는 동일한 해시 값을 생성해야 한다.
• 효율성 : 시간 복잡도가 O(1)이어야 한다.
• 균일한 분배 : 배열 전체를 최대한 활용해야 한다.

소수 해싱

모듈러 연산을 통해 인덱스를 얻어내는 방법. 여기서 소수는 해시 테이블의 개수가 된다.
소수 해싱은 고정된 크기에 대해 가장 균등한 분배를 보장한다. 하지만 소수가 아닌 작은 수에 의한 모듈러는 충돌이 자주 일어난다.
모듈러 나눗셈은 해싱에 있어 지켜야 할 철 번째 해싱 기법이다.

탐사

• 선형 탐사
  동일한 키로 해싱이 되는 경우 해당 키의 다음 빈 곳을 찾아 해싱하는 방법.
  선형 탐사는 충돌이 일어났다면 get(key)를 사용할 때 원래 해시 결과에서 부터 원하는 결과를 찾을 때까지 테이블을 순회하게 된다.

  ex)
  만약 해싱된 키가 7인데 이미 값이 있을 경우 다음으로 빈 곳이 8이라면 8로 해싱된다.
  만약 8이 아니라 16이 다음 빈 곳이 었다면 get(key)사용 시 원래 결과인 7부터 16까지 테이블을 순회한다.

• 이차 탐사
  이차 탐사는 매번 1씩 증가시키는 것이 아니라 완전 제곱을 사용하는 방법이다. 이는 사용 가능한 인덱스에 키를 균등하게 분배하는 데 도움이 된다.

재해싱/이중 해싱

재해싱은 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이다. 이때 사용되는 이차 해싱 함수가 가져야 할 요구 사항이 존재한다.

이차 해싱 함수가 지녀야 할 주요 요구 사항

• 첫 번째 해싱 함수와 달라야 한다.
• 시간 복잡도는 O(1)이어야 한다.
• 결과가 0이 아니어야 한다.(0은 초기 해시 값을 결과로 내기 때문에)

참고자료

[엔지니어 대한민국] 해쉬테이블에 대해 알아보고 구현하기 :
https://youtu.be/Vi0hauJemxA
[JS] Hash Table 구현 :
https://velog.io/@yunsungyang-omc/JS-Hash-Table-%EA%B5%AC%ED%98%84
자바스크립트로 하는 자료 구조와 알고리즘(에이콘)

해시 테이블 시뮬레이터 :
https://www.cs.usfca.edu/~galles/visualization/OpenHash.html