[C++로 배우는 알고리즘과 자료구조 ] Day 14: 해시 함수와 충돌 해결 기법

해시 함수 (Hash Function)

해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 테이블에서 해시 함수는 주어진 키를 인덱스로 변환하여 데이터의 저장 및 검색을 효율적으로 수행합니다.

해시 함수의 특성:

1. 결정적 (Deterministic): 동일한 입력에 대해 항상 동일한 해시 값을 반환해야 합니다.
2. 균등 분포 (Uniform Distribution): 해시 값이 가능한 고르게 분포되어야 합니다.
3. 빠른 계산 (Fast Computation): 해시 값을 빠르게 계산할 수 있어야 합니다.

충돌 해결 기법 (Collision Resolution)

해시 테이블에서 두 개 이상의 키가 동일한 해시 값을 가지는 경우를 충돌(Collision)이라고 합니다. 충돌을 해결하기 위한 대표적인 방법에는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다.

1. 체이닝 (Chaining)

체이닝은 각 인덱스에 연결 리스트를 사용하여 충돌을 해결하는 방법입니다. 동일한 해시 값을 가지는 모든 요소는 동일한 인덱스의 연결 리스트에 저장됩니다.

 

체이닝을 사용한 해시 테이블 구현

HashNode.h

#ifndef HASHNODE_H
#define HASHNODE_H

template <typename K, typename V>
class HashNode {
public:
    HashNode(const K& key, const V& value) : key(key), value(value), next(nullptr) {}

    K getKey() const { return key; }
    V getValue() const { return value; }
    void setValue(const V& value) { this->value = value; }

    HashNode* getNext() const { return next; }
    void setNext(HashNode* next) { this->next = next; }

private:
    K key;
    V value;
    HashNode* next;
};

#endif // HASHNODE_H

 

HashTable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include "HashNode.h"
#include <vector>
#include <cstddef>
#include <iostream>

template <typename K, typename V>
class HashTable {
public:
    HashTable(size_t size = 101) : table(size, nullptr), tableSize(size) {}

    ~HashTable();

    void insert(const K& key, const V& value);
    bool search(const K& key, V& value) const;
    bool remove(const K& key);
    void display() const; // 해시 테이블 출력

private:
    std::vector<HashNode<K, V>*> table;
    size_t tableSize;

    size_t hashFunction(const K& key) const;
};

// 소멸자 정의 (메모리 해제)
template <typename K, typename V>
HashTable<K, V>::~HashTable() {
    for (auto node : table) {
        while (node != nullptr) {
            HashNode<K, V>* prev = node;
            node = node->getNext();
            delete prev;
        }
    }
}

// 해시 함수 정의
template <typename K, typename V>
size_t HashTable<K, V>::hashFunction(const K& key) const {
    return std::hash<K>{}(key) % tableSize;
}

// 값 삽입 함수 정의
template <typename K, typename V>
void HashTable<K, V>::insert(const K& key, const V& value) {
    size_t hashValue = hashFunction(key);
    HashNode<K, V>* prev = nullptr;
    HashNode<K, V>* node = table[hashValue];

    while (node != nullptr && node->getKey() != key) {
        prev = node;
        node = node->getNext();
    }

    if (node == nullptr) {
        node = new HashNode<K, V>(key, value);
        if (prev == nullptr) {
            table[hashValue] = node;
        } else {
            prev->setNext(node);
        }
    } else {
        node->setValue(value);
    }
}

// 값 검색 함수 정의
template <typename K, typename V>
bool HashTable<K, V>::search(const K& key, V& value) const {
    size_t hashValue = hashFunction(key);
    HashNode<K, V>* node = table[hashValue];

    while (node != nullptr) {
        if (node->getKey() == key) {
            value = node->getValue();
            return true;
        }
        node = node->getNext();
    }

    return false;
}

// 값 삭제 함수 정의
template <typename K, typename V>
bool HashTable<K, V>::remove(const K& key) {
    size_t hashValue = hashFunction(key);
    HashNode<K, V>* prev = nullptr;
    HashNode<K, V>* node = table[hashValue];

    while (node != nullptr && node->getKey() != key) {
        prev = node;
        node = node->getNext();
    }

    if (node == nullptr) {
        return false;
    } else {
        if (prev == nullptr) {
            table[hashValue] = node->getNext();
        } else {
            prev->setNext(node->getNext());
        }
        delete node;
        return true;
    }
}

// 해시 테이블 출력 함수 정의
template <typename K, typename V>
void HashTable<K, V>::display() const {
    for (size_t i = 0; i < tableSize; ++i) {
        std::cout << "Bucket " << i << ": ";
        HashNode<K, V>* node = table[i];
        while (node != nullptr) {
            std::cout << "(" << node->getKey() << ", " << node->getValue() << ") -> ";
            node = node->getNext();
        }
        std::cout << "nullptr" << std::endl;
    }
}

#endif // HASHTABLE_H

 

체이닝을 사용한 해시 테이블 예제

#include <iostream>
#include "HashTable.h"

int main() {
    HashTable<std::string, int> hashTable;

    hashTable.insert("apple", 1);
    hashTable.insert("banana", 2);
    hashTable.insert("orange", 3);

    hashTable.display(); // 해시 테이블 출력

    int value;
    if (hashTable.search("banana", value)) {
        std::cout << "banana: " << value << std::endl;
    } else {
        std::cout << "banana를 찾을 수 없습니다." << std::endl;
    }

    if (hashTable.remove("apple")) {
        std::cout << "apple 삭제 완료" << std::endl;
    } else {
        std::cout << "apple을 찾을 수 없습니다." << std::endl;
    }

    hashTable.display(); // 해시 테이블 출력

    return 0;
}

 

2. 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생했을 때 다른 빈 인덱스를 찾아 데이터를 저장하는 방법입니다. 대표적인 개방 주소법으로는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.

 

선형 탐사 (Linear Probing)

선형 탐사는 충돌이 발생하면 고정된 간격으로 다음 인덱스를 탐색하여 빈 인덱스를 찾습니다.

 

LinearProbingHashTable.h

#ifndef LINEARPROBINGHASHTABLE_H
#define LINEARPROBINGHASHTABLE_H

#include <vector>
#include <iostream>

template <typename K, typename V>
class LinearProbingHashTable {
public:
    LinearProbingHashTable(size_t size = 101)
        : table(size, {nullptr, false}), tableSize(size), currentSize(0) {}

    void insert(const K& key, const V& value);
    bool search(const K& key, V& value) const;
    bool remove(const K& key);
    void display() const;

private:
    struct HashEntry {
        std::pair<K, V>* kvp;
        bool isDeleted;

        HashEntry() : kvp(nullptr), isDeleted(false) {}
    };

    std::vector<HashEntry> table;
    size_t tableSize;
    size_t currentSize;

    size_t hashFunction(const K& key) const;
};

// 해시 함수 정의
template <typename K, typename V>
size_t LinearProbingHashTable<K, V>::hashFunction(const K& key) const {
    return std::hash<K>{}(key) % tableSize;
}

// 값 삽입 함수 정의
template <typename K, typename V>
void LinearProbingHashTable<K, V>::insert(const K& key, const V& value) {
    size_t hashValue = hashFunction(key);
    size_t index = hashValue;

    while (table[index].kvp != nullptr && !table[index].isDeleted && table[index].kvp->first != key) {
        index = (index + 1) % tableSize;
    }

    if (table[index].kvp == nullptr || table[index].isDeleted) {
        table[index].kvp = new

 std::pair<K, V>(key, value);
        table[index].isDeleted = false;
        ++currentSize;
    } else {
        table[index].kvp->second = value;
    }
}

// 값 검색 함수 정의
template <typename K, typename V>
bool LinearProbingHashTable<K, V>::search(const K& key, V& value) const {
    size_t hashValue = hashFunction(key);
    size_t index = hashValue;

    while (table[index].kvp != nullptr) {
        if (!table[index].isDeleted && table[index].kvp->first == key) {
            value = table[index].kvp->second;
            return true;
        }
        index = (index + 1) % tableSize;
    }

    return false;
}

// 값 삭제 함수 정의
template <typename K, typename V>
bool LinearProbingHashTable<K, V>::remove(const K& key) {
    size_t hashValue = hashFunction(key);
    size_t index = hashValue;

    while (table[index].kvp != nullptr) {
        if (!table[index].isDeleted && table[index].kvp->first == key) {
            table[index].isDeleted = true;
            delete table[index].kvp;
            table[index].kvp = nullptr;
            --currentSize;
            return true;
        }
        index = (index + 1) % tableSize;
    }

    return false;
}

// 해시 테이블 출력 함수 정의
template <typename K, typename V>
void LinearProbingHashTable<K, V>::display() const {
    for (size_t i = 0; i < tableSize; ++i) {
        if (table[i].kvp != nullptr && !table[i].isDeleted) {
            std::cout << "Bucket " << i << ": (" << table[i].kvp->first << ", " << table[i].kvp->second << ") " << std::endl;
        } else {
            std::cout << "Bucket " << i << ": nullptr" << std::endl;
        }
    }
}

#endif // LINEARPROBINGHASHTABLE_H

 

선형 탐사를 사용한 해시 테이블 예제

#include <iostream>
#include "LinearProbingHashTable.h"

int main() {
    LinearProbingHashTable<std::string, int> hashTable;

    hashTable.insert("apple", 1);
    hashTable.insert("banana", 2);
    hashTable.insert("orange", 3);

    hashTable.display(); // 해시 테이블 출력

    int value;
    if (hashTable.search("banana", value)) {
        std::cout << "banana: " << value << std::endl;
    } else {
        std::cout << "banana를 찾을 수 없습니다." << std::endl;
    }

    if (hashTable.remove("apple")) {
        std::cout << "apple 삭제 완료" << std::endl;
    } else {
        std::cout << "apple을 찾을 수 없습니다." << std::endl;
    }

    hashTable.display(); // 해시 테이블 출력

    return 0;
}

 

설명

1. 해시 함수 (Hash Function):
   • 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환합니다.
   • 해시 함수는 결정적이어야 하며, 균등 분포와 빠른 계산의 특성을 가져야 합니다.
2. 충돌 해결 기법 (Collision Resolution):
   • 체이닝 (Chaining): 각 인덱스에 연결 리스트를 사용하여 충돌을 해결합니다.
   • 개방 주소법 (Open Addressing): 충돌이 발생하면 다른 빈 인덱스를 찾아 데이터를 저장합니다.

이제 해시 함수와 충돌 해결 기법의 기본 개념과 구현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 15: 정렬 알고리즘 개요"에 대해 학습하겠습니다.