자료구조) 해시 테이블

해시 테이블(Hash Table)은 키(Key)와 값(Value)를 저장하는 데이터 구조이다.

키를 해시 함수(Hash Function)를 통해 배열의 인덱스로 변환하여 저장하므로,

탐색, 삽입, 삭제 연산을 평균적으로 O(1)의 시간 복잡도로 수행할 수 있다.

해시 테이블이 필요한 이유

배열과 연결 리스트의 한계

• 배열(Array)

  • 탐색 속도 O(1) (인덱스로 접근 가능)

  • 크기가 고정되어 있어 유연성이 부족함

  • 특정 값을 검색할 때 O(n)이 걸릴 수 있음

• 연결 리스트(Linked List)

  • 크기 조절이 자유롭지만, 탐색 속도가 O(n)

해시 테이블의 해결책

• 해시 테이블은 배열의 빠른 접근(O(1))과 연결 리스트의 유연성을 조합한 구조다.

• 키(Key)를 해시 함수(Hash Function)를 통해 인덱스로 변환하여 저장한다.

해시 테이블의 구조

해시 테이블은 키(Key) - 값(Value) 쌍(Item)을 저장하는 배열이다.

template<typename K, typename V>
class HashTable
{
public:
    struct Item
    {
        K key{};
        V value{};
    };

• key: 데이터를 찾는 고유한 값
• value: 키에 매칭되는 데이터
• 해시 테이블 내부에서 Item을 배열로 관리한다.

해시 함수 (Hash Function)

해시 함수는 키(Key)를 특정한 크기의 정수(배열 인덱스)로 변환하는 함수이다.

정수형 키

size_t HashFunc(const int& key)
{
    return key % capacity;
}

• 나머지 연산(%)을 사용하여 배열 크기(capacity) 내에서 인덱스를 결정한다.

문자열 키 (Horner’s Method)

size_t HashFunc(const string& s)
{
    int g = 71; // 소수 (충돌 방지 효과)
    size_t index = 0;
    for (char c : s)
    {
        index = (g * index + int(c)) % capacity;
    }
    return index;
}

• 문자열을 하나씩 가져와 곱셈과 나머지 연산을 반복 수행하여 해시값을 생성한다.

해시 충돌 (Collision) 해결 방법

해시 함수가 다르면 같은 인덱스로 매핑될 수 있다.

이를 “해시 충돌(Hash Collision)”이라 한다.

선형 탐사(Linear Probing)

void Insert(const Item& item)
{
    size_t index = HashFunc(item.key);

    // 충돌 발생 시 선형 탐사
    for (int i = 0; i < capacity; i++)
    {
        size_t new_index = (index + i) % capacity;
        if (hash_table_[new_index].key == K()) // 빈 자리 확인
        {
            hash_table_[new_index] = item;
            return;
        }
    }

    cout << "Failed to insert! Hash table is full." << endl;
}

• 이 코드에서 K()는 기본값을 생성하며, 빈 자리인지 확인 가능하다.
• 충돌 발생 시, 다음 인덱스로 이동하며 빈 공간을 찾는다.
• 장점: 구현이 간단함
• 단점: 클러스터링(Clustering, 연속적인 충돌) 문제 발생 가능

K() ?

• K는 템플릿 타입 매개변수(Template Type Parameter) 이다.
• K()는 해당 타입의 기본 생성자를 호출하는 표현식이다.

즉, K가 어떤 타입이냐에 따라 K()의 의미가 달라진다.

타입 K	K()의 결과
int	0
std::string	"" (빈 문자열)
bool	false
double	0.0

주요 연산

데이터 삽입 (Insert)

void Insert(const Item& item)
{
    size_t index = HashFunc(item.key);

    for (int i = 0; i < capacity; i++)
    {
        size_t new_index = (index + i) % capacity;
        if (hash_table_[new_index].key == K()) // 빈 자리 확인
        {
            hash_table_[new_index] = item;
            return;
        }
    }

    cout << "Failed to insert! Hash table is full." << endl;
}

시간 복잡도: 평균 O(1), 최악 O(n) (충돌이 많을 경우)

데이터 검색 (Get)

V Get(const K& key)
{
    size_t index = HashFunc(key);

    for (int i = 0; i < capacity; i++)
    {
        size_t new_index = (index + i) % capacity;
        if (hash_table_[new_index].key == key)
            return hash_table_[new_index].value;
    }

    return V(); // 기본값 반환
}

시간 복잡도: 평균 O(1), 최악 O(n)

해시 테이블 출력 (Print)

void Print()
{
    for (int i = 0; i < capacity; i++)
        cout << i << " : " << hash_table_[i].key << " " << hash_table_[i].value << endl;
    cout << endl;
}

해시 테이블 vs. 다른 자료구조

비교 항목	해시 테이블	배열(Array)	연결 리스트(Linked List)	이진 탐색 트리 (BST)
탐색 속도	O(1) (평균)	O(1)	O(n)	O(log n)
삽입 속도	O(1) (평균)	O(n) (중간 삽입)	O(1)	O(log n)
삭제 속도	O(1) (평균)	O(n)	O(n)	O(log n)
메모리 사용	여유 공간 필요	크기 고정	동적 할당	동적 할당
충돌 가능성	있음	없음	없음	없음

해시 테이블은 빠른 검색이 필요한 경우 유용하지만, 충돌 해결 기법이 필요하다.

BST는 정렬된 데이터 저장에 유리하고, 해시 테이블은 빠른 조회에 강점이 있다.

해시 테이블의 단점

• 해시 충돌 가능성
  • 충돌이 많으면 탐색 속도가 O(n)까지 느려질 수 있음
• 메모리 사용량 증가
  • 효율적인 해시 테이블은 빈 공간(Load Factor)을 유지해야 하므로 메모리 낭비 가능
• 정렬된 데이터 제공 불가능
  • 이진 탐색 트리와 달리 순차적인 데이터 접근이 어렵다.