Hash Table - 데이터 저장의 끝판왕

해시테이블은 키(Key)를 통해 데이터를 저장하고,
다시 키를 이용해 빠르게 검색하는 자료구조 !

핵심은
👉 데이터를 "그냥 저장"하지 않고
👉 키를 해시 함수에 넣어서 나온 인덱스에 저장한다는 것

??: 왜씀?

• 리스트나 배열에서 값을 찾으려면 O(n)
• 해시 테이블은 평균적으로 O(1)
  - "거의 즉시" 찾을 수 있음 !

그렇다고 한다. 이제 구조를 알아보자

구조

💡 기본 구성

[0] → None  
[1] → ("apple", 3)  
[2] → ("banana", 7)  
[3] → ("grape", 5)  
...  

1. 키: "apple"
2. 해시 함수: hash("apple") → 1
3. 테이블의 1번 인덱스에 값 저장: ("apple", 3)
   
   
   📌 해시 함수는 키를 숫자로 바꿔서 배열 인덱스로 변환해주는 역할

해시 충돌 (Collision)

해시 충돌은 서로 다른 키인데도 해시값이 같으면 같은 위치에 저장되려 하는 문제이다.

왜 충돌이 생길까?

• 해시 함수는 무한한 키를 유한한 크기의 배열 인덱스로 압축해야 하기 때문

• 결국 언젠가는 다른 키가 같은 인덱스로 매핑되는 일이 생김

.
.
.
.

그렇다면 해결 방법에는 어떤 것이 있을까?

충돌 해결 방법

1. 체이닝 (Chaining)

• 충돌난 데이터를 리스트로 연결해서 저장
• 배열의 각 인덱스가 리스트(버킷) 역할을 함

table[3] → [("apple", 3), ("banana", 7)]

→ 삽입은 빠르고 구현도 간단
→ 하지만 한 버킷에 너무 많이 모이면 검색 O(n) 될 수 있음

2. 개방 주소법 (Open Addressing)

• 빈 자리를 찾아 저장하는 방식
• 충돌이 나면 그다음 인덱스, 그다음 그다음... 식으로 이동

대표적인 전략들

→ 한 배열에만 저장되므로 메모리 사용은 좋지만,
→ 삭제/재삽입 관리가 까다롭고, 빈자리 찾는 데 시간이 들 수 있음