자료구조 & 알고리즘 (해시 테이블 - HashTable)

해시 테이블

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

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조

삽입은 0(1)이며 키를 알고 있다면 ,삭제, 탐색도 0(1)로 수행한다.

해시 함수

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

해시 테이블의 문제점

만약 해시 함수의 결과가 동일하게 겹칠 수 있다.

Hash Collision

선형 탐사법

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

제곱 탐사법

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

이중 해싱

충돌이 발생하면 다른 해시 함수를 이용한다.

분리 연결법

버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

해시테이블을 사용하면 0(1)에 찾을 수 있다.

따라서 빠르게 값을 찾아야하는 경우 해시 테이블을 사용하는 것이 좋다.

JavaScript 사용법

JavaScript Array = Hash Table

Map

Set