해싱이란

• 대부분의 탐색 방법들은 키 값 비교로써 탐색하고자 하는 항목에 접근
• 해싱(hashing): 키 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근
• 해시 테이블(hash table): 키 값의 연산에 의해 직접 접근이 가능한 구조

추상 자료형, 사전

사전구조(dictionary)

• 맵(map) 또는 테이블(table)로 불리움
• 탐색 키와 관련된 값의 2가지 필드로 구성
  • 영어 단어나 사람의 이름 같은 탐색 키(search key)
  • 단어의 정의나 주소 또는 전화 번호 같은 탐색 키와 관련된 값(value)

해싱의 구조

해시 함수(hash function)

• 탐색키를 입력받아 해시 주소(hash address) 생성
• 이 해시 주소가 배열로 구현된 해시 테이블(hash table)의 인덱스
• 해시 함수 설계 시 충돌 발생하는 경우를 주의해야 함
  → 슬롯으로 간접적으로 해결

좋은 해시 함수의 조건

• 충돌이 적어야 한다
• 해시함수 값이 해시테이블의 주소 영역 내에서 고르게 분포되어야 한다
• 계산이 빨라야 한다

제산 함수

• 나머지 연산자(mod)를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법
  $h(k) = k \bmod M$
• 해시 테이블의 크기 M은 소수(prime number) 선택

폴딩 함수

• 이동 폴딩(shift folding)과 경계 폴딩(boundary folding)
  

해시 테이블

• M개의 버킷(bucket)으로 구성된 테이블
• ht[0], ht[1], … , ht[M-1]의 원소를 가짐
• 하나의 버킷에 s개의 슬롯(slot) 가능

충돌(collision)

• 서로 다른 두 개의 탐색키 k1과 k2에 대하여 같은 해시값 주소를 가져 h(k1) = h(k2)가 되는 경우
• 충돌이 발생하면 해시 테이블에 항목 저장 불가능
• 충돌을 효과적으로 해결하는 방법 반드시 필요(선형 조사법, 체이닝)

선형 조사법

• 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
• 과정
  1. 충돌이 ht[k]에서 발생했다면, ht[k+1]이 비어 있는지 조사
  2. 만약 비어있지 않다면, ht[k+2] 조사
  3. 비어있는 공간이 나올 때까지 계속 조사
  4. 테이블의 끝에 도달하게 되면 다시 테이블의 처음부터 조사
  5. 조사를 시작했던 곳으로 다시 되돌아오게 되면 테이블이 가득 찬거임
  6. 조사되는 위치: h(k), h(k) + 1, h(k) + 2, …
• 군집화(clustering)과 결합(Coalescing) 문제 발생

체이닝

• 각 버킷에 고정된 슬롯이 할당되어 있지 않음
• 각 버킷에 삽입과 삭제가 용이한 연결 리스트 할당
• 버킷 내에서는 연결 리스트 순차 탐색

오버플로우(overflow)

• 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하는 것
• 오버블로우 해결 방법 반드시 필요

이상적인 해싱

학생 정보 저장 및 탐색

• 5자리 학번 중에 앞 2자리가 학과 번호, 뒤 3자리가 각 학과의 학생 번호
• 같은 학과 학생들만 가정하면 뒤의 3자리만 사용해서 탐색 가능
• 학번이 00023이라면 이 학생의 인적사항은 해시테이블 ht[23]에 저장
• 만약 해시테이블이 1000개의 공간을 가지고 있다면 탐색 시간이 O(1)이 되므로 이상적임

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구