자바스크립트로 하는 자료구조와 알고리즘(11장) - 해시 테이블

해시테이블

해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고, 키-값 쌍을 기반으로 자료를 얻을 수 있다.

 

자바스크립트에서 객체는 해시 테이블과 같은 방식으로 키와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.

 

해시테이블 주요 함수

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

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

둘다 시간 복잡도 O(1)

 

-> 인덱스가 해싱 함수에 의해 계산되는 배열과 유사하다. 이때 인덱스는 메모리에서 유일한 공간을 식별하기 위한것

 

locaStorage 는 해시테이블에 기반한 자료구조의 예이다.

브라우저 내에 자료를 유지할 수 있으며, 세션 이후(페이지를 새로고침 등)에도 접근 가능하다는 것을 의미한다.

 

해싱 기법

해시 함수(해시 테이블에서 가장 중요)

특정 키를 자료를 저장하는 배열의 인덱스롤 변환한다.

좋은 해시 함수가 되기 위해서는 결정성, 효율성, 균일한 분배 가 동반되어야한다.

 

해싱의 기법

소수 해싱

소수를 사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성

 

탐사 

해시테이블에 데이터를 집어 넣다보면 인덱스 충돌이 발생한다. 이런 부분을 피하기 위해 탐사 해싱기법을 사용한다.

 

1) 선형 탐사

한 번에 한 인덱스를 증가 시킴으로써 사용 가능한 인덱스를 찾는다.

인덱스가 값이 들어있으면(충돌이 나면) 다음 방(바로 옆방)을 찾아 넣는다.

단점은 군집이 쉽게 발생한다는 것.

 

2) 이차 탐사

선형탐사의 단점인 군집 문제를 해결 하는데 좋은 기법

바로 옆방을 찾아서 넣는 것이 아니라 완전 제곱을 사용하여 옆방에 집어 넣는다.

 

 

재해싱/이중해싱

키를 균일하게 분배하는 방법 중 이차 해싱함수를 사용해 원래 해싱함수로 부터 나온 결과를 한번 더 해싱하는것!