(Key, Value) 로 데이터를 저장하는 자료 구조.
해시 함수에 Key 값을 입력하면 Value를 저장할 메모리의 Index가 결과값으로 도출된다.
실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
랜덤 탐색, 삽입, 삭제 모두 O(1)라는 성능을 보여준다는 장점이 있지만,
순차 탐색이 불가능하고 해시 함수에 따라 성능이 좌지우지 된다. 최악의 경우 연결 리스트와 다를 바가 없어진다.
| Random Read | Sequential Read | Insert | Delete | |
| 시간 복잡도 | O(1) | X | O(1) | O(1) |
해시 충돌
제아무리 해시 함수를 잘 구축해도 해시 함수 결과값이 중복될 수 있다.
이 경우, 2 가지 방법으로 해결 가능하다.
1. 분리 연결법(Separate Chaining)
단순하게 연결 리스트와 같은 자료구조를 추가로 둬서 중복된 값이어도 추가할 수 있게 만드는 것이다.
2. 개방 주소법(Open Addressing)
충돌이 일어난 결과값이 아닌 해당 값을 활용한 2차 해시 함수의 결과물를 사용하는 것.
Linear Probing, Quadratic Probing, Double Hashing Probing과 같은 방법으로 새 주소값을 얻는다.
