Hash Function, Hash Table 개념
Hash Function 이란?
: 임의의 길이를 가진 데이터를 고정된 데이터의 길이로 변환시키는 함수
* 해시 함수에 의해 얻어지는 값 - 해시(해시 값, 해시 코드)
(해시는 정수형태)
특징
1. 어떤 입력 값에도 항상 고정된 길이의 해시값이 출력한다
2. 입력 값이 하나라도 변경되어도 전혀 다른 결과물이 나온다 (눈사태 효과)
3. 상대적으로 메모리자원을 덜 소모한다
종류
1. 비암호학적 해시 함수
: CRC32 등
* CRC : 파일의 에러체크할 때 사용
2. 암호학적 해시 함수
: MD5, SHA계열 등
* 해시 함수 알고리즘 종류
1) Division Method (나눗셈 법)
: 입력 값을 테이블의 크기로 나누고, 나머지를 테이블의 주소로 사용함.
* 테이블의 크기를 소수(prime Number)로 정하는 것이 좋다. (충돌 최소화)
2) Digit Folding (자릿수 접기)
: 숫자의 각 자릿수를 더해 해시값을 만듬
* 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘
응용
1. 자료구조 - Hash Table, Hash Set 등
2. Cache
3. 중복 레코드 검색, 유사 레코드 검색 등
4. 변조 탐지/에러 검출
Hash Table
: index에 해시값 을 사용하는 자료구조.
정렬을 하지 않고 빠른 검색/삽입이 가능
* 빠른 이유
: key에 대한 데이터를 찾을 때, Hash function을 한번만 수행하여 직접 접근해서 찾을 수 있기 때문에 매우 빠름
EX) Data인 k를 Hash Function에 넣어서 나온 값 h(k)를 index로 사용함.
* 검색하고자 하는 Data값을 입력받아서 해시함수를 돌려 반환받은 해시코드를 배열의 인덱스로 환산하여 사용
장점
: 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다
index에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색/삽입/삭제를 빠르게 수행 가능하다
충돌 (Collusion)
: Hash테이블의 근본적인 문제.
다른 값이 동일한 해시값을 가져 동일한 index에 저장되는 경우, 충돌 발생
다른 해시값이어도 동일한 인덱스에 배정 받는 경우, 출동 발생
* 알고리즘이 아무리 정교하게 설계되어도 모든 입력 값에 대한 고유한 해시 값을 만들지 못함.
why? 입력받는 값은 문자열로 무한한 경우의 수가 있지만, 해시코드는 정수형태로 길이가 정해져있으므로
충돌이 많아질 수록 시간 복잡도는 O(1) -> O(n)에 가까워 진다.
Hash Table에서 매우 중요한 이슈
Direct Addressing Table에 비해 공간 낭비가 적다는 장점이 있지만,
key값의 크기만큼 생성되는 것이 아니라, h(k)만큼 공간에 저장되므로
충돌을 최소화시키고 얼마나 인덱스에 골고루 분배하느냐에 따라 좋은 해시 알고리즘을 결정
충돌 해결방법
1. Open Hashing (개방 해싱)
- Chaining
2. Closed Hashing (폐쇄 해싱)
- Chaining
- Open Addressing
- Linear Probing (선형 탐사)
- Quadratic Probing (제곱 탐사)
- Double Hashing (이중 해싱)
- Rehashing (재해싱)
- Chaining (분리 연결법)
: Linked List를 이용하는 방식
index에 데이터를 저장하는 Linked list에 대한 포인터를 가지는 방식
충돌 발생시, index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가함
추가할 수 있는 데이터 수의 제약이 작다.
* JDK 1.8 경우, index에 노드가 8개 이하일 경우, Linked List를 사용
8개 이상으로 늘어날 때는, Tree 구조로 바꾸도록 되어있음
- Open addressing
: Linked List같은 추가 메모리 공간을 사용하지 않고, Hash Table array의 빈 공간을 사용하는 방법
Chaining에 비해 메모리를 덜 사용함.
* 단점 : 데이터 삭제시 비효율적
1) Linear Probing
: index에 대해 충돌이 발생했을 경우, 버킷중에 빈 버킷을 순차적으로 찾아서 데이터를 넣는 방식
2) Resizing
: 해시 버킷 개수가 적다면, 메모리를 아낄 수 있지만, 해시 충돌로 인한 성능 손실이 발생함.
그래서 데이터 개수가 일정 개수 이상으로 늘어나면, 버킷 개수를 2배로 늘림.
3) Quadratic probing
: 2차 함수를 이용하여 탐색
4) Double hashing probing
: 하나의 해시 함수에 충돌이 발생하면 2차 해시 함수를 이용해 새로운 주소를 할당
(Linear, Quadratic probing에 비해 많은 연산량을 요구함)
'Data Structure' 카테고리의 다른 글
| [Data Structure] Data Structure 개념 (0) | 2019.03.02 |
|---|