Q. 배열이 인덱스 기반으로 접근 가능한데 왜 가능하냐
A. 배열은 동일한 데이터 타입의 값을 메모리에 연속으로 저장하기 때문에 입력한 인덱스 * 데이터 타입의 크기를 해 해당하는 메모리 주소에 접근하면 된다.
CPU는 한번에 일정 크기의 메모리(ex. 64byte)를 읽어오므로 순차 접근 시 캐시 미스가 줄어들어 성능이 향상됨
해시 테이블
주어진 키에 해시 함수를 적용해서 계산된 인덱스 위치에 값을 저장한다.
인덱스로 접근하므로 O(1)의 시간 복잡도를 가지게 된다
해시 함수는 같은 Key를 넣었을 때 반드시 같은 값이 반환되어야 한다는 조건이 있기 때문에 가능한 일이다.
우선 입력된 key를 해쉬 함수를 거쳐 고정 크기의 정수, 즉 해시 코드로 반환하고 이 값을 내부 배열(버킷)의 인덱스로 사용해 데이터를 저장한다.
간단한 예시를 들자면 index = hash(key) % table_size 이런 식으로 인덱스를 만들어 사용하게 된다.
이렇게 인덱스를 만들어서 저장하면 O(1)의 시간 복잡도를 가지게 되지만 현실적으로 해시 충돌(Collision)이 일어날 수 밖에 없다.
모든 해시 테이블은 반드시 충돌 해결 기법을 포함해야 한다.
해시 충돌의 해결 방법은 크게 2가지로 나눌 수 있다.
- 체이닝(Chaining) 방식
- 오픈 어드레싱(Open Addressing) 방식
체이닝 방식
이 방식에서는 동일한 해시 값을 가진 여러 키-값 쌍을 하나의 버킷(내부 배열)에 연결 리스트나 동적 배열과 같이 별도의 자료구조를 통해 저장한다.
체이닝 방식은 각 버킷에 여러 요소를 저장할 수 있어 테이블 전체의 크기와 상관없이 유연하게 데이터를 관리할 수 있는 장점이 있지만, 만약 충돌이 빈번해지면 해당 버킷 내에서 순차 탐색이 필요해지는 단점이 있다.
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <fstream>
#include <Windows.h>
#include <algorithm>
#include <set>
#include <numeric>
#include <map>
#include <queue>
#include <unordered_map>
#include <stack>
using namespace std;
const int TABLE_SIZE = 10;
class HashTable {
vector<list<string>> table;
public:
HashTable() : table(TABLE_SIZE) {}
void Insert(const string& key)
{
int index = Hash(key);
table[index].push_back(key);
}
void Display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
cout << i << " : ";
for (const auto& item : table[i])
{
cout << item << " → ";
}
cout << "nullptr\n";
}
}
private:
int Hash(const string& key) {
int h = 0;
for (char ch : key)
h += ch;
return h % TABLE_SIZE;
}
};
int main()
{
HashTable ht;
ht.Insert("apple");
ht.Insert("banana");
ht.Insert("grape");
ht.Insert("orange"); // 일부는 같은 버킷으로 충돌할 수 있음
ht.Display();
}오픈 어드레싱 방식
이 방식은 충돌이 발생할 경우, 충돌이 발생한 버킷 외의 다른 빈 버킷을 찾아 데이터를 저장한다.
오픈 어드레싱에는 여러 기법이 존재하는데, 가장 단순한 선형 탐사(Linear Probing)는 충돌이 발생하면 다음 인덱스를 순차적으로 검사하여 빈 버킷을 찾는다.
그러나 이 방식은 동일한 해시 값 근처에 데이터가 몰려 발생하는 1차 군집(Primary Clustering) 문제를 일으킬 수 있다.
이를 보완하기 위해 제곱 탐사(Quadratic Probing) 방식이 사용되며, 이 방식은 충돌 발생 시 탐사 간격을 제곱수로 증가시켜 빈 버킷을 찾는다.
또 다른 기법인 이중 해싱(Double Hashing)은 두 개의 해시 함수를 사용하여 첫 번째 해시 함수로 기본 인덱스를 결정하고, 두 번째 해시 함수를 통해 탐사 간격을 정함으로써 보다 균등한 분포와 뛰어난 충돌 회피 성능을 제공한다.
아래는 선형 탐사 방식이다.
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <fstream>
#include <Windows.h>
#include <algorithm>
#include <set>
#include <numeric>
#include <map>
#include <queue>
#include <unordered_map>
#include <stack>
using namespace std;
const int TABLE_SIZE = 10;
class OpenAddressingHashTable
{
vector<string> table;
public:
OpenAddressingHashTable() : table(TABLE_SIZE, "") {}
void Insert(const string& key)
{
int index = Hash(key);
int originalIndex = index;
while (!table[index].empty())
{
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex)
{
cout << "Table is full!\n";
return;
}
}
table[index] = key;
}
void Display()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
cout << i << " : " << (table[i].empty() ? "empty" : table[i]) << "\n";
}
}
private:
int Hash(const std::string& key)
{
int h = 0;
for (char ch : key)
h += ch;
return h % TABLE_SIZE;
}
};
int main()
{
OpenAddressingHashTable ht;
ht.Insert("apple");
ht.Insert("banana");
ht.Insert("grape");
ht.Insert("orange");
ht.Display();
return 0;
}해시 테이블은 키 기반 데이터 접근을 매우 빠르게 수행할 수 있다는 점에서 큰 장점을 가진다.
평균적으로 검색, 삽입, 삭제 연산이 O(1)의 시간 복잡도를 보장하므로, 객체 ID 매핑, 캐싱, 설정 값 저장 등 빠른 데이터 접근이 필요한 응용 분야에서 특히 유용하다.
하지만 해시 함수의 품질에 따라서 전체 성능이 크게 좌우될 수 있으며, 키의 분포가 고르지 않다면 속도가 매우 느려질 수 있다.
그리고 해시 테이블은 내부적으로 해시 버킷과 충돌 해결을 위한 추가 자료구조(예를 들어 체이닝 방식의 연결 리스트)를 사용하므로, 메모리 오버헤드가 발생한다.
데이터가 많아지면 해시 테이블의 크기를 동적으로 조절하기 위해 재해싱(Rehashing)이 필요해지는데, 이 과정에서는 모든 데이터를 새로운 버킷 배열로 옮기는 작업이 포함되어 일시적인 성능 저하가 발생할 수 있다.
메모리 관리 측면에서도 해시 테이블은 추가적인 버킷 공간과 충돌 해결 구조를 유지해야 하므로 전체 메모리 사용량이 증가하는 단점이 있다.
따라서, 해시 테이블을 설계할 때는 적절한 초기 크기와 부하 계수(Load Factor)를 설정하여 재해싱 빈도를 최소화하고 메모리 효율성을 높이는 전략이 필요하다.
