해시 테이블

 

 

 

사진출처 : 링크(위키)

Hash table - Wikipedia

 

해시 테이블(Hash Table)

 

해시테이블이란 키를 입력 값으로 해시 함수(hash function)을 사용하여 변환한 해시(hash)값을 색인(index)으로 키(key)오ㅓ 데이터(data)를 저장하는 자료구조다. 

 

해시테이블이란 핸드폰 단축번호와 같다 위에서 본 이미지와 같이 1번을 누르면 521-8976번호로 전화가 되듯이 작동한다. 

이와 같이 필요한 데이터의 키(key)는 해시함수를 사용해 별도의 해시(hash)로 바꿔 주고, 해당하는 데이터(value)를 함께 저장하는 자료구조다. 

 

 

해시 테이블의 구조 

해시 테이블은 키(key)와 해시함수(hash function), 해시(hash), 데이터(value)로 이루어져있다.

 

키(key) : 고유한 값으로 해시 함수의 입력값이 된다. 
해시함수(hash function): 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 

충돌(hash collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요함

해시(hash): 해시 함수(hash function)를 사용하여 만들어진 결과물로, 저장소에서 데이터(valu)와 매칭되어 저장되고 변환된 값을 색인(index)와 같이 사용함

데이터(value) :  저장소에 최종적으로 저장되는 값으로 색인(index)와 매칭되어 저장됨

 

 

 

해시 테이블의 특징

 

1. 해시 테이블에서 저장, 삭제, 검색과정은 모두 평균적으로 O(1)의 시간복잡도를 가짐

2. 해시충돌이 발생할 수 있음

3. 데이터가 저장되기 전에 저장공간을 미리 만들어야 해서 공간 효율성이 떨어짐

4. 해시함수(hash function)의 의존도가 높음

5. 해시함수(hash function)이 복잡하다면, 해시(hash)값을 만들어내는 데 많은 시간이 소요됨

 

 

 

1. 저장, 삭제, 검색 과정

 

해시테이블에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수(hash function)에 키(key)값을 넣어 해시(hash) 값을 만들게 됩니다. 이후 만들어진 해시(hash)값과 일치하는 색인(index)를 찾아 저장하거나 삭제, 검색해야함 이럴 경우 기본적인 시간 복잡도는 O(1)입니다.

 

그러나 해싱 충돌이 발생할 경우 저장소의 모든 색인(index)(삽입)  혹은 데이터(value)(삭제, 검색)을 찾아봐야 하므로  O(n)이 된다. 

 

 

2. 대표적인 해시 알고리즘

1. Division Method : Number type의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인(index)로 사용하는 방법

이 때 저장소의 크기를 Prime Number로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋음

 

2. Digit Folding : 키(key)의 문자열을 Ascii 코드로 바꾸고 그 값을 합해 저장소에서 색인(index)로 사용하는 방법 만약 색인(index)이 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있음

 

3. Multiplication Method : 숫자로 된 Key 값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 M을 사용하여 다음과 같이 계산함

index = (KA mode 1)m

 

4. Universal Hashing : 다수의 해시함수를 만들어 특정한 장소에 넣어두고 무작위로 해시함수를 선택해 해시(hash)값을 만드는 기법

 

 

 

3. 해시 충돌을 해결하는 방법

 

서로 다른 두 값이 동일한 키값을 가지는 경우를 "해시 충돌"이라고 함

 

개방 연결법 

 

Linear Problng(선형 탐사법) : 말 그대로 선형적으로 순차적 검색을 하는 방법, 해당 해시값에서 고정 폭을 옮겨 다음 해시값에 해당하는 버킷에 엑세스함, 이 경우 특정해시값의 주변이 모두 채워져있는 일차 군집화 문제에 취약함 

 

Quadratic Probing(제곱 타사법) : 선형탐사법과 동일한데, 고정폭이 아니라 제곱으로 늘어난다. 

 

Double Hashing Probing(이중 해싱) : 탐사할 해시값의 규칙값을 없애서 클러스터링을 방지한다. 

 

 

분리 연결법

개방주소와는 달리 한 버킷(슬롯)당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다. 이 때 버킷에는 링크드 리스트(linked list)나 트리(tree)를 사용함