해시 테이블

해시 테이블(Hash Table)은 데이터를 저장할 때, 키(Key)와 값(Value)으로 쌍으로 저장하는 자료구조이며, 각 키(Key)에 대해 고유한 인덱스를 생성하여 해당 인덱스 위치에 값을 저장하는 방식을 사용합니다.

해시 테이블의 핵심은 해시 함수(Hash Function)입니다. 해시 함수는 키(Key)를 받아서 고유한 인덱스(Hash Value)를 생성합니다. 이 과정에서 해시 함수는 키(Key)와 인덱스(Hash Value) 사이에 일대일 대응 관계를 만들어야 합니다. 즉, 동일한 키(Key)에 대해서는 항상 동일한 인덱스(Hash Value)가 생성되어야 합니다.

해시 함수에서 생성된 인덱스(Hash Value)는 배열(Array)의 인덱스로 사용됩니다. 해시 테이블에서는 생성된 인덱스(Hash Value)를 이용하여 값을 저장하고 검색합니다. 만약 동일한 키(Key)를 가진 데이터가 여러 개 존재하는 경우 충돌(Collision)이 발생할 수 있습니다. 이 때, 충돌을 처리하는 방법에 따라서 해시 테이블의 성능이 달라집니다.

해시 테이블은 다음과 같은 특징을 가집니다.

빠른 검색 속도: 해시 함수를 이용하여 고유한 인덱스(Hash Value)를 생성하므로, 값을 검색하는 데에 상수 시간(O(1))이 소요됩니다.
삽입/삭제 속도가 빠름: 해시 함수를 이용하여 인덱스(Hash Value)를 생성하므로, 배열(Array)의 특정 위치에 직접 접근하여 값을 삽입하거나 삭제할 수 있습니다.
저장 공간 낭비가 있을 수 있음: 해시 함수를 이용하여 인덱스(Hash Value)를 생성하므로, 저장소 공간을 재사용할 수 없어 메모리 사용량이 증가할 수 있습니다.
충돌(Collision) 문제가 발생할 수 있음: 해시 함수를 이용하여 생성된 인덱스(Hash Value)는 일대일 대응이 아닌 경우가 발생할 수 있으므로, 충돌(Collision) 문제를 해결해야 합니다.
해시 테이블은 C++ STL에서 unordered_map 클래스를 이용하여 구현할 수 있습니다. 이 클래스는 해시 테이블을 구현하고 있으며, 해시 함수를 이용하여 키(Key)와 인덱스(Hash Value)를 생성합니다. 충돌(Collision) 문제는 내부적으로 체이닝(Chaining) 기법을 이용하여 해결합니다.

 

 

 

해시 테이블 사용 예제

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    string str = "hello world";
    unordered_map<char, int> freq;

    // 문자열의 각 문자별 출현 빈도수 계산
    for (char c : str) {
        freq[c]++;
    }

    // 출현 빈도수 출력
    for (auto it = freq.begin(); it != freq.end(); it++) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}