해시 테이블(Hash Table)
해시 테이블(Hash Table)이란, Key와 Value로 이루어진 데이터 쌍을 저장하는 자료구조이다.
내부적으로 배열을 사용하여 데이터를 저장하기에 빠른 검색 속도를 가진다.
(C++에서는 map, Python에서는 dictionary가 해시 테이블에 해당된다.)
해쉬 테이블에서 key, value 데이터 쌍을 저장하는 과정은 다양하며, 아래는 Division Method 방식의 해시 함수를 이용한 과정이다.
- index = hash_func(key)%table_size, 과정을 통해 index값을 계산한다.
- array[index] = value로 배열을 이용하여 value를 저장한다.
위와 같은 해싱 구조로 데이터를 저장하면 key값을 통해 value를 불러올 때
해시 함수(Hash Function)을 한 번만 수행하면 되기에, 빠르게 데이터를 조회 / 삭제 / 저장할 수 있다.
이때 해시 테이블의 시간 복잡도는 O(1)이 된다.
해싱 (Hashing)
해싱은 해시 함수를 이용하여 입력받은 key를 숫자로 변환하는 과정이다.
해싱 과정을 통해 입력받은 key값은 해시 테이블의 index로 변환되는데
이를 통해 해시 테이블의 자료에 접근할 수 있다.
해시 함수 (Hash Function)
해시 함수(Hash Function)는 임의 길이의 입력을 받아 고정된 길이의 출력값으로 반환하는 함수로
해시 테이블에선 이러한 특성을 활용하여 데이터를 검색, 저장한다.
앞서 언급한 Division Method 방식으로 C++에서 해시 함수를 구현하여 보겠다.
이때 해시 테이블의 크기는 소수로, 2의 제곱수와 먼 값으로 하면 효과가 좋다. (해시 충돌이 줄어든다)
#define MAX_TABLE 1429
int hash_F(const char* str){
int hash = 941;
while (*str != '\0'){
hash = (hash << 4) + ((int)(*str));
str++;
}
return hash%MAX_TABLE;
}
int main(){
const char* s1 = "hello";
int index1 = hash_F(s1);
const char* s2 = "world";
int index2 = hash_F(s2);
cout << "s1 -> " << index1 << endl;
cout << "s2 -> " << index2 << endl;
}
hash_F함수는 입력받은 문자열을 정수로 반환하는 간단한 예제 함수로
문자열을 반복하며 hash값을 4비트 left-shift시키고 현재 문자의 ASCII값을 더하는 구조이다.
최종적으로 해시값에 해시 테이블 크기를 %연산하여 정수를 반환한다.
-output-
s1 -> 842
s2 -> 345
해시 테이블 구현
해시 테이블을 C++코드로 최종 구현하여 보겠다. 이때 해시 함수를 통해 반환된 값이 겹칠 경우
해시충돌이 발생하는데, 해시 충돌을 방지하는 다양한 방법 중 chaining 방법으로 구현하였다.
chaining : LinkedList를 이용한 방식으로 저장하려는 해시 테이블에 같은 반환 값이 존재할 경우, 노드를 추가하여 다음 노드를 가리키는 방식
HashNode, HashBucket, HashTable
class HashNode {
private:
string key;
int value;
HashNode* nextHash;
public:
HashNode() : nextHash(nullptr) {}
HashNode(const string& k, int val) : key(k), value(val), nextHash(nullptr) {}
HashNode* getNext() { return nextHash; }
void setNext(HashNode* node) { nextHash = node; }
const string& getKey() { return key; }
int getValue() { return value; }
};
class HashBucket {
private:
int size;
HashNode* head;
public:
HashBucket() : size(0), head(nullptr) { head = new HashNode; }
~HashBucket() {
HashNode* node = head;
HashNode* next = nullptr;
while (node != nullptr) {
next = node->getNext();
delete node;
node = next;
}
}
bool isEmpty() { return size == 0; }
void push(HashNode* val) {
HashNode* next = head->getNext();
head->setNext(val);
val->setNext(next);
size++;
}
HashNode* findNode(const string& key) {
HashNode* node = head->getNext();
while (node != nullptr) {
if (key == node->getKey()) {
return node;
}
node = node->getNext();
}
return nullptr;
}
void delNode(const string& key) {
HashNode* node = head;
HashNode* prev = nullptr;
while (node != nullptr) {
if (node->getKey() == key) {
if (prev) {
prev->setNext(node->getNext());
} else {
head->setNext(node->getNext());
}
delete node;
size--;
return;
}
prev = node;
node = node->getNext();
}
}
void display() {
HashNode* node = head->getNext();
while (node != nullptr) {
cout << node->getValue() << " ";
node = node->getNext();
}
}
};
class HashTable {
private:
int bucketSize;
int size;
HashBucket* bucket;
int makeHash(const string& key) {
int hash = 401; // 소수값
for (int i = 0; i < key.length(); i++) {
hash = (hash << 4) + static_cast<int>(key[i]);
}
return hash % bucketSize;
}
public:
HashTable() : bucketSize(16), size(0) {
bucket = new HashBucket[bucketSize];
}
HashTable(int bSize) : bucketSize(bSize), size(0) {
bucket = new HashBucket[bSize];
}
~HashTable() { delete[] bucket; }
void insert(const string& key, int val) {
int hash = makeHash(key);
HashNode* overlap = bucket[hash].findNode(key); // 같은 key값 노드가 있는 지 확인
if (overlap != nullptr) {
return;
}
bucket[hash].push(new HashNode(key, val));
}
void del(const string& key) {
int hash = makeHash(key);
bucket[hash].delNode(key);
}
int find(const string& key) {
int hash = makeHash(key);
HashNode* find = bucket[hash].findNode(key);
if (find == nullptr) return -1;
return find->getValue();
}
int operator[](const string& key) {
int hash = makeHash(key);
HashNode* find = bucket[hash].findNode(key);
if (find == nullptr) {
return -1;
}
return find->getValue();
}
void display() {
for (int i = 0; i < bucketSize; i++) {
bucket[i].display();
}
cout << endl;
}
};
main
HashTable ht(10);
ht.insert("key1", 10);
ht.insert("key2", 20);
ht.insert("key3", 30);
ht.insert("key4", 40);
cout << "Hash Table: " << endl;
ht.display();
cout << "Finding key1: " << ht.find("key1") << endl;
cout << "Finding key2: " << ht.find("key2") << endl;
cout << "Finding key3: " << ht.find("key3") << endl;
cout << "Finding key5: " << ht.find("key5") << endl; // This key does not exist
ht.del("key2");
cout << "Hash Table:" << endl;
ht.display();
cout << "Finding key2: " << ht.find("key2") << endl; // 값이 없을 때
cout << ht["key3"] << endl;
return 0;
output
Hash Table:
20 30 40 10
Finding key1: 10
Finding key2: 20
Finding key3: 30
Finding key5: -1
Hash Table:
30 40 10
Finding key2: -1
30
해시 테이블은 (key, value)쌍으로 이루어진 자료구조로,
key값을 해시함수를 통해 인덱스로 변환하여 배열에 value를 저장하는 구조이다.
C++의 STL 중 map이 이에 해당한다. 다양한 해시 충돌 방지법이 있는데 그 중 chaining 방식에 대해 다루었다.
추후 다른 방식들 또한 포스팅 예정.