Chap 10. 테이블과 해쉬

해쉬 테이블은 빠른 탐색을 한다.
하지만, 트리의 언급은 없다.

테이블의 탐색 시간 복잡도는 O(1)을 나타낸다.

---

저장하는 데이터에 대하여 키와 값으로 하나의 쌍을 이룰 경우에 테이블이라 칭한다.

키는 유일해야한다.
키가 존재하지 않는 값은 존재할 수 없다.

---

테이블의 문제점

- key의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않을 수 있다.
- key의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

위 두가지 문제를 해결해주는 '해쉬 함수'가 존재한다.

'해쉬 함수'는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.

---

'충돌' 이란 해쉬 함수를 통과하였는데, 키의 값이 동일한 경우를 나타낸다.
'충돌'은 피하는게 아니라, 해결을 해야한다.

---

<좋은 해쉬 함수의 조건>

좋은 해쉬 함수
- '충돌'이 발생활 확률이 낮다. 즉, 데이터가 테이블의 고루 분포되어있다.
- 키의 일부분을 참조하지않고 키 '전체'를 참조하여 해쉬 값을 만든다.
- 키의 특정 위치에서 중복의 비율이 높거나, 공통으로 들어가는 값이 있다면 제외한 나머지로 생성

'충돌'의 해결책이 마련해 있다 한들, '충돌'자체가 발생하지 않아야 데이터의 저장, 삭제
탐색 등의 효율이 높다.

---

<충돌 문제 해결방법>

충돌이 발생하면 빈자리를 찾으면 된다.

● 선형 조사법
충돌이 발생하였을 대 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장

ex) key % 7 인 경우 9와 2는 인덱스 2인 배열에 들어가야한다.
하지만 9가 먼저 인덱스 2를 차지하고 있다면
2는 인덱스 2에 들어갈 수 없다. 따라서 인덱스 3에 들어가야한다.

==> 빈자리 찾는 순서는 f(k) + 1 => f(k) + 2 ...

● 이차 조사법
선형 조사법에서 빈자리 찾는 순서가 f(k) + 1 => f(k) + 2 ...이다.
하지만 이렇게 할 경우 충돌 확률을 더욱 더 높인다.

따라서, 좀 멀리서 빈자리를 찾는 방법이 이차 조사법이다.

ex) f(k) + 1² => f(k) + 2² ...

 

선형 조사법과 이차조사법의 문제점

- 똑같은 해쉬 값이 나온다면 똑같은 위치로 빈 슬롯을 찾게된다.

따라서, 2차해쉬를 사용해야한다.

2차 해쉬 함수 h₂(k) = 1 + ( k % c)