14.1. 해싱이란?

• 해싱은, 이상적으로 O(1)의 시간 안에 탐색을 끝마칠 수도 있는 알고리즘이다.
• 해싱은 키(KEY)에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(Table)이라고 한다.
• 또한, 해시 테이블을 이용한 탐색을 해싱(hashing)이라고 한다.
• 해싱은 보통 사전(dictionary)이라는 자료구조를 구현할 때에 최상의 선택이 된다.

14.2. 추상 자료형 사전

사전의 개념

• 사전은 (키, 값) 쌍의 집합이다. 사전은 맵이나 테이블로 불리기도 한다.
• 예를 들어 영어 사전의 경우, 영어 단어가 키가 되고 단어의 설명이 값이 된다.
  • 항목들을 접근하고 삭제하려면 키만 가지고 있으면 된다!
• 리스트와 다른 점은, 리스트는 근본적으로 위치에 의하여 관리되는 자료구조 이지만, 사전은 오직 키에 의해서만 관리된다는 점이다.

14.3. 해싱의 구조

• 현실적으로, 탐색 키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있으므로 각 탐색 키를 작은 정수로 사상(mapping)시키는 어떤 함수가 필요하다.
• 해싱에서는 자료를 저장하는데 배열을 사용한다.
  • 배열은, 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다.
  • 해싱이란, 이런식으로 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는 기법이다.
• 해시 함수(hash function)이란, 키를 입력으로 받아 해시 주소를 생성하고 이 해시 주소를 해시 테이블의인덱스로 사용하는 것을 말한다.
• 해시 함수의 경우, 키가 같으면 충돌이 생길 수 있는데, 이처럼 서로 다른 두 개의 키 k1, k2에 대해서 h(k1) = h(k2)인 경우를 충돌 이라고 한다. 또한, 이런 경우 키 k1, k2를 동의어 라고 한다.
• 충돌이 자주 발생하면 버킷 내부에서 순차 탐색 시간이 길어져서 탐색 성능이 저하될 수 있으므로 해시 함수를 수정하거나 해시 테이블의 크기를 적절하게 조절해줘야 한다.

이상적인 해싱

• 이상적인 해싱 알고리즘은 다음과 같다.

add(key, value) :
	index <- hash_function(key)
	ht[index] = value

search() : 
	index <- hash_function(key)
	return ht[index]