자료구조 - 해싱
[해싱(Hashing)]
해싱(Hashing)은 데이터를 저장하고 검색하는 빠른 방법 중 하나입니다.
이는 해시 함수를 사용하여 데이터를 해시 값으로 변환한 후, 이 값을 사용하여 데이터를 저장하고 검색합니다.
해싱은 주로 사전(딕셔너리)과 같은 추상 자료형을 구현하는 데 사용됩니다.
[맵(Map)]
사전(dictionary), 맵(map), 테이블(table) :: 셋 다 같은 이름입니다.
균형이진트리의 일종인 레드-블랙 트리로 구현되어 있습니다.
키-값으로 저장하고 키로 검색하여 값을 찾고, 이진 탐색을 사용하므로 검색이 빠른 편입니다.
삽입, 삭제 시 균형트리이기 때문에 균형을 유지하는데에 오버헤드가 생깁니다.
맵에 삽입하는 경우 이미 있는 key라면 값을 삽입하지 않고 이미 키가 있는 해당 노드의 키/값을 리턴합니다.
정확히는 사전은 insert 할 경우 무조건 pair를 리턴합니다.
pair < std::pair(key, value), bool > 을 리턴합니다.
bool : 해당 키가 이미 맵에 있는지 없는지를 리턴합니다. 있으면 false, 없으면 true
앞의 pair은 (키, 값) 입니다.
맵의 개념
- 키(Key) : 데이터를 식별하는 유일한 값입니다.
- 값(Value) : 키에 연결된 데이터입니다.
사전의 연산
- 삽입(Insert) : 주어진 키와 값을 사전에 추가합니다.
- 삭제(Delete) : 주어진 키에 연결된 값을 사전에서 제거합니다.
- 검색(Search) : 주어진 키에 해당하는 값을 찾습니다.
- 수정(Modify) : 주어진 키에 연결된 값을 변경합니다
[해싱의 구조]
해싱은 해시 테이블(Hash Table)이라는 배열을 사용하여 데이터를 저장합니다.
해시 함수를 사용하여 키를 해시 값으로 변환하고, 이 해시 값에 따라 배열의 인덱스를 결정합니다.
이상적인 해싱 알고리즘
- 균등한 분배: 가능한 모든 해시 값이 해시 테이블에서 균일하게 분배되어야 합니다.
- 충돌 최소화: 서로 다른 키에 대해 충돌이 발생할 확률을 최소화해야 합니다.
add(key, value) :
index <- hash_function(key)
ht[index] = value
search(key) :
index <- hash_function(key)
return ht[index]
해시 함수
해시 함수는 임의의 길이의 데이터를 고정된 길이의 해시 값으로 변환하는 함수입니다.
좋은 해시 함수의 조건 :
1. 충돌이 적어야 합니다.
2. 해시함수 값이 해시테이블 주소 영역 내에서 고르게 분포되어야 합니다.
3. 계산이 빨라야 합니다.
해시 함수의 종류 :
1. 제산 함수: 키를 해시 테이블의 크기로 나눈 나머지를 해시 값으로 사용합니다.
2. 폴딩 함수: 키를 일정한 크기의 부분으로 나누고 이를 더하여 해시 값을 만듭니다.
3. 중간 제곱 함수: 키를 제곱한 후 중간 일부를 해시 값으로 사용합니다.
4. 비트 추출 방법: 키의 비트를 일부 추출하여 해시 값을 만듭니다.
5. 숫자 분석 방법: 키의 내부 구조를 분석하여 해시 값을 만듭니다.
* 주의할 점
문자열 키의 경우 해시 함수를 선택할 때 고려해야 할 사항이 있습니다.
이는 문자열의 내용이나 길이에 따라 충돌이 발생할 수 있기 때문입니다.
일반적으로 문자열의 모든 문자를 고려하여 해시 값을 계산하는 것이 좋습니다.
[충돌 해결 방법]
충돌(collision) 이란 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상입니다.
충돌이 발생하고, 해시 주소에 더 이상 빈 버킷이 남아있지 않으면 오버플로우가 발생합니다.
오버플로우가 발생하면 해시테이블에 항목을 저장할 수 없습니다.
이러한 오버플로우를 해결하는 방법은 개방 주소법과 체이닝이 있습니다.
개방 주소법(Open Addressing)
개방 주소법은 충돌이 발생하면 다른 빈 슬롯을 찾아 이동하는 방식입니다. 이 중에서 선형 조사법과 이차 조사법을 구현해 보겠습니다.
선형 조사법(Linear Probing) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입합니다.
#include <iostream>
#include <vector>
using namespace std;
class HashTable
{
private:
static const int TABLE_SIZE = 10;
vector<int> table[TABLE_SIZE]; // 해시 테이블 배열
// 해시 함수: 키를 해시 값으로 변환
int hashFunction(int key)
{
return key % TABLE_SIZE;
}
// 선형 조사 함수
int linearProbe(int hashValue, int i)
{
return (hashValue + i) % TABLE_SIZE;
}
public:
// 삽입 함수
void insert(int key)
{
int index = hashFunction(key);
int i = 0;
// 충돌이 발생한 경우 선형 조사를 수행하여 다음 위치를 계산
while (!table[index].empty())
{
index = linearProbe(index, ++i);
}
// 빈 슬롯에 데이터 삽입
table[index].push_back(key);
}
// 해시 테이블 출력 함수
void display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
cout << "[" << i << "]: ";
for (int key : table[i])
{
cout << key << " ";
}
cout << endl;
}
}
};
int main()
{
HashTable hashTable;
// 데이터 삽입
hashTable.insert(10);
hashTable.insert(22);
hashTable.insert(31);
hashTable.insert(14);
hashTable.insert(27);
hashTable.insert(42);
// 해시 테이블 출력
hashTable.display();
return 0;
}
이차 조사법(Quadratic Probing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용합니다.
#include <iostream>
#include <vector>
using namespace std;
class HashTable
{
private:
static const int TABLE_SIZE = 10;
vector<int> table[TABLE_SIZE]; // 해시 테이블 배열
// 해시 함수: 키를 해시 값으로 변환
int hashFunction(int key)
{
return key % TABLE_SIZE;
}
// 제곱수 계산 함수
int quadraticProbe(int hashValue, int i)
{
return (hashValue + i * i) % TABLE_SIZE;
}
public:
// 삽입 함수
void insert(int key)
{
int index = hashFunction(key);
int i = 0;
// 충돌이 발생한 경우 제곱수를 이용하여 다음 위치를 계산
while (!table[index].empty())
{
index = quadraticProbe(index, ++i);
}
// 빈 슬롯에 데이터 삽입
table[index].push_back(key);
}
// 해시 테이블 출력 함수
void display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
cout << "[" << i << "]: ";
for (int key : table[i])
{
cout << key << " ";
}
cout << endl;
}
}
};
int main()
{
HashTable hashTable;
// 데이터 삽입
hashTable.insert(10);
hashTable.insert(22);
hashTable.insert(31);
hashTable.insert(14);
hashTable.insert(27);
hashTable.insert(42);
// 해시 테이블 출력
hashTable.display();
return 0;
}
제곱 조사법(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입합니다. (1,4,9,16..)
#include <iostream>
#include <vector>
using namespace std;
class HashTable
{
private:
static const int TABLE_SIZE = 10;
vector<int> table[TABLE_SIZE]; // 해시 테이블 배열
// 해시 함수: 키를 해시 값으로 변환
int hashFunction(int key)
{
return key % TABLE_SIZE;
}
// 제곱수 계산 함수
int quadraticProbe(int hashValue, int i)
{
return (hashValue + i * i) % TABLE_SIZE;
}
public:
// 삽입 함수
void insert(int key)
{
int index = hashFunction(key);
int i = 0;
// 충돌이 발생한 경우 제곱수를 이용하여 다음 위치를 계산
while (!table[index].empty())
{
index = quadraticProbe(index, ++i);
}
// 빈 슬롯에 데이터 삽입
table[index].push_back(key);
}
// 해시 테이블 출력 함수
void display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
cout << "[" << i << "]: ";
for (int key : table[i])
{
cout << key << " ";
}
cout << endl;
}
}
};
int main()
{
HashTable hashTable;
// 데이터 삽입
hashTable.insert(10);
hashTable.insert(22);
hashTable.insert(31);
hashTable.insert(14);
hashTable.insert(27);
hashTable.insert(42);
// 해시 테이블 출력
hashTable.display();
return 0;
}
체이닝(Chaining)
체이닝은 충돌이 발생해도 모든 항목을 동일한 해시 값의 버킷에 저장하는 방식입니다. 각 버킷은 연결 리스트로 구현됩니다.
#include <list>
using namespace std;
// 체이닝을 위한 버킷 구조체
struct Bucket
{
list<int> values; // 값 리스트
// 기타 필요한 멤버 변수 및 메서드 정의
};
// 해시 테이블 구조체
class HashTable
{
private:
int size; // 해시 테이블 크기
Bucket* buckets; // 버킷 배열
public:
// 생성자, 소멸자 및 기타 메서드 정의
};
해시 테이블 구현
#include <iostream>
#include <list>
using namespace std;
// 체이닝을 위한 버킷 구조체
struct Bucket
{
list<int> values; // 값 리스트
// 기타 필요한 멤버 변수 및 메서드 정의
};
// 해시 테이블 구조체
class HashTable
{
private:
int size; // 해시 테이블 크기
Bucket* buckets; // 버킷 배열
public:
// 생성자
HashTable(int size)
{
this->size = size;
buckets = new Bucket[size];
}
// 소멸자
~HashTable()
{
delete[] buckets;
}
// 해시 함수
int hashFunction(int key)
{
return key % size;
}
// 삽입 연산
void insert(int key)
{
int index = hashFunction(key);
buckets[index].values.push_back(key);
}
// 삭제 연산
void remove(int key)
{
int index = hashFunction(key);
buckets[index].values.remove(key);
}
// 검색 연산
bool search(int key)
{
int index = hashFunction(key);
for (int value : buckets[index].values)
{
if (value == key)
{
return true;
}
}
return false;
}
// 기타 필요한 메서드 정의
};
int main()
{
// 해시 테이블 생성
HashTable hashTable(10);
// 삽입 연산
hashTable.insert(10);
hashTable.insert(20);
hashTable.insert(30);
// 검색 연산
cout << "Search 20: " << (hashTable.search(20) ? "Found" : "Not Found") << endl;
// 삭제 연산
hashTable.remove(20);
// 검색 연산
cout << "Search 20: " << (hashTable.search(20) ? "Found" : "Not Found") << endl;
return 0;
}
해싱의 성능 분석
체이닝의 장점 :
- 연결 리스트만 사용하면 된다. 즉, 복잡한 계산논리를 사용할 필요가 개방주소법에 비해 적다.
- 해시테이블이 채워질수록, Lookup 성능저하가 선형적으로 발생한다. (그림 참조)
개방 주소법의 장점 :
- 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다.
- 삽입, 삭제시 오버헤드가 적다.
- 저장할 데이터가 적을 때 더 유리하다.