해시 테이블

calendar 2022-10-15

해시를 이용해서 key: value 쌍을 저장하고 O(1) 에 value를 찾는 자료구조이다.

  1. 해시 함수를 통해 immutable 한 key에서 해시를 얻는다
  2. 크기를 고정한(n) 배열을 생성하고
  3. 해시를 인덱스(0~n-1)로 변환하여(보통 modulo 연산. 해시 % n)
  4. 배열의 인덱스에 키 밸류를 저장한다
    1. 리스트, 그래프 형태로(Separate Channing)로 저장하거나
    2. 인접한 다른 인덱스에 삽입(Open Addressing)한다.

(해시) 충돌이 발생하면 최악의 경우 탐색에 O(n)이 걸린다.

refs