Hash
해시(Hash) 란 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 과정을 말한다.
즉 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑해주는 함수이다.
- 키(key): 매핑전 원래 데이터의 값
- 해시값(Hash Value): 매핑 후 데이터의 값, 해시코드, 해시섬, 체크섬 등이라고도 한다.
- 해싱(Hashing) : 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법
해시 테이블
키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. 키를 해시 함수(hash function) 로 계산하여 그 값을 배열의 인덱스로 사용한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다. 정리하면 다음과 같다.
i. hashFunction(key) = hashcode
ii. Bucket[hashcode] = data
Example)
이름을 키(key)로 하여 학번를 저장하는 해시 테이블은 다음과 같이 만들 수 있다. 전체 데이터 양을 7이라고 하면 하영이의 데이터를 저장할 때, 배열의 인덱스는 hashFunction("하영") % 7을 통해 인덱스 값을 계산한다. 여기서는 인덱스 값은 2이다.
물론 실생활이나 암호화폐의 영역에서는 hash function이 더욱 더 복잡하고 hashcode는 더 길다.
위는 이더리움 블록체인 거래내역 증명서이다. 거래값이 해시함수로 처리되어 해시코드가 보인다.
해쉬 충돌 (Hash collision)
비둘기 집 원리
: n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리
증명) n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정한다. 만약 각 비둘기집에 한 마리 이하의 비둘기만 들어 있다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 존재한다. 그런데 비둘기는 모두 n+1마리이므로, 이것은 모순이다. 따라서 어느 비둘기집에는 두 마리 이상의 비둘기가 있다.
해시 함수는 보통 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력이 다름에도 불구하고 드물게 동일한 값이 출력되는 경우도 존재한다. 이러한 경우를 충돌한다고 한다. (비둘기집 원리)
해시 함수에서 충돌은 여러가지 문제를 야기한다. 일단 충돌이 발생하면 다른 Key 값인데 같은 해시코드가 발생한다. 예를 들어 나중에 입력된 "세원" 이란 이름을 해시 함수에 넣었더니 2번 인덱스로 나온다면 "하영"과 동일한 인덱스을 가지게 되는 문제가 발생한다. 또 충돌이 많아질 수록 탐색의 시간 복잡도가 O(1)에서 O(n)에 가까워지기 때문이다.
보통 두 가지 방법으로 충돌을 처리한다.
1. 개별 체이닝(Separate Chaining)
Separating Chaining - Linked List, Tree(Red-Black Tree)
이 방법은 JDK내부에서도 사용하고 있는 충돌 처리 방식인데, Linked List를 이용하는 방식이다. Linked List뿐만이 아니라 Tree(Red-Black Tree)를 사용하기도 한다.
두 개를 사용하는 기준은 data가 6개 이하이면 linked list를 사용하고 8개 이상이면 tree를 사용한다.
충돌 발생 시 그림과 같이 연결 리스트로 연결(link)하는 방식이다. 충돌이 발생한 지은과 영주는 지은의 다음 아이템이 영주인 형태로 서로 연결 리스트로 연결되었다. 이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로, 개별 체이닝 방식은 인기가 높다. 원래 해시 테이블 구조의 원형이기도 하며 가장 전통적인 방식으로, 흔히 해시 테이블이라고 하면 바로 이 방식을 말한다
2. 오픈 어드레싱(Open Addressing)
Open addressing - Linear Probing, Quadratic Probing, Double hashing
충돌 발생 시 그림과 같이 탐사를 통해 빈 공간을 찾아나서는 방식이다. 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다.
충돌이 일어나면 테이블 공간 내에서 탐사(Probing)를 통해 빈 공간을 찾아 해결하며, 이 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.
그림은 가장 간단한 방식인 선형 탐사(Linear Probing) 방식이며 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되어 있으면 바로 그 다음 위치를 확인하는 식이다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 된다. 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입한다.
그림에서도 지은 다음에 영주의 해시값이 동일한 2로 충돌이 발생했고, 다음번 빈 위치를 탐색하며 그 다음 비어있는 위치인 3에 영주가 들어가게 된다. 이처럼 선형 탐사 방식은 구현 방법이 간단하면서도, 의외로 전체적인 성능이 좋은 편이기도 하다.
3. 그래도 안되면... resize
이렇게 충돌 해결을 한다고 해도 결과적으로 충돌로 인한 성능 저하는 막을 수 없다. 그림과 같이 수용률이 일정량을 넘어서게 되면 저장/조회 성능이 모두 점점 떨어지며 그래서 수용률이 일정량을 넘어가게 되는 경우에는 아예 리스트 자체의 크기를 키운 뒤에 재배열을 하는 방법을 사용한다.
다만, 이 과정 자체가 상당히 비용이 많이 드는 과정이라서 실시간으로 빠르게 처리해야되는 환경에서는 무리가 있을 수 있다.
Consistent hashing
또는 해시의 비트수를 늘이는 방법도 있다. 항목 수가 적을 때에는 짧은(적은 비트 수) 해시와 작은 저장공간를 사용하다가 충돌이 잦아지면 비트수를 1비트 늘이고 저장공간도 2배로 늘인다. 그리고 항목을 점진적으로 확장된 공간으로 이전하게 함으로써 충돌을 줄일 수 있다. 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 사용되고 있다.
- Separate changing: 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에, 검색 성능이 떨어지기 때문에 버킷의 개수를 늘려줘야 한다.
- Open addressing: 고정 크기 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해야 한다.
해시의 장단점
장점
- 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
- 예) HDD, Cloud에 존재하는 많은 데이터들을 유한한 개의 해시(Hash)값으로 매핑하여 작은 크기의 캐쉬 메모리로 프로세스 관리가 가능하다.
- 배열의 인덱스(index)를 사용해서 검색, 삽입, 삭제가 빠르다. (평균 시간복잡도 : O(1))
- 인덱스를 사용해서 배열의 검색이 빠르다
- 여기서의 인덱스는 데이터만의 고유한 위치이기 때문에 만약 삽입이나 삭제를 한다고 해도 다른 데이터로 채울 필요가 없다. 즉, 삽입이나 삭제할 때 데이터를 이동할 필요가 없기 때문이다.
- 키(key)와 해시값(Hash)이 연관성이 없어 보안에도 많이 사용된다.
- 데이터 캐싱(Data Caching)에 많이 사용된다.
- get(key), put(key)에 캐시 로직을 추가하면 자주 hit하는 데이터를 바로 찾을 수 있다.
- 중복을 제거하는데 유용하다.
단점
- 충돌
- 공간 복잡도가 커진다.
- 순서가 있는 배열에는 어울리지 않는다.
- 해시 함수 의존도가 높아진다.
해시 테이블(Hash Table) VS 해시 맵(Hash Map)
Java에서 HashTable과 HashMap의 차이는 동기화 지원 여부이다. 키(Key)에 대한 해시(Hash)값을 사용하여 값을 저장, 조회 하는 것은 동일하다.
- 해시 테이블(Hash Table)
- 병렬 처리를 할 때 (동기화를 고려해야하는 상황)
- Null 값을 허용하지 않는다.
- 해시 맵(Hash Map)
- 병렬 처리를 하지 않을 때 (동기화를 고려하지 않는 상황)
- Null 값을 허용한다.
C++에서는 동일한 것으로 보아도 무방하다.
해시 테이블의 성능
키값이 배열의 인덱스로 변환되기 때문에 탐색,저장,삭제가 빠르다. 평균 시간 복잡도가 O(1)이다.
- 평균 시작 복잡도인 이유는 collision 때문이다.
| 평균적인 경우 | 최악의 경우 | |
|---|---|---|
| 탐색 | O(1) | O(N) |
| 삽입 | O(1) | O(N) |
| 삭제 | O(1) | O(N) |
언어별 자료구조
| 언어 | 방식 |
|---|---|
| C++(GCC libstdc++) | 개별 체이닝 |
| 자바 | 개별 체이닝 |
| 고(Go) | 개별 체이닝 |
| 루비 | 오픈 어드레싱 |
| 파이썬 | 오픈 어드레싱 |
예제코드
헤더파일
#include <iostream>
#include <string>
typedef struct hashItems* pHashItems;
typedef struct hashItems {
std::string key;
std::string value;
pHashItems nextHashItem;
int isEmpty;
}hashItems;
int table_size;
hashItems hashTable1[100];
hashItems hashTable2[100];
hashItems newHashItem (std::string key, std::string value) {
hashItems item;
item.key = key;
item.value = value;
item.isEmpty = 1;
item.nextHashItem = NULL;
return item;
}
int getHashCode(std::string key) {
int hashCode = 0;
for (int i = 0; i < key.length(); i++)
hashCode += key[i];
return hashCode;
}
int convertToIndex(int key) {
return key % table_size;
}
체이닝 해시테이블
void chaining_put(std::string key, std::string value) {
int hashCode = getHashCode(key);
int hashArrayIndex = convertToIndex(hashCode);
hashItems item = newHashItem(key, value);
if (hashTable1[hashArrayIndex].isEmpty == 0) {
//hash table의 슬롯이 비어 있으면 바로 삽입
hashTable1[hashArrayIndex] = item;
std::cout << "hashTable[" << hashArrayIndex << "] " << "\n";
std::cout << " - key: " << hashTable1[hashArrayIndex].key << "\n";
std::cout << " - value: " << hashTable1[hashArrayIndex].value << "\n\n";
}
else {
//hash table의 슬롯이 비어있지 않으면
std::cout << "hashTable[" << hashArrayIndex << "], " << key << "에서 해시충돌 발생!" << "\n";
//hash table 슬롯에 저장된 첫번째 데이터를 가져온다.
hashItems hashItem = hashTable1[hashArrayIndex];
// 연결리스트 마지막까지 탐색을 수행하고 삽입.
while (hashItem.nextHashItem != NULL) {
std::cout << " ?";
hashItem = *(hashItem.nextHashItem);
}
hashItem.nextHashItem = &item;
std::cout << "hashTable[" << hashArrayIndex << "]의 연결리스트 뒤에 연결되었습니다." << "\n\n";
}
}
std::string chaining_get(std::string key) {
int hashCode = getHashCode(key);
int hashArrayIndex = convertToIndex(hashCode);
if (hashTable1[hashArrayIndex].isEmpty == 0) return "not found";
hashItems hashItem = hashTable1[hashArrayIndex];
while (hashItem.isEmpty != 1 && hashItem.key != key) {
hashItem = *(hashItem.nextHashItem);
}
if (hashItem.isEmpty == 0) return "not found";
else return hashItem.value;
}
오프닝 어드레스
void openadd_put(int key, int value) {
//충돌을 발생하기 위해서 key값을 hashcode로 바로 사용
//key값이 1, 11, 21 ..이 들어오면 충돌 발생
int hashArrayIndex = convertToIndex(key);
std::cout << "chaining_put() method called with value : " + value << ", hashArrayIndex : " + hashArrayIndex << "\n";
//충돌이 없을 때까지 반복 수행
while (hashTable2[hashArrayIndex].isEmpty != 0) {
//인덱스 1 씩 증가
hashArrayIndex = (hashArrayIndex + 1) % table_size;
std::cout << "collision -> move to next index : " + hashArrayIndex << "\n";
}
std::cout << "Inserted finally with index : " + hashArrayIndex << "\n";
hashTable2[hashArrayIndex] = newHashItem(std::to_string(key), std::to_string(value));
}
int openadd_get(int key) {
int hashArrayIndex = convertToIndex(key);
while (hashTable2[hashArrayIndex].isEmpty != 0 && hashTable2[hashArrayIndex].key != std::to_string(key)) {
hashArrayIndex = (hashArrayIndex + 1) % table_size;
std::cout << "not matched, move to next index : " + hashArrayIndex << "\n";
}
if (hashTable2[hashArrayIndex].isEmpty == 0) return -1;
else return std::stoi(hashTable2[hashArrayIndex].value);
}
메인 함수
#include <iostream>
#include <string>
int main() {
std::cin >> table_size;
std::cout << "----------------Chaining HashTable-------------------" << "\n";
chaining_put("key1", "a");
chaining_put("key2", "ab");
chaining_put("key3", "abc");
chaining_put("key4", "abcd");
chaining_put("key5", "abcde");
chaining_put("key6", "abcde");
chaining_put("key7", "abcde");
chaining_put("key8", "abcde");
chaining_put("key9", "abcde");
chaining_put("key10", "abcde");
chaining_put("key11", "abcde");
chaining_put("key12", "abcde");
chaining_put("key13", "abcde");
std::cout << "key1의 value : " + chaining_get("key1") << "\n";
std::cout << "key6의 value : " + chaining_get("key6") << "\n";
std::cout << "--------------Linear Probing HashTable-----------------" << "\n";
openadd_put(1,10);
openadd_put(2,20);
openadd_put(11,100); //충돌 발생
std::cout << "key1의 value : " + openadd_get(1) << "\n";
std::cout << "key2의 value : " + openadd_get(2) << "\n";
return 0;
}
'CS study > [core] 데이터 구조' 카테고리의 다른 글
| 16. 그래프 탐색 (2) - DFS (0) | 2021.07.20 |
|---|---|
| 15. 그래프 탐색 (1) - BFS (0) | 2021.07.20 |
| 14. Graph Basics (0) | 2021.07.10 |
| 11. AVL tree (0) | 2021.07.10 |
| 10. Heapsort (0) | 2021.07.09 |