1. 개념

1.1 글

• 동일한 입력값에 대하여 동일한 해쉬결과를 도출하는 함수
• 상이한 입력값에 대하여 상이한 해쉬결과를 도출하는 함수

1.2 그림

2. 예시

2.1 문제

• 8자리의 빈칸에 서로다른 값을 입력하고자 한다.
• 입력값 list = [빨, 주, 노, 초, 파, 남, 보, 검]

2.2 슈도 코드

• list 만들기: list 형식으로 8개 칸 만들기
• 자리 지정하기: hash(빨) % 8, hash(주) % 8, ...
• 결과: 빨, 노, 초, 주, 보, 검
• 왜 8개 모두 입력되지 않았을까? 그 이유는 충돌 때문이다.

3. 충돌

3.1 개념

• 동일한 자리에 서로 다른 값이 겹치는 현상
• 상이한 해쉬결과가 도출되었으나 나머지의 값이 동일해 같은 자리에 서로 다른 값이 입력됨
• 예> 25/8의 나머지 = 1, 33/8의 나머지 = 1

3.2 해결방법

3.2.1 체이닝(Chaining)

• 개념: 자리에 linked list 형식으로 다양한 값을 받는 방법
• 도식화
  

3.2.2 개방 주소법(Open Addressing)

• 개념: 겹치는 자리 주변의 또 다른 자리를 찾아 입력하는 방법
• 선형 탐색, 제곱 탐색, 이중 해쉬으로 구분됨

4. 시간복잡도

• 시간 복잡도: O(1)
• 이유: 단 번에 입력값을 찾을 수 있음
• 예시: list[hash('원숭이') % 8]은 항상 list의 동일한 index를 가리킴