💿자료구조 - 해쉬테이블 Hash Table

이진 탐색 트리 (최악의 경우 O(N)) 의 성능을 개선한

AVL 트리, 레드-블랙 트리, B-트리의

탐색, 삽입과 삭제 연산의 시간복잡도는 모두 O(logN)

 

그런데! O(logN)보다 좋은 성능을 갖는 자료구조는 없을까?

>> Hash Table!

 

<Hash Table>

 : 데이터의 값과 Hash 함수에 의해 삽입 위치가 결정되는 자료구조

 : 충돌의 경우를 무시한다면 삽입, 삭제, 검색에 O(1)만 소요됨

---

[ Hash Table의 충돌 해결법 ]

 

1. Chaining

 

 

---

---

2. Linear Probing

 

---

어라.. 문제점 1

---

해결!!

---

어라.. 문제점 2

---

3. Quadratic Probing을 통한 해결!

---

4. Double Hashing