C++ 알고리즘) 해시 테이블

해시(Hash) 및 해시 테이블(Hash Table)

1. 기본 개념

• 해시(Hash): 임의의 길이를 가진 데이터를 고정된 길이의 고유한 값(해시 값)으로 변환하는 과정이다.
• 해시 테이블(Hash Table): 키(Key)와 값(Value)을 연결하여 데이터를 저장하는 자료구조다. 해시 함수를 이용해 키를 인덱스로 변환하므로, 평균 O(1)의 매우 빠른 탐색 속도를 보장한다.

2. 해시 함수 (Hash Function)

• 정의: 키를 입력받아 배열의 인덱스(해시 주소)를 출력하는 함수다.
• 특징:
  • 같은 입력에 대해 항상 같은 출력을 내야 한다.
  • 입력값이 조금만 달라져도 출력값이 크게 변하는 것이 좋다(눈사태 효과).
  • 해시 충돌을 최소화할 수 있도록 인덱스를 고르게 분산시켜야 한다.

종류:

1. 나눗셈법 (Division Method) 가장 직관적이고 널리 쓰이는 방법이다. 키를 테이블의 크기로 나눈 나머지를 인덱스로 사용한다.

• 공식: h(k) = k (mod m)
• 특징: 테이블 크기 m이 2의 거듭제곱에 가깝지 않은 소수(Prime Number) 일 때 충돌이 가장 적다.
• 장점: 구현이 매우 빠르고 간단하다.

2. 곱셈법 (Multiplication Method) 키에 0과 1 사이의 상수 A를 곱한 뒤, 그 소수 부분만을 취해 테이블 크기 m을 곱하는 방식이다.

• 공식: h(k) = [ m(kA (mod 1))]
• 특징: 테이블 크기 m의 선택이 나눗셈법보다 자유롭다. 보통 A = 0.618033... (황금비)를 권장한다.
• 장점: 키의 분포가 고르지 않아도 비교적 균등한 해싱이 가능하다.

3. 문자열 해싱 (String Hashing) 문자열은 길이가 가변적이므로 각 문자의 아스키(ASCII) 값에 특정 가중치(보통 소수)를 곱해 더하는 다항식 롤링 해시(Polynomial Rolling Hash) 방식을 주로 사용한다.

• 공식:

• 특징: P는 주로 31이나 53 같은 소수를 사용하며, m은 매우 큰 소수를 사용하여 충돌을 방지한다.

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

class HashFunctions {
public:
    // 1. 나눗셈법
    int divisionHash(int key, int m) {
        return key % m;
    }

    // 2. 곱셈법
    int multiplicationHash(int key, int m) {
        const double A = 0.6180339887; // 황금비
        double temp = key * A;
        double fractionalPart = temp - floor(temp); // 소수 부분 추출
        return floor(m * fractionalPart);
    }

    // 3. 문자열 해싱 (djb2 알고리즘 유사 방식)
    unsigned long stringHash(string str, int m) {
        unsigned long hash = 5381;
        for (char c : str) {
            // hash * 33 + c 와 동일 (비트 연산으로 최적화)
            hash = ((hash << 5) + hash) + c;
        }
        return hash % m;
    }
};

int main() {
    HashFunctions hf;
    int m = 101; // 테이블 크기 (소수)

    cout << "Division (Key 12345): " << hf.divisionHash(12345, m) << endl;
    cout << "Multiplication (Key 12345): " << hf.multiplicationHash(12345, m) << endl;
    cout << "String (Key 'Gemini'): " << hf.stringHash("Gemini", m) << endl;

    return 0;
}

 

3. 해시 충돌 (Hash Collision)

서로 다른 두 개 이상의 키가 해시 함수에 의해 동일한 인덱스로 배정되는 현상을 말한다. 이를 해결하기 위한 주요 기법은 다음과 같다.

 

A. 체이닝 (Chaining) - 폐쇄 주소법

• 각 버킷(Bucket)을 연결 리스트(Linked List)로 구현한다.

• 충돌이 발생하면 해당 인덱스의 리스트에 데이터를 추가한다.

• 메모리 사용량이 유연하지만, 한 인덱스에 데이터가 쏠리면 성능이 O(N)으로 저하될 수 있다.

 

// 목적: 해시 테이블에서 체이닝(Chaining)을 이용하여 값을 저장하고 출력하는 예제
// 동작: 동일한 해시 인덱스를 가진 값들은 연결 리스트로 연결됨

#include <iostream>
#include <list>
using namespace std;

const int TABLE_SIZE = 5;

class HashTable {
    list<int> table[TABLE_SIZE];

public:
    void insert(int key) {
        int index = key % TABLE_SIZE;
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < TABLE_SIZE; ++i) {
            cout << i << ": ";
            for (int val : table[i]) {
                cout << val << " -> ";
            }
            cout << "NULL" << endl;
        }
    }
};

int main() {
    HashTable ht;
    ht.insert(1);
    ht.insert(6);
    ht.insert(11);
    ht.insert(2);
    ht.insert(7);

    ht.display();

    return 0;
}

/*
출력결과
0: 
1: 1 -> 6 -> 11 -> NULL
2: 2 -> 7 -> NULL
3: 
4: 
*/

 

B. 개방 주소법 (Open Addressing)

충돌 발생 시 빈 버킷을 찾아 데이터를 저장하는 방식이다.

1. 선형 조사법(Linear Probing): 충돌 시 정해진 폭(예: +1)만큼 이동하며 빈 칸을 찾는다. 데이터가 뭉치는 클러스터링(Clustering) 현상에 취약하다.

 

