해시 테이블이란?

해시 테이블은 (key, value) 쌍으로 데이터를 저장하는 자료구조이다.
key를 해시 함수로 변환해서
→ 배열 인덱스에 직접 접근해서 값을 빠르게 찾는 구조!

💡 "key로 빠르게 value를 찾는 사전(dictionary) 같은 구조"
배열에서 인덱스로 값을 바로 불러오듯, 해시 테이블에서는 key를 이용해 값을 빠르게 조회할 수 있다.
배열에서는 인덱스가 숫자였지만, 해시테이블은 key가 “문자”나 “객체”일 수 있다!

---

☑️ 왜 사용할까?

• 데이터를 O(1) 에 빠르게 저장/탐색하기 위해서
• key → value 매핑이 필요한 상황에서 사용

---

☑️ 해시 테이블 동작 원리

1. key를 입력
2. 해시 함수를 사용해 key를 숫자로 변환
   → ex) "apple" → hash("apple") = 3
3. 변환된 숫자를 배열의 인덱스로 사용
   → table[3] = value

예시)

"apple" → hash → index 3 → table[3] = "fruit"

---

☑️ 파이썬의 해시 테이블

• 파이썬의 dict(딕셔너리)
• 💡 *set(집합)**도 내부적으로 해시 테이블을 사용한다.

d = {}
d["apple"] = "fruit"
print(d["apple"])  # fruit

---

☑️ 시간복잡도

연산	평균 시간복잡도	최악 시간복잡도 (충돌 시)
삽입	O(1)	O(N)
탐색	O(1)	O(N)
삭제	O(1)	O(N)

일반적으로 O(1) 에 매우 빠르게 동작하지만,
충돌이 많아지면 최악의 경우 O(N)까지도 갈 수 있다.

---

☑️ 어디에 사용될까?

• 사전(dictionary): 단어-뜻 매칭
• 캐시(Cache) 시스템
• 중복 체크 / 빈도수 세기
• 네트워크(ARP 테이블)

---

💡 해시 함수란?

• key를 숫자로 변환하는 함수
• 입력값을 받아 고정된 범위의 숫자(index)로 반환

ex)

hash("apple")  → 189823019  → 189823019 % 1000 = 19

• 보통 mod 연산으로 배열 크기에 맞춘다.