해시 테이블은 자료구조 중 하나로 매우 빠른 평균 삽입, 삭제, 탐색 연산을 제공한다.
파이썬을 기준으로 작성하기 때문에 딕셔너리로 비유하면, key 와 value를 가지고 있는 형태의 데이터를 가지고 있다고 가정을 해보자.
이 데이터를 해시 테이블에 넣을 때 몇 번 인덱스에 저장할 지를 고민한다.
이때 필요한 것이 해시 함수(hash function)이다.
해시 함수는 key의 정보를 hash table에 매핑한다.
간단한 예시로는 key에 len(hash table)을 나눈 나머지로 hash table의 인덱스에 매핑하는 방법이 있다.
그러나 만약 두 데이터가 매핑한 인덱스가 같은 값이 나오는 경우가 있다.
이런 경우를 충돌(collision)이라고 한다.
충돌은 되도록 없는 것이 좋지만, 완전히 없는건 비현실적이기 때문에 줄이는 것을 목표로 한다.
이러한 방법을 collision resolution method라고 부른다.
해시 테이블에서는 3가지가 중요하다.
1. hash table
2. hash function
3. collision resolution method