해쉬(Hash)

해쉬는 데이터를 빠르게 저장하고 검색하기 위한 자료구조다.
데이터의 키를 입력받아 해쉬 함수를 통해 배열의 인덱스로 변환하고, 그 인덱스 위치에 데이터를 저장하는 방식으로 동작한다.
이 구조를 해쉬 테이블이라고 부른다.

---

해쉬의 기본 개념

일반적인 배열이나 리스트는 데이터를 순차적으로 탐색해야 하므로 검색 속도가 느리지만,
해쉬는 해쉬 함수를 통해 직접 인덱스를 계산하므로 평균적으로 O(1) 시간 안에 데이터 접근이 가능하다.

해쉬 테이블은 다음과 같은 구성 요소로 이루어진다.

1. 키(Key): 데이터를 구분하기 위한 고유 값
2. 값(Value): 실제 저장되는 데이터
3. 해쉬 함수(Hash Function): 키를 일정한 범위의 인덱스로 변환하는 함수
4. 버킷(Bucket): 변환된 인덱스에 해당하는 저장 공간

---

해쉬 충돌

서로 다른 키가 같은 해쉬 인덱스를 반환하는 경우를 충돌(Collision) 이라고 한다.
충돌은 완전히 피할 수 없기 때문에, 여러 가지 해결 방법이 사용된다.

1. 체이닝 (Chaining)
   같은 해쉬 인덱스에 연결 리스트를 만들어 여러 값을 저장한다.
2. 개방 주소법 (Open Addressing)
   충돌이 발생하면 다음 빈 공간을 찾아 저장한다.
   • 선형 탐사(Linear Probing)
   • 제곱 탐사(Quadratic Probing)
   • 이중 해싱(Double Hashing)

---

C++ 해쉬 테이블 예시 코드

#include <iostream>
#include <list>
using namespace std;

class HashTable {
private:
    static const int TABLE_SIZE = 10;
    list<pair<int, string>> table[TABLE_SIZE]; // 체이닝 방식 사용

    int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

public:
    void insert(int key, string value) {
        int index = hashFunction(key);
        for (auto& pair : table[index]) {
            if (pair.first == key) {
                pair.second = value;
                return;
            }
        }
        table[index].push_back({key, value});
    }

    string search(int key) {
        int index = hashFunction(key);
        for (auto& pair : table[index]) {
            if (pair.first == key)
                return pair.second;
        }
        return "데이터 없음";
    }

    void remove(int key) {
        int index = hashFunction(key);
        for (auto it = table[index].begin(); it != table[index].end(); ++it) {
            if (it->first == key) {
                table[index].erase(it);
                return;
            }
        }
    }

    void display() {
        for (int i = 0; i < TABLE_SIZE; ++i) {
            cout << i << ": ";
            for (auto& pair : table[i])
                cout << "(" << pair.first << ", " << pair.second << ") ";
            cout << endl;
        }
    }
};

int main() {
    HashTable ht;
    ht.insert(1, "Apple");
    ht.insert(2, "Banana");
    ht.insert(11, "Grape");
    ht.insert(21, "Orange");

    cout << "해쉬 테이블 상태:" << endl;
    ht.display();

    cout << "\n검색 결과: key 11 -> " << ht.search(11) << endl;

    ht.remove(2);
    cout << "\n삭제 후 상태:" << endl;
    ht.display();

    return 0;
}

---

정리

해쉬는 데이터를 빠르게 찾을 수 있는 효율적인 자료구조로,
탐색과 삽입은 평균적으로 O(1)의 시간 복잡도를 갖지만,
해쉬 함수의 품질과 충돌 처리 방식에 따라 성능이 크게 달라진다.
대표적인 활용 예로는 데이터베이스 인덱스, 캐시, 암호화 알고리즘 등이 있다.