티스토리 뷰
해시 테이블
모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 O(N)의 매우 많은 시간이 소요되고 비효율적이다.
BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하더라도 O(logN)이라는 시간이 소요되고 검색 횟수가 크게 증가할 경우 이 정도 연산도 만족스럽지 않다.
위 경우보다 더욱 효율적인 방법은 해시 테이블을 이용하는 것이다.
해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업이다.
이때 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해시 함수라고 한다.
가장 간단한 구조의 해시 테이블 : 충돌 문제 발생
가장 간단한 해시 함수는 큰 범위의 정수를 인자로 받아 정해진 정수(n)으로 나눈 나머지를 반환하는 모듈로 함수이다.
인풋이 x라면 (x % n) 연산의 결과가 반환되고, x를 arr[x % n]에 삽입하면 된다.
이럴 경우 충돌의 문제가 발생할 수 있다. 충돌이란 해시 함수가 서로 다른 키값에 대해 같은 값을 반환함으로써 다수의 키가 같은 값을 갖게 되는 현상이다.
- 람다 함수 사용에 주목
[&] 람다 표현식은 바디 안에서 사용할 수 있는 모든 데이터(지역 변수 & 전역 변수)들을 참조로 얻어 사용한다. 참조로 가져온 캡처된 레퍼런스는 수정이 가능할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
class hash_map {
using uint = unsigned int;
vector<int> data;
public:
hash_map(size_t n) {
data = vector<int>(n, -1);
}
void insert(int val) {
int n = data.size();
data[val % n] = val;
cout << val << " 삽입!" << endl;
}
bool find(uint val) {
int n = data.size();
return data[val % n] == val;
}
void erase(uint val) {
int n = data.size();
if (data[val % n] == val) {
data[val % n] = -1;
cout << val << " 삭제!" << endl;
}
}
};
void hs_1() {
hash_map hs(10);
auto print = [&](int value) {
if (hs.find(value)) cout << "해시 맵에서 " << value << " 찾음!" << endl;
else cout << "해시 맵에서 " << value << " 찾지 못함!" << endl;
cout << endl;
};
for (int i = 0; i < 10; i++) hs.insert(i);
print(5);
hs.erase(8);
print(8);
}
체이닝
위 코드에서는 특정 해시 값 위치에 이미 원소가 존재한다면 이전 값을 버려야 하는 문제가 있다.
체이닝은 해시 테이블의 특정 위치에 하나의 키를 저장하는 것이 아닌 하나의 연결 리스트를 저장한다.
그러므로 새로 삽입된 키에 의해 충돌이 발생하면 연결 리스트 맨 뒤에 새로운 키를 추가하는 방식으로 키를 저장한다.
벡터 대신 연결 리스트를 사용하는 이유는 특정 위치의 원소를 빠르게 삭제하기 위함이다.
- find() 함수와 erase() 함수에서 각각 참조 변수와 포인터 변수로 초기화된 entries 주목
- algorithm 헤더 파일의 함수: std::find, std::for_each 사용에 주목
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
class hash_chaining {
private:
vector<list<int>> data;
using uint = unsigned int;
public:
hash_chaining(size_t n) {
data = vector<list<int>>(n);
}
void insert(uint val) {
int n = data.size();
data[val % n].push_back(val);
cout << val << " 삽입!" << endl;
}
bool find(uint val) {
int n = data.size();
list<int>* entries = &data[val & n];
return std::find(entries->begin(), entries->end(), val) != entries->end();
}
void erase(uint val) {
int n = data.size();
list<int>& entries = data[val % n];
auto it = std::find(entries.begin(), entries.end(), val);
if (it != entries.end()) {
entries.erase(it);
cout << val << " 삭제!" << endl;
}
}
void prt_all() {
cout << "Index: ";
for (int i = 0; i < data.size(); i++) cout << i << " ";
cout << endl;
for (int i = 0; i < data.size(); i++) {
cout << i << "번째: ";
for_each(data[i].begin(), data[i].end(), [](int val) {
cout << val << " ";
});
cout << endl;
}
}
};
void hs_2() {
hash_chaining hc(10);
for (int i = 0; i < 10; i++) hc.insert(i);
hc.prt_all();
for (int i = 9; i > 6; i--) hc.erase(i);
hc.prt_all();
}
부하율
체이닝 방식에서 삽입 함수의 시간 복잡도는 O(1)이다.
다만 룩업과 삭제는 데이터 크기와 해시 테이블 크기에 따라 상당히 느릴 수 있다.
예를 들어 모든 키가 같은 해시 값을 가질 경우, 룩업 연산은 연결 리스트에서 선형 검색을 수행하는 것과 같으므로 O(N)의 시간 복잡도를 갖는다.
만약 해시 테이블이 저장할 키 개수에 비해 매우 작다면 충돌이 많아지고, 리스트는 평균적으로 길어진다.
반면 너무 큰 해시 테이블을 가지고 있다면 메모리 낭비가 발생한다.
부하율은 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 나타내며 (전체 키 개수 / 해시 테이블 크기)로 구할 수 있다. 만약 키 개수가 해시 테이블 크기와 같다면 부하율은 1이고, 모든 연산이 O(1)에 가깝게 동작하는 이상적인 형태의 해시 테이블이다.
또한 해시 함수를 수정하여 부하율이 1에 가까운 값이 되도록 만드는 것을 재해싱이라고 한다.
버킷 (해시 테이블의 한 셀에 연결되어 있는 하나의 연결 리스트)
부하율이 해시 테이블의 성능을 결정하는 유일한 지표는 아니다.
만약 크기가 7인 해시 테이블에 7개의 원소가 저장되어 있을 경우 부하율은 1로 매우 이상적이지만,
모든 원소가 같은 해시 값을 가져서 하나의 버킷에 있는 경우 검색 연산은 O(N)의 시간 복잡도를 갖는다.
기본적으로 버킷의 최대 크기와 최소 크기의 차이가 너무 크면 성능이 좋지 않다.
위와 같은 경우의 버킷의 크기 차이는 7이 된다.
열린 주소 지정
선형 탐색법과 이차 함수 탐색법
체이닝 외에 충돌을 해결하는 방법으로 열린 주소 지정 방법이 있다.
열린 주소 지정 방법의 핵심은 특정 해시 값에 해당하는 위치에 이미 원소가 있다면 테이블의 다른 비어 있는 위치를 탐색하는 것이다. 따라서 해시 테이블의 크기가 반드시 데이터의 개수보다 커야 한다.
열린 주소 지정 방법에서 충돌이 발생했을 때 다른 비어있는 셀을 탐색하는 방법으로는 선형 탐색과 이차함수 탐색이 있다.
선형 탐색은 말그대로 바로 다음 인덱스(다음 셀)이 비어 있는지 확인하는 작업을 말하는데, 데이터가 특정 위치에 군집화(clustering)되는 경우 성능이 느려지는 단점이 있다.
이러한 군집화 문제를 해결하기 위해 이차함수 탐색법을 사용할 수 있다.
예를 들어 x를 hash(x) 위치에 삽입하려 할 때, x 위치가 이미 사용중이라면 hash(x + 1^2) -> hash(x + 2^2) 순으로 빈 셀이 나올 때까지 이동시키는 방식이다.
이처럼 이동 폭을 이차함수 형태로 증가시키면 데이터 군집이 나타날 확률은 상대적으로 줄어들게 된다.
뻐꾸기 해싱
뻐꾸기 해싱은 모든 연산에 대해 O(1)을 만족하는 완벽한 해싱 기법 중 하나이다.
크기가 같은 두개의 해시 테이블과, 각각 다른 해시 함수를 가지는 구조로 되어있는데, 방식은 다음과 같다.
- 첫번째 해시 테이블에서 A를 삽입할 위치를 첫번째 해시 테이블의 해시 함수를 통해 얻어낸다.
- 그 위치가 비어있으면 그대로 삽입하고, 해당 자리에 다른 원소 B가 이미 존재하면 B를 두번째 해시 테이블로 옮기고 A를 그 자리에 삽입한다.
- 만약 B가 이동할 위치에 다른 원소 C가 존재하면, 해당 위치에 B를 저장하고 C를 첫번째 해시 테이블로 옮긴다.
- 위 작업을 완전히 비어 있는 셀이 나타날 때까지 재귀적으로 반복한다.
위 과정에서 만약 순환(Cycle)이 발생한다면 무한 루프에 빠질 수 있다.
순환이 발생했다면 새로운 해시 함수를 이용하여 재해싱을 수행해야 한다.
뻐꾸기 해싱에서는 적절한 해시 함수만 제대로 사용한다면 높은 확률로 O(1)의 성능을 갖는 해시 테이블을 구성할 수 있다.
뻐꾸기 해싱에서 높은 성능을 보장하려면 부하율이 0.5보다 작게끔 설정해야 한다. 즉, 전체 원소 개수가 해시 테이블 크기의 절반보다 작아야 한다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class cuckoo_hashing {
vector<int> data1;
vector<int> data2;
int size;
// 삽입은 재귀적으로 동작해야 하기 떄문에 실제 삽입 구현 함수를 따로 만든다.
// 재귀 호출 횟수가 해시 테이블 크기보다 커진다면 순환으로 간주한다.
void insert_impl(int key, int cnt, int table) {
if (cnt >= size) {
cout << key << " 삽입 시 순환 발생!\n";
cout << "재해싱이 필요합니다.." << endl;
return;
}
if (table == 1) {
int hash = hash1(key);
if (data1[hash] == -1) {
cout << table << "번 테이블에 " << key << " 삽입" << endl;
data1[hash] = key;
}
else {
int old = data1[hash];
data1[hash] = key;
cout << table << "번 테이블에 " << key << " 삽입: ";
cout << "기존의 " << old << " 이동 -> ";
insert_impl(old, cnt + 1, 2);
}
}
else {
int hash = hash2(key);
if (data2[hash] == -1) {
cout << table << "번 테이블에 " << key << " 삽입" << endl;
data2[hash] = key;
}
else {
int old = data2[hash];
data2[hash] = key;
cout << table << "번 테이블에 " << key << " 삽입: ";
cout << "기존의 " << old << " 이동 -> ";
insert_impl(old, cnt + 1, 1);
}
}
}
public:
cuckoo_hashing(int n) : size(n)
{
data1 = vector<int>(size, -1);
data2 = vector<int>(size, -1);
}
// 두개의 해시 함수
int hash1(int key) const {
return key % size;
}
int hash2(int key) const {
return (key / size) % size;
}
// 룩업
vector<int>::iterator lookup(int key) {
int hash_value1 = hash1(key);
if (data1[hash_value1] == key) {
cout << "1번 테이블에서 " << key << " 발견!" << endl;
return data1.begin() + hash_value1;
}
int hash_value2 = hash2(key);
if (data2[hash_value2] == key) {
cout << "2번 테이블에서 " << key << " 발견!" << endl;
return data2.begin() + hash_value2;
}
return data2.end();
}
// 삭제
// lookup()은 양쪽 해시 테이블에서 key를 찾지 못하는 경우 data2.end()를 반환한다.
void erase(int key) {
auto pos = lookup(key);
if (pos != data2.end()) {
*pos = -1;
cout << key << " 삭제!" << endl;
}
else cout << key << " 발견하지 못함!" << endl;
}
// 삽입
void insert(int key) {
insert_impl(key, 0, 1);
}
void prt_all() {
cout << "Index: ";
for (int i = 0; i < size; i++) cout << i << '\t';
cout << endl;
cout << "Data1: ";
for_each(data1.begin(), data1.end(), [](int val) {
cout << val << '\t';
});
cout << endl;
cout << "Data2: ";
for (auto it = data2.begin(); it != data2.end(); it++)
cout << *it << '\t';
cout << endl;
}
};
void cuckoo_hashing_ex() {
cuckoo_hashing map(7);
map.prt_all();
cout << endl;
map.insert(10);
map.insert(20);
map.insert(30);
cout << endl;
map.insert(104);
map.insert(2);
map.insert(70);
map.insert(9);
map.insert(90);
map.insert(2);
map.insert(7);
cout << endl;
map.prt_all();
cout << endl;
map.insert(14); // 순환 발생
}
'Algorithm' 카테고리의 다른 글
| 04 - 1. 분할 정복 (Divide -and-Conquer) (0) | 2022.07.02 |
|---|---|
| 03 - 2. STL 해시 테이블과 블룸 필터 (0) | 2022.06.30 |
| 02 - 3. Graph (Adjacency Matrix, Adjacency List) (0) | 2022.06.24 |
| 02 - 2. 다양한 트리 구조 (BST, 균형 트리, N항 트리, Heap) (0) | 2022.06.24 |
| 02 - 1. 트리, 순회 (0) | 2022.06.23 |