#include <iostream>
#include <vector> // 동적 배열 사용
#include <stdexcept> // 예외 처리 (선택 사항)

using namespace std;

const int TABLE_SIZE = 5;
const int EMPTY_SLOT = -1; // 빈 슬롯 표시 값

class HashTable {
    vector<int> table; // 해시 테이블 저장소 (벡터 사용)
    int current_size; // 현재 저장된 요소 개수

public:
    // 생성자: 테이블 초기화
    HashTable() : table(TABLE_SIZE, EMPTY_SLOT), current_size(0) {}

    // 선형 탐사 삽입
    void insert(int key) {
        // 테이블이 가득 찼는지 확인
        if (current_size >= TABLE_SIZE) {
             cerr << "오류: 해시 테이블 가득 참 (" << key << " 삽입 불가)" << endl;
             return;
        }

        int index = key % TABLE_SIZE; // 초기 해시 인덱스 계산
        int original_index = index;

        // 빈 슬롯 찾기 (선형 탐사)
        while (table[index] != EMPTY_SLOT) {
            index = (index + 1) % TABLE_SIZE; // 다음 인덱스로 이동 (테이블 끝->처음)
            if (index == original_index) { // 한 바퀴 돌았는지 확인 (이론상 불필요)
                 cerr << "오류: 삽입 중 무한 루프 가능성. 키: " << key << endl;
                 return;
            }
        }

        // 빈 슬롯에 키 삽입 및 크기 증가
        table[index] = key;
        current_size++;
    }

    // 해시 테이블 내용 출력
    void display() {
        cout << "--- 해시 테이블 (선형 탐사) ---" << endl;
        for (int i = 0; i < TABLE_SIZE; ++i) {
            cout << i << ": ";
            if (table[i] != EMPTY_SLOT) {
                cout << table[i]; // 값이 있으면 출력
            } else {
                cout << "EMPTY"; // 비어있으면 EMPTY 출력
            }
            cout << endl;
        }
        cout << "-----------------------------" << endl;
    }

    // 인덱스 1의 상태 출력
    void display_index_one() {
        cout << "--- 인덱스 1의 상태 ---" << endl;
        cout << "1: ";
        if (table[1] != EMPTY_SLOT) {
            cout << table[1];
        } else {
            cout << "EMPTY";
        }
        cout << endl;
        cout << "-----------------------" << endl;
    }
};

int main() {
    HashTable ht;
    ht.insert(1);
    ht.insert(6);
    ht.insert(11);
    ht.insert(2);
    ht.insert(7);

    ht.display(); // 전체 테이블 출력
    ht.display_index_one(); // 인덱스 1의 상태 출력

    return 0;
}

/*
최종 테이블 상태 (삽입 완료 후): [7, 1, 6, 11, 2]

예상 출력 결과:
--- 해시 테이블 (선형 탐사) ---
0: 7
1: 1
2: 6
3: 11
4: 2
-----------------------------
--- 인덱스 1의 상태 ---
1: 1
-----------------------
*/

 

2. 이차 조사법(Quadratic Probing): 폭을 제곱수(1^2, 2^2, 3^2...)로 늘리며 빈칸을 찾는다. 선형 조사보다는 덜하지만 여전히 뭉침 현상이 발생할 수 있다.

#include <iostream>
#include <vector>

using namespace std;

class QuadraticHashTable {
private:
    int size;
    vector<int> table;
    vector<bool> occupied;

public:
    QuadraticHashTable(int n) : size(n), table(n, -1), occupied(n, false) {}

    void insert(int key) {
        int hashValue = key % size;
        int i = 0;
        
        // 빈 공간을 찾을 때까지 이차식으로 조사
        while (occupied[(hashValue + i * i) % size]) {
            i++;
            if (i == size) { // 테이블이 가득 찬 경우
                cout << "Table is full!" << endl;
                return;
            }
        }
        
        int index = (hashValue + i * i) % size;
        table[index] = key;
        occupied[index] = true;
        cout << key << " inserted at index " << index << endl;
    }
};

 

3. 이중 해싱(Double Hashing): 충돌 시 별도의 제2 해시 함수를 사용하여 이동 폭을 결정한다. 규칙성을 없애 클러스터링을 효과적으로 방지한다.

#include <iostream>
#include <vector>

using namespace std;

class DoubleHashTable {
private:
    int size;
    vector<int> table;
    vector<bool> occupied;

    int hash1(int key) { return key % size; }
    // 제2 해시 함수: 조사 간격을 결정 (0이 되면 안 됨)
    int hash2(int key) { return 5 - (key % 5); } 

public:
    DoubleHashTable(int n) : size(n), table(n, -1), occupied(n, false) {}

    void insert(int key) {
        int h1 = hash1(key);
        int h2 = hash2(key);
        int i = 0;

        while (occupied[(h1 + i * h2) % size]) {
            i++;
            if (i == size) {
                cout << "Table is full!" << endl;
                return;
            }
        }

        int index = (h1 + i * h2) % size;
        table[index] = key;
        occupied[index] = true;
        cout << key << " inserted at index " << index << " (step size: " << h2 << ")" << endl;
    }
};

int main() {
    DoubleHashTable dht(7);
    dht.insert(7);  // 7%7 = 0
    dht.insert(14); // 14%7 = 0 (충돌), h2 = 5-(14%5) = 1 -> index 1
    dht.insert(21); // 21%7 = 0 (충돌), h2 = 5-(21%5) = 4 -> index 4
    
    return 0;
}