Key와 Value를 1:1로 연관지어 저장하는 자료구조
-
Key를 이용해 Value 도출. 이 과정을 해싱(Hashing)이라 함
-
Key, Hash Function, Hash, Value, 저장소(Bucket, Slot)로 구성
Key: 고유한 값
Hash Function: Key를 Hash로 바꿔주는 역할. 해시 충돌(서로 다른 Key가 같은 Hash가 되는 경우)를 최대한 줄이는 함수를 만들어야 함
Hash: Hash Function의 결과. 저장소에서 Value와 매칭되어 저장
Value: 저장소에 최종적으로 저장되는 값. Key와 매칭되어 저장, 삭제, 검색, 접근 가능 -
시간복잡도
| 평균 | 최악 | |
|---|---|---|
| 탐색 | O(1) | O(N) |
| 삽입 | O(1) | O(N) |
| 삭제 | O(1) | O(N) |
=> 해시 함수를 거치는 시간
- Hash 충돌 해결: linked list 사용
