JS Hash table

해시 테이블

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

해시 테이블의 주요 함수

• put(): 해시 테이블에 자료를 저장
  • 시간 복잡도: O(1)
• get(): 해시 테이블로부터 자료를 얻음
  • 시간 복잡도: O(1)

브라우저의 localStorage

• 해시 테이블에 기반의 자료 구조
• 주요 브라우저(모던 브라우저?)에서 지원하는 기본 자바스크립트 객체
• 브라우저 내에 자료를 유지할 수 있게 해준다 (세션 이후에도 접근 가능하다는 것을 의미)

해싱 기법

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

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

소수 해싱

소수를 사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성한다. 소수에 의한 모듈러는 고정된 크기에 대해 가장 균등한 분배를 보장한다.

탐사

탐사 해싱 기법을 사용해 충돌을 피하고 배열에서 다음으로 사용 가능한 인덱스를 찾을 수 있다.

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

이차 탐사 이차 탐사는 매번 1씩 증가시키는 대신 완전 제곱을 사용한다. 군집 문제를 해결하는 데 좋은 기법이다.

이중 해싱 / 재해싱

이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이 있다.

• 첫 번째 해싱 함수와 달라야 한다.
• 시간 복잡도가 O(1)이어야 한다.
• 결과가 0이 돼서는 안 된다.

$$ hash_2(x) = R-(x \% R) $$

• $x$ : 첫 번째 해싱의 결과
• $R$ : 해시 테이블의 크기보다 작다.
• $i$ : 반복 시도 횟수

$$ i*hash_2(x) $$

요약

해시 테이블은 처음 정의 할때 지정한 고정된 크기의 자료 구조이다. 배열의 인덱스를 생성하는 해시 함수를 사용해 구현된다. 좋은 함수는 결정적이고 효율적이고 균등하게 분해한다. 하지만 일부 충돌이 발생하는 것은 피할 수 없다.