해시 충돌 방지 로직에는 Open addressing, Chaining이 있다.

Open addressing

• 탐사 규칙
  • linear probing: h(k) + i
    • 항목이 삽입될 때, 해시 충돌이 나면 비어있는 키를 순차적으로 찾도록 해서 해시충돌을 해결
  • Quadratic Probing
  • Double Hashing

Chaining

• Chaining in hash tables involves storing colliding elements in linked lists within the same bucket.
• It offers benefits such as flexible memory allocation and simple implementation.
• hash table의 bucket에 다른 자료구조를 삽입하는 방식
• hash 키로 먼저 버킷을 찾고 버킷 안에서 탐색
• 링크드 리스트로 관리하기 때문에 모든 데이터를 한번에 가지고 있을 필요 없이 다음 노드의 포인터만 알면 됨
• 메모리 사용량이 크고 링크드 리스트를 순회해야하기 때문에 긴 탐색시간이 발생할 수 있음