자료구조: ch6) 해시 테이블 (Hash table)

Ji·2021년 2월 25일

자료구조

해시 테이블?

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. (https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94)
해시 함수를 사용하여 키를 해시값으로 매핑 후 해시 값을 index 혹은 주소로 삼아 데이터의 값(value)를 키와 함께 저장하는 자료 구조.
매우 빠른 삽입, 삭제, 탐색연산 제공
key와 value는 항상 한 쌍으로 저장된다!

해시 테이블의 구성요소

해시 테이블은 키(key), 해시 함수(Hash function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어진다.
해시함수: 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑(mapping)하는 함수이다. 다양한 길이의 key를 일정 길이를 갖는 hash 로 변경한다. 따라서 저장소의 효율적 운영이 가능하게 할 수 있다.
키: 매핑 전 원래의 데이터 값이자 해시 함수의 input 값. 고유 값이며 다양한 길이의 값이 될 수 있다. 해시함수로 값을 바꾸어 저장이 되어야 공간의 효율적 운영이 가능하다.
해시 값: 매핑 후 데이터의 값. 해시 함수의 output. 저장소(Bucket)에서 값(value)과 매칭돼 저장된다.
값(Value): 저장소(Bucket)에 최종 저장되는 값. 키와 매칭돼 저장,삭제,검색,접근이 가능하다.
해싱: 매핑하는 전체 과정

해시 함수의 알고리즘

1. Division Method(나눗셈 법)
  입력 값을 테이블의 크기로 나누고, 그 '나머지'를 테이블 주소로 활용
  주소=입력 값 % 테이블 크기 (테이블 크기 n을 소수로 정하는 것이 좋음)
  f(k)=(k%p)%m (p: prime number, m:해시 테이블의 크기)
1. Digit Folding (자릿 수 접기)
  숫자의 각 자릿수를 더해 해시 값을 만드는 방법
  문자열을 키로 사용하는 해시 테이블에 유용하게 사용된다. 문자열의 각 요소를 아스키 코드 번호로 바꾸고, 이 값을 각각 더하여 주소로 변환해 사용한다.

이외에도 다양한 종류의 해시 함수의 알고리즘이 존재.

좋은 해시 함수의 조건

less collision
fast computation

해시 함수의 문제점

해시 충돌 (Hash Collision): 서로 다른 입력 값에 대해 동일한 해시 값을 반환하는 것. 즉 해시 테이블 내의 동일한 주소를 반환한다.
클러스터(Cluster): 일부 지역 주소들을 집중적으로 반환하는 결과, 데이터들이 한 곳에 모이게 되는 문제가 발생한다. 클러스터를 피하게 저장소를 운영하는 것이 이상적이다.

해시 충돌의 해결법 (Collision resolution)

Open Hashing(개방 해싱): 주소 밖에 새로운 공간을 할당해 문제를 해결
-Chaining(체이닝): 개방해싱+폐쇄해싱 특징을 동시에 갖는다. 충돌이 발생하면 각 데이터를 해당 주소의 링크드 리스트에 삽입하여 문제 해결.
Closed Hashing(폐쇄 해싱): 처음 주어진 해시테이블 공간 안에서 문제 해결
-Chaining
-Open Addressing(개방 주소법): 충돌이 일어나면 해시 테이블 내 새로운 주소를 탐사한다. 탐사 후, 충돌된 데이터를 입력. chaining과 대비되는 방법

<open addressing 종류>

(1) Linear Probing(선형 탐사): 저장소에 이미 데이터가 저장된 경우, 현재 주소에서 고정폭으로 다음 빈 주소로 이동.
(2) Quadratic Probing(제곱 탐사): 선형탐사보다 이동폭이 제곱수로 늘어남.
(3) Double Hashing(이중 해싱): 클러스터 방지 위해 2개 해시 함수 준비. 하나는 최초의 주소 위해, 다른 하나는 충돌이 일어날 경우의 주소.
(4) Rehashing(재해싱): 해시 테이블 크기 늘리고, 그 크기에 맞추어 테이블 내 모든 데이터를 다시 해싱.