[ch 13] 테이블과 해쉬

[주제]

- 해쉬 테이블의 개념

[정의]

사원 번호(Key)	직원(Data)
00150	홍길동
01320	고길동
00099	아무개

- 표(Table) 형태의 자료구조

- 저장되는 데이터가 키(Key) 값과 데이터 값이 하나의 쌍으로 구성됨

- 키 값이 없으면 데이터를 저장할 수 없으며, 키 값을 중복될 수 없음

■ 그림(해쉬 함수)

- 일정한 규칙으로 작성된 중복되지 않는 고유 값을 함수를 통해 쉽게 구분할 수 있는 값으로 변경

  ※ 해쉬함수(Hash Function): 넓은 범위의 값을 좁은 범위의 값으로 변경하는 역할

- 하지만 해쉬함수가 단순한 산술 연산으로만 되어있으면 값이 중복되어버리는 충돌 현상이 발생됨

- 위 그림은 테이블의 메모리 상황을 표현

- 칠해진 영역이 데이터가 저장된 슬롯

- 데이터가 저장되는 위치가 골고루 퍼지는 형태가 가장 이상적임

- 좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만듦

[충돌 문제의 해결책]

1. 선형 조사법(Linear Probing)

- 충돌이 발생했을 때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 저장하는 방법

  ※ 테이블의 저장 방식이 '배열'이라고 가정

- f(x): Key % 6

- 충돌 시 적용되는 해쉬 함수

■ 그림(선형 조사)

- 'Key가 10'인 데이터는 해쉬 함수를 통해 '4'의 위치에 저장됨

- 다음에 저장되는 데이터의 'Key가 4'인 경우 저장되는 위치가 '4'로 동일하기 때문에 '+1'되어 '5' 위치에 저장됨

- 하지만 우연찮게 충돌 현상이 자주 발생할 경우 바로 옆에 계속 쌓이게 때문에 데이터가 한 쪽에 몰리는 현상이 발생됨

2. 이차 조사법(Quadratic Probing)

- 선형 조사법의 단점을 보완한 방법

- 충돌 시 다음 위치에 저장되는 간격을 배수로 늘림

- 하지만 이차 조사법도 근복적으로 '다음 위치는 찾는 방식이 항상 규칙적이다'라는 단점이 존재

■ 그림(단점을 해결하기 위한 준비)

- 선형 조사법, 이차 조사법의 단점을 해결하기 위해선 각 슬롯마다 상태를 지정해줘야 함

- Empty: 데이터가 저장된적이 없는 상태

- Deleted: 데이터가 저장되었다가 삭제된 상태

- Inuse: 데이터가 저장되어 있는 상태

- 'Deleted' 상태를 확인하여 충돌 상태를 판단

3. 이중 해쉬(Double Hash)

- 1차 해쉬 함수: 키를 근거로 저장위치를 결정하는 도구

※ '15'은 결정에 따라 다름. 일반적으로는 배열의 길이 값을 사용

- 2차 해쉬 함수: 충돌 발생 시 몇 칸 뒤를 살필지 결정하는 도구

- '+1'은 2차 해쉬 함수가 적용될 때 0값이 나오지 않기 위함

- 0 값이 나오면 제자리이기 때문에 의미가 없음

- 'y'는 일반적으로 1차 해쉬 함수의 '% 연산되는 값'보다 작고, 소수(2, 3, 5...)인 값을 사용

  ※ 통계적으로 소수를 사용했을 때 충돌 현상이 발생되는 확률이 현저히 낮춰진다는 근거에 의함

■ 이중 해쉬 예

▷ f(3) = 3 % 15 = 3

▷ f(18) = 18 % 15 = 3

▷ f(33) = 33 % 15 = 3

- 두 번째, 세 번째의 경우 충돌이 발생했으므로 2차 해쉬 함수를 적용

  ※ f(x) = 1 + (x % 7)

▷ f(18) = 1 + (18 % 7) = 5

▷ f(33) = 1 + (33 % 7) = 6

- 이후, 빈 슬롯을 찾을 때까지 탐색 횟수를 곱하면서 자리를 찾아감

▷ f(18) → f(18) + 5 x 1 → f(18) + 5 x 2 → f(18) + 5 x 3 → ...

▷ f(33) → f(33) + 6 x 1 → f(33) + 6 x 2 → f(33) + 6 x 3 → ...

[체이닝]

- 이전의 해결 방식은 '열린 어드레싱 방법(Open Addressing Method)'이었으며,

  체이닝은 '닫힌 어드레싱 방법(Closed Addressing Method)'에 속함

- 충돌 현상이 발생했을 경우 새로운 위치를 찾지 않고 동일한 위치에 저장하는 방식

- 배열과 연결 리스트를 이용한 방식이 존재

- 배열은 2차원 배열을 활용하는데 충돌이 발생하지 않을 경우 메모리 낭비가 심하고,

  배열 특성상 최대 횟수를 지정해야하는 단점이 존재

- 때문에 연결 리스트를 활용하는 것이 일반적임

■ 그림(연결 리스트 방식의 체이닝)

- 하나의 Key에 다수의 슬롯을 저장

- 탐색을 할 때 동일한 Key에서 연결되어 있는 모든 슬롯을 조사해야하는 단점이 존재하지만, 이는 해쉬 함수로 해결함