[C++로 배우는 알고리즘과 자료구조] Day 5: 해시 테이블 (Hash Table)

해시 테이블 (Hash Table)

해시 테이블은 키(Key)와 값(Value) 쌍을 저장하는 자료구조로, 평균적으로 O(1) 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있습니다. 해시 테이블은 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용하여 값을 저장합니다.

해시 테이블의 주요 연산:

1. 삽입 (Insert): 키와 값을 해시 테이블에 삽입합니다.
2. 검색 (Search): 키를 사용하여 해시 테이블에서 값을 검색합니다.
3. 삭제 (Delete): 키를 사용하여 해시 테이블에서 값을 삭제합니다.

해시 함수 (Hash Function)

해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 해시 함수는 다음과 같은 특성을 가져야 합니다:

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

충돌 해결 (Collision Resolution)

해시 테이블에서 두 개 이상의 키가 동일한 해시 값을 가지는 경우, 이를 충돌이라고 합니다. 충돌을 해결하기 위한 방법에는 다음과 같은 것이 있습니다:

1. 체이닝 (Chaining): 각 인덱스에 연결 리스트를 사용하여 충돌을 해결합니다.
2. 개방 주소법 (Open Addressing): 충돌 시 다른 빈 인덱스를 찾습니다.

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

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>

// 해시 테이블 클래스
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);

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;
    }
}

#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);

    // 값 검색
    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;
    }

    // 값 재검색
    if (hashTable.search("apple", value)) {
        std::cout << "apple: " << value << std::endl;
    } else {
        std::cout << "apple을 찾을 수 없습니다." << std::endl;
    }

    return 0;
}

 

설명

1. 해시 테이블:
   • 해시 테이블은 키-값 쌍을 저장하는 자료구조로, 평균적으로 O(1) 시간 복잡도로 검색, 삽입, 삭제가 가능합니다.
   • 해시 함수를 사용하여 키를 해시 값으로 변환하고, 이를 인덱스로 사용하여 값을 저장합니다.
   • 체이닝을 사용하여 충돌을 해결합니다.
2. 해시 함수:
   • 해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다.
   • 결정적, 고르게 분포, 빠른 계산의 특성을 가져야 합니다.
3. 충돌 해결:
   • 체이닝을 사용하여 충돌을 해결합니다. 각 인덱스에 연결 리스트를 사용하여 충돌이 발생한 요소들을 저장합니다.

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

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 6: 트리의 기본 개념"에 대해 학습하겠습니다.