해시 테이블

해시테이블이란?

키와 값을 받아 키를 해싱하여 나온 인덱스 값을 저장하는 선형 자료구조이다.

해시테이블의 특징

• 삽입의 시간복잡도는 O(1)이며, 만약 키를 알고 있다면, 삭제와 탐색의 시간복잡도 역시 O(1)로 수행하게 된다.
• 해시테이블에서 각 테이블의 인덱스를 bucket이라하며, 테이블의 각 요소는 키와 값 모두 저장하고 있어야 함.

해시충돌

해시테이블을 사용할 때 발생하는 문제점으로 어떠한 값을 해싱할 경우에 리턴된 결과 값이 같을 경우 발생한다.

해시 충돌을 해결하기 위한 방법

• Open Addressing

  • 선형 탐사법: 충돌이 발생하면 옆으로 한 칸 이동한다.
  • 제곱 탐사법: 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
  • 이중 해싱: 해시 충돌이 발생하면 다른 해시함수를 이용하여 새로운 인덱스를 생성

• Chaining

  • 분리 연결법 : 충돌이 발생했을 때 새로운 공간에 저장하는 것이 아닌, 이를 동일한 버킷에 저장, 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가

사용할 곳

빠르게 값을 찾아야하는 경우나 어떠한 데이터를 묶을 때 사용하기 좋다.
자바스크립트에서는 주로 object나, new Map()을 사용하여 만들수도있다.