[c++] 빈번한 데이터 조회를 위한 해시 테이블 활용 방법

08 Dec 2023

해시 테이블은 빠른 데이터 조회를 위한 자료구조로, 데이터를 키-값 쌍으로 저장하여 O(1)의 시간복잡도로 데이터에 접근할 수 있습니다. 빈번한 데이터 조회를 위해서 해시 테이블을 어떻게 활용할 수 있는지 알아보겠습니다.

해시 함수 선택

해시 함수는 데이터를 해시 테이블의 인덱스로 변환하는 역할을 합니다. 빈번한 데이터 조회를 위해서는 해시 함수를 신중하게 선택해야 합니다. 데이터가 고르게 분포되도록 하는 좋은 해시 함수를 선택하는 것이 중요합니다.

unsigned int customHashFunction(const string& key) {
    unsigned int hash = 5381;
    for(char c : key) {
        hash = ((hash << 5) + hash) + c; // 해시 충돌을 최소화하기 위해 해시 값을 조정
    }
    return hash;
}

충돌 처리

다른 데이터가 동일한 해시값을 갖는 해시 충돌은 해시 테이블에서 자주 발생하는 문제입니다. 이를 해결하기 위해 충돌 처리 기법을 사용할 수 있습니다. 가장 일반적인 방법은 체이닝으로, 각 해시 버킷에 연결 리스트를 이용하여 충돌 데이터를 관리하는 것입니다.

class HashTable {
private:
    vector<list<pair<string, int>>> table;
    unsigned int size;

public:
    explicit HashTable(unsigned int size) : size(size), table(size) {}

    void insert(const string& key, int value) {
        int index = customHashFunction(key) % size;
        for(auto& kv : table[index]) {
            if(kv.first == key) {
                kv.second = value; // 이미 존재하는 키라면 값을 갱신
                return;
            }
        }
        table[index].emplace_back(key, value);
    }

    int get(const string& key) {
        int index = customHashFunction(key) % size;
        for(auto& kv : table[index]) {
            if(kv.first == key) {
                return kv.second;
            }
        }
        return -1; // 키에 해당하는 값이 없을 경우 -1 반환
    }
};

해시 테이블 사용

해시 테이블은 조회 연산에 최적화되어 있으므로, 빈번한 데이터 조회를 필요로 하는 경우에 활용될 수 있습니다. 예를 들어, 큰 양의 데이터를 빈번하게 탐색해야하는 경우 해시 테이블을 사용하여 효율적으로 조회할 수 있습니다.

참고 문헌: Scott, Wills. “Programming Principles and Practice Using C++” - Chapter 21

해시 테이블은 많은 데이터를 빠르게 조회하는 데에 유용한 자료구조입니다. 데이터 조회가 빈번한 상황에서는 해시 테이블 활용을 고려해보세요.

내용을 더 깊게 이해하고자 하시거나, 다양한 출처를 통해 정보를 찾고자 하신다면, 해시 테이블(Hash Table) 및 해시 함수(Hash Function) 페이지를 참고하시기 바랍니다.