TIL 9)해시 테이블

0. 해시 테이블이란?

사물함과 해시 테이블은 비슷한 성질을 가지고 있다.

사물함과 해시 테이블 모두 key를 인덱스로 변환하여 값을 넣게 된다.

해시 테이블은 한정된 배열 공간에 key를 index로 변환하여 값들을 넣게 된다.

해시 테이블은 키와 값을 받아 키를 Hashing하여 나온 index에 값을 저장하는 선형 자료구조다.

1. 해시 함수

해시 함수는 입력받은 값을 특정 범위 내 숫자로 변경하는 함수다.

만약 해시함수를 통과한 결과물이 같다면 문제가 발생한다.(해시 충돌)

해시 충돌의 해결법

1. 충돌이 발생하면 옆으로 한 칸 이동한다.

최악의 경우 탐색에 선형 시간이 걸릴 수 있다.

2. 충돌이 발생하면 발생한 횟수의 제곱만큼 옆으로 이동한다.

충돌이 한 번 발생하면 한칸, 두 번 발생하면 4칸 이동한다.

3. 이중 해싱

충돌이 발생하면 다른 해시 함수를 이용한다.
충돌이 발생할 경우 기존 해시 함수가 아닌 새로운 해시 함수를 이용한다.

4. 분리 연결법

해시 함수의 리턴값을 연결 리스트로 만들어준다.

2. 해시 테이블의 사용

key 또는 value값을 통해 원하는 정보를 알고 싶을때 해시 테이블을 사용한다.

선형 연결리스트나 배열을 사용할 경우 최악의 경우 전부 탐색을 해야할 경우가 생긴다.

따라서 이런 경우는 해시테이블을 사용하는 것이 시간복잡도에도 이득이 된다.

빠르게 값을 찾아야 하는 경우는 해시 테이블 사용!

3. HashTable in JavaScript

자바스크립트에서 Map을 이용해 hashtable을 구현할 수 있다.