해시 테이블 (Hash Table)의 개념 및 구현

해시 테이블(Hash Table)의 개념 및 구현

해시 테이블(Hash Table)은 효율적으로 데이터를 저장하고 검색할 수 있는 데이터 구조입니다. 주로 키(Key)와 값(Value)의 쌍으로 데이터를 저장하며, 해시 함수(Hash Function)를 사용해 데이터를 적절한 위치에 매핑합니다. 이번 포스팅에서는 해시 테이블의 개념, 작동 원리, 장단점, 구현 방법, 그리고 활용 사례에 대해 설명합니다.

---

1. 해시 테이블의 개념

1.1 정의

해시 테이블은 키를 기반으로 데이터를 저장하고 검색하는 데이터 구조입니다. 키를 해시 함수에 입력하면, 고유한 해시 값(Hash Value)이 생성되고 이를 사용해 데이터를 저장할 인덱스를 결정합니다.

1.2 특징

• 빠른 검색: 평균 시간 복잡도는 O(1)입니다.
• 키-값 구조: 각 키는 유일하며, 값과 매핑됩니다.
• 해시 함수: 키를 해시 값으로 변환하는 함수로, 해시 충돌(Collision)을 최소화해야 합니다.

---

2. 작동 원리

1. 키를 해시 함수에 전달:
   • 해시 함수는 키를 고유한 정수 값(해시 값)으로 변환합니다.
2. 해시 값을 기반으로 인덱스 생성:
   • 해시 값을 배열 크기와 연산(Modulus)하여 배열 내 위치를 결정합니다.
3. 데이터 저장 및 검색:
   • 해당 인덱스에 데이터를 저장하거나 검색합니다.

---

3. 해시 충돌(Collision)

3.1 발생 원인

두 개 이상의 키가 같은 해시 값을 갖는 경우 발생합니다. 이는 해시 테이블에서 해결해야 할 중요한 문제입니다.

3.2 해결 방법

1. 체이닝(Chaining):
   • 같은 인덱스에 여러 값을 저장하기 위해 연결 리스트(Linked List)를 사용합니다.
2. 오픈 주소법(Open Addressing):
   • 충돌이 발생하면 다른 빈 위치를 찾아 데이터를 저장합니다.
   • 방법: 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing).

---

4. C#으로 해시 테이블 구현

4.1 체이닝 기반 구현

using System;
using System.Collections.Generic;

public class HashTable<TKey, TValue>
{
    private readonly int size;
    private readonly LinkedList<KeyValuePair<TKey, TValue>>[] buckets;

    public HashTable(int size)
    {
        this.size = size;
        buckets = new LinkedList<KeyValuePair<TKey, TValue>>[size];
        for (int i = 0; i < size; i++)
        {
            buckets[i] = new LinkedList<KeyValuePair<TKey, TValue>>();
        }
    }

    private int GetBucketIndex(TKey key)
    {
        return Math.Abs(key.GetHashCode()) % size;
    }

    public void Add(TKey key, TValue value)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];

        foreach (var pair in bucket)
        {
            if (pair.Key.Equals(key))
                throw new ArgumentException("Key already exists");
        }

        bucket.AddLast(new KeyValuePair<TKey, TValue>(key, value));
    }

    public TValue Get(TKey key)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];

        foreach (var pair in bucket)
        {
            if (pair.Key.Equals(key))
                return pair.Value;
        }

        throw new KeyNotFoundException("Key not found");
    }

    public void Remove(TKey key)
    {
        int index = GetBucketIndex(key);
        var bucket = buckets[index];

        foreach (var pair in bucket)
        {
            if (pair.Key.Equals(key))
            {
                bucket.Remove(pair);
                return;
            }
        }

        throw new KeyNotFoundException("Key not found");
    }

    public void Print()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write($"Bucket {i}: ");
            foreach (var pair in buckets[i])
            {
                Console.Write($"[{pair.Key}: {pair.Value}] ");
            }
            Console.WriteLine();
        }
    }
}

// 사용 예제
public class Program
{
    public static void Main()
    {
        var hashTable = new HashTable<string, int>(10);

        hashTable.Add("apple", 3);
        hashTable.Add("banana", 5);
        hashTable.Add("cherry", 7);

        Console.WriteLine($"Value for 'apple': {hashTable.Get("apple")}");
        hashTable.Remove("banana");

        hashTable.Print();
    }
}

4.2 출력 결과

Value for 'apple': 3
Bucket 0: 
Bucket 1: 
Bucket 2: 
Bucket 3: [cherry: 7] 
Bucket 4: 
Bucket 5: 
Bucket 6: 
Bucket 7: [apple: 3] 
Bucket 8: 
Bucket 9:​

---

5. 장단점

5.1 장점

1. 빠른 검색, 삽입, 삭제: 평균 시간 복잡도는 O(1)
2. 확장성: 다양한 데이터 형식을 저장 가능.

5.2 단점

1. 해시 충돌: 적절한 해시 함수 설계가 필수.
2. 메모리 사용량: 배열 크기 및 충돌 해결 방식에 따라 증가.

---

6. 활용 사례

1. 캐싱(Caching):
   • 데이터의 빠른 검색이 필요한 경우 사용.
   • 예: 웹 브라우저의 캐시.
2. 데이터베이스 인덱싱:
   • 빠른 데이터 조회를 위한 키-값 기반 구조.
3. 문자열 매칭:
   • 서브스트링 검색 등.
4. 집합 연산:
   • 유일한 데이터 저장 및 확인.

---

해시 테이블은 효율적인 데이터 저장 및 검색을 위한 핵심 데이터 구조입니다.
적절한 해시 함수를 설계하고 충돌 해결 방법을 선택하면 대부분의 응용에서 탁월한 성능을 발휘할 수 있습니다.