Chapter13 테이블(Table)과 해쉬(Hash)

2018/02/28 - [프로그래밍/자료구조] - Chapter12 탐색(Search) 2

13-1 빠른 탬색을 보이는 해쉬 테이블

탐색과 관련이 있지만 트리와 관련된 어떠한 것도 언급하지 않는다는 점이 구분된다.

테이블(Table) 자료구조의 이해
이AVL 트리의 탐색 연산이 O(log2n)의 시간 복잡도를 보이는 반면, 테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보인다.

표에 저장된 데이터가 키(key)와 값(value)이 하나의 쌍을 이룰때 '테이블'로 구분 짓는다.
자료구조의 '테이블'은 '사전 구조'라고도 불린다. 더불어 '맵(map)'이라 불리기도 한다.

좋은 해쉬 함수의 조건

좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'라고도 말할 수 있다.

"좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다."

자릿수 선택(Digit Selection) 방법과 자릿수 폴딩(Digit Folding) 방법

"여덟 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네 자리의 수를 뽑아서 해쉬 값을 생성한다."

해쉬 함수를 디자인할 때에는 이러한 방법들보다 키의 특성과 저장공간의 크기를 고려하는 것이 우선이다.

13-1 충돌(Collision) 문제의 해결책

충돌이 발생하면, 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾아야 한다. 다만 빈 자리를 찾는 방법에 따라서 해결책이 구분될 뿐이다.

선형 조사법(Linear Probing)과 이차 조사법(Quadratic Probing)

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

선형 조사법은 충돌 발생시 n칸 옆의 슬롯을 검사한다면, 이차 조사법은 n^2칸 옆의 슬롯을 검사한다.

이중 해쉬(Double Hash)

이차 조사법의 문제점 "해쉬 값이 같으면, 충졸 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다."

- 1차 해쉬 함수: h1(k) = k % 15

- 2차 해쉬 함수: h2(k) = 1 + (k % c)

이런 경우 c는 15보다 작은, 그러면서 소수(prime number) 중 하나로 결정

- 1차 해쉬 함수: h1(k) = k % 15

- 2차 해쉬 함수: h2(k) = 1 + (k % 7)

2차 해쉬 값의 크기만큼 건너 뛰면서 빈 슬롯을 찾게 되므로, 키가 다르면 건너 뛰는 길이도 달라진다. 따라서 클러스터(cluster) 현상의 발생 확률을 현저히 낮출 수 있다. 참고로 실제도롣 이중 해쉬는 이상적인 충돌 해결책으로 알려져 있다.

체이닝(Chaining)

앞서 소개한 유형의 방법들을 가리켜 '열린 어드레싱 방법(open addressing method)'이라 하는데, 이는 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨 있다. 반면 '닫힌 어드레싱 방법(closed addressing method)'은 무슨 일이 있어도 자신의 자리에 저장을 한다는 의미가 담겨 있다.

슬롯을 생성하여 연결 리스트의 모델로 연결해나가는 방식으로 충돌 문제를 해결하는 것이 '체이닝' 방법이다.