해시 테이블

• 키와 값을 받아, 키를 해싱하여 나온 인덱스에 값을 저장하는 선형 자료구조이다.
• 삽입은 O(1), 삭제와 탐색은 인덱스를 알고 있다면 O(1)이 걸린다.

해싱 함수

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

해시 충돌(Hash Collision)과 해결 방법

만약 다른 키를 해시 함수로 해싱한 결과가 같다면, 이를 해시 충돌이 발생했다고 한다. 해시 충돌을 해결하는 방법으로 아래의 네 가지가 있다.

선형 탐사법

• 개방 주소법 중 하나이다.
• 충돌이 발생하면 단순히 인덱스 옆 한 칸을 이동한다.
• 단순하지만 특정 영역에 데이터가 몰릴 수 있다는 단점이 있다.
• 이동한 영역에서 충돌이 또 발생한다면 충돌이 발생하지 않을 때까지 이동하기 때문에, 최악의 경우 O(n)이 걸릴 수 있다.

제곱 탐사법

• 선형 탐사법에서 특정 영역에 데이터가 몰리는 단점을 해결하기 위한 방법이다.
• 충돌이 발생한 지점에서 충돌이 발생한 횟수의 제곱만큼 이동한다.
• 충돌이 발생한 만큼 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다는 덜하다.

이중 해싱

• 충돌이 발생할 경우 기존 해시 함수가 아닌 다른 해시 함수를 이용해서 해시 값을 만든다.

분리 연결법

• 충돌이 발생할 경우 다른 인덱스로 이동하지 않고, 버킷의 값을 연결리스트로 사용(Chaining)하여 충돌이 발생하면 리스트에 값을 추가한다.
• 최악의 경우 하나의 버킷이 무한정 늘어날 수 있다는 단점이 있다.

  버킷이란 해시 테이블에서 데이터(키와 밸류의 형태)가 저장되는 곳을 의미한다. 슬롯이라고도 한다.

언어 별로 해시 충돌을 해결하는 방법이 각각 다른 듯하다. 자바스크립트가 실제로 충돌을 어떻게 해결하는 지 궁금해졌다.🤔

참고 자료 및 강의

프로그래머스 프론트엔드 데브코스 Day3 [강의] 해시 테이블