해시 테이블

개념 정의

키와 값의 한 쌍으로 데이터를 저장하는 자료구조이다.

키를 통해 빠르게 값을 찾는 것이 목표이다.

배열과 비교

const menuArr = [
{name: "coffee", price: 10},
{name: "burger", price: 15},
{name: "tea", price: 5},
{name: "pizza", price: 10},
{name: "juice", price: 5},
];
//여기서 피자의 가격을 찾으려면 인덱스 0부터 탐색한다.
//커피..버거..차..피자!, 선형 검색
//O(N)
const menuHash = {
	coffe: 10,
	burger: 15,
	tea: 5,
	pizza: 10,
	juice: 5,
}
menu["pizza"] // = 10
//O(1)

동작 방식

해시 함수를 통해 키를 넣으면 인덱스가 반환된다.

값이 저장된 공간에 인덱스로 직접 접근하는 것이 가능해진다.

해시 함수

그럼 해시 함수는 뭘까?

임의의 길이의 데이터를 정해진 길이의 값(인덱스)으로 변환해주는 역할을 한다.

특성

• 압축성 : 다양한 길이의 키를 고정된 크기로 반환
  
• 저항성 : 결과값을 바탕으로 입력 값을 찾는 것이 불가능한 성질
  

충돌 (Collision)

해시 함수에 다른 키를 넣었는데 동일한 인덱스를 반환하는 경우가 발생한다.

이런 경우를 충돌이라고 한다.

체이닝 (Chaining)

충돌 해결 방법

해당 인덱스에 연결리스트를 만들어서 데이터를 연결한다.

인덱스 4에 값이 중복되면 연결 리스트로 만들어서 저장한다.

(그림은 배열이지만 실제론 연결 리스트를 쓴다. 연결 리스트는 떨어진 노드를 포인터로 연결하기 때문에 chaining이란 네이밍이 적절한 것 같다.)

오픈 어드레싱(Open Addressing)

충돌이 발생하면 다른 인덱스에 값을 저장한다.

추가적인 메모리 할당 없이 고정된 크기 내에서 충돌을 해결 할 수 있다.

• 선형 탐사(Linear Probing) 충돌이 발생하면 그 다음 인덱스로 이동하여 빈 슬롯을 찾는다. 다음 인덱스가 계속 꽉 차있으면 오래 걸릴 수 있다. (1차 클러스터링 문제)
  
• 제곱 탐사(Quadratic Probing) 인덱스에 제곱하여 빈 슬롯을 찾는다. (1^2, 2^2, 3^2…) 같은 이유로 2차 클러스터링이 발생할 수 있다.
  
• 더블 해싱(Double Hashing) 두 개의 해시 함수를 사용하는 방식이다. 첫 번째 함수로 충돌이 발생하면 두 번째 함수를 사용하여 빈 슬롯을 찾는다. 가장 효율적인 방식이다.
  

참고자료 (노마드코더 유튜브 영상)