Hash Table

정의

빠른 삽입과 탐색을 위해 hash 함수를 이용하여 데이터를 관리하는 자료 구조.

종류

1. Hash Set(중복 키값 없게 하는 자료 구조)
2. Hash Map(key-value 저장하는 자료 구조)

원리

1. 해시 함수로 키가 어느 버킷에 저장될지 결정한다.
2. 키를 찾을 때, 같은 해시 함수로 어느 버킷에서 키를 찾을지를 결정한다.

해시 테이블을 설계할 때 주의할 점

1. 해시 함수: 키값의 범위와 버킷의 갯수를 고려한다. 최대한 키값이 버킷에 고루 담길 수 있게 설계한다.
2. 충돌 해결: 버킷의 용량과 한 버킷에 담길 수 있는 키값의 갯수를 고려한다.