해싱(Hashing)이란?
해싱은 길이에 상관없는 데이터 요소를 고정된 크기의 키로 매핑하는 기법으로, 키-값(key-value) 쌍의 형태로 동작합니다.
해시 함수(hash function)는 해시 맵에서 실제 매핑 작업을 수행하는 함수입니다. 그런데 서로 다른 데이터 요소가 해시 함수에 입력될 때 동일한 해시 키를 가질 수 있으며, 이 경우 요소들이 서로 겹치는 충돌(collision) 문제가 발생합니다. 이러한 충돌을 방지하기 위해 등장한 개념이 바로 체이닝(chaining)입니다.
해시맵 생성하기
해시맵을 만들기 위해서는 각 데이터 요소의 인덱스 값을 결정해 주는 해시 함수가 필요합니다.
n개의 버킷(bucket)을 가진 해시 테이블이 있다고 가정하고, 해시 테이블에 노드를 삽입하기 위한 해시 함수는 다음과 같습니다.
hashIndex = key % noOfBuckets
이제 이 해시 함수를 사용하여 해시맵에 삽입되는 모든 값의 해시 인덱스를 계산합니다.
삽입(Insert): 주어진 키 값의 해시 인덱스를 계산한 뒤, 해당 인덱스의 연결 리스트 끝에 새 노드를 추가합니다.
삭제(Delete): 해시 인덱스를 계산한 후, 해당 인덱스에 대응하는 버킷 안에서 요소를 검색하여 찾으면 제거합니다.
C++ 구현 예제
#include<iostream>
#include <list>
using namespace std;
class Hash{
int BUCKET;
list<int> *table;
public:
Hash(int V);
void insertItem(int x);
void deleteItem(int key);
int hashFunction(int x){
return (x % BUCKET);
}
void displayHash();
};
Hash::Hash(int b){
this->BUCKET = b;
table = new list<int>[BUCKET];
}
void Hash::insertItem(int key){
int index = hashFunction(key);
table[index].push_back(key);
}
void Hash::deleteItem(int key){
int index = hashFunction(key);
list<int>::iterator i;
for (i = table[index].begin(); i != table[index].end(); i++){
if (*i == key)
break;
}
if (i != table[index].end())
table[index].erase(i);
}
void Hash::displayHash(){
for (int i = 0; i < BUCKET; i++){
cout << i;
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
int main(){
int a[] = { 5, 12, 67, 9, 16 };
int n = 5;
Hash h(7);
for (int i = 0; i < n; i++)
h.insertItem(a[i]);
h.deleteItem(12);
h.displayHash();
return 0;
}
실행 결과
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6
위 예제는 크기가 7인 해시 테이블에 {5, 12, 67, 9, 16}을 차례로 삽입한 뒤 값 12를 삭제한 결과입니다. 각 키를 7로 나눈 나머지가 곧 저장 위치(버킷 번호)가 되며, 예를 들어 9와 16은 나머지가 모두 2이므로 2번 버킷에 함께 연결되어 저장됩니다. 이처럼 체이닝은 충돌이 발생하더라도 연결 리스트로 여러 요소를 관리할 수 있게 해주는 효과적인 해시 충돌 해결 기법입니다.