Hash table
- hash function h를 이용해서 (key, value)를 index:h(k)에 저장
-> "키 k 값을 갖는 원소가 위치 h(k)에 hash된다." or "h(k)는 키 k의 해시 값이다" - key는 무조건 존재해야 하며, 중복되는 key가 있으면 안됨
- 데이터를 저장할 수 있는 각각의 공간을 slot or bucket
Collision
- 서로 다른 key의 해시값이 똑같을 때 발생
-> collision이 최대한 적게 나도록 hash function을 잘 설계해야하고, 어쩔 수 없이 collision이 발생하는 경우 seperate chaning 또는 open addressing등의 방법을 사용하여 해결
-> 좋은 hash function의 조건은 각 상황마다 good hash function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야하고, 해시값이 최대한 겹치지 않아야 함
시간복잡도와 공간효율
- 시간복잡도는 저장, 삭제, 검색 모두 기본적으로 O(1)이지만, collision으로 인하여 최악의 경우 O(n)이 될 수 있음
- 공간효율성은 떨어짐, 데이터가 저장되기 전에 미리 저장공간(slot, bucket)을 확보해야 하기 때문
-> 저장공간이 부족하거나 채워지지 않은 부분이 많은 경우가 생길 수 있음
