👩💻알고리즘/자료구조
💿자료구조 - 해쉬테이블 Hash Table
비엔 Vien
2024. 5. 9. 17:58
이진 탐색 트리 (최악의 경우 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