[c++] 해시 테이블의 기본 구조

08 Dec 2023

해시 함수 (Hash Function)

해시 테이블에서 가장 중요한 요소는 해시 함수입니다. 해시 함수는 특정 키를 해시된 값으로 변환하여 해당 값의 인덱스를 계산합니다. 이를 통해 값을 배열의 특정 위치에 저장하거나 검색할 수 있습니다.

unsigned int hashFunction(string key, int tableSize) {
    unsigned int hash = 0;
    for (char& c : key) {
        hash = (hash * 31 + c) % tableSize;
    }
    return hash;
}

위 코드는 간단한 문자열 해싱을 구현한 예시입니다. 이 해시 함수는 문자열의 각 문자를 이용하여 해시 값을 계산합니다.

충돌 (Collision)

해시 함수가 제대로 설계되지 않았거나 여러 키가 동일한 해시 값을 갖는 경우 충돌이 발생할 수 있습니다. 이러한 충돌을 처리하는 기법에는 개별 체이닝(Chaining)과 개방 주소법(Open Addressing) 등이 있습니다.

구현 예시

class HashTable {
private:
    vector<vector<pair<string, int>>> table;
    int size;
public:
    HashTable(int initialSize) : size(initialSize) {
        table.resize(size);
    }

    void insert(string key, int value) {
        int index = hashFunction(key, size);
        table[index].push_back({key, value});
    }

    optional<int> search(string key) {
        int index = hashFunction(key, size);
        for (auto& entry : table[index]) {
            if (entry.first == key) {
                return entry.second;
            }
        }
        return nullopt;
    }
};

위 코드는 C++을 사용하여 간단한 해시 테이블을 구현한 예시입니다.

해시 테이블은 효율적인 데이터 저장 및 검색을 위한 중요한 자료구조입니다. 충돌을 효과적으로 처리하고 해시 함수를 잘 설계하는 것이 중요합니다.