📌 Hashing (해싱)

✅ 개념 요약

• Hashing은 데이터를 저장하고 조회하는 데 사용되는 고속 탐색 기법으로, 배열 기반 자료구조와 **해시 함수(hash function)**를 이용하여 구현됨.
• 일반적으로 해시는 **키(key)**를 기반으로 한 값을 특정한 위치에 빠르게 저장하거나 검색함.
• 정렬이 필요 없는 탐색 방식이며, 시간 복잡도는 평균적으로 **O(1)**에 가까움.

---

🔐 해시 함수 (Hash Function)

• 입력값(key)을 고정된 크기의 배열 인덱스로 매핑하는 함수
• 동일한 입력값은 항상 동일한 해시값을 반환해야 함

특징

• 결정성: 동일한 입력에 대해 항상 동일한 해시값 반환
• 해시값은 일반적으로 배열의 인덱스로 사용됨

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

---

⚠️ 충돌(Collision)과 처리 방법

• 서로 다른 키가 동일한 해시 인덱스를 가질 경우 발생
• 이를 해결하기 위해 다양한 충돌 해결 전략이 사용됨

1. 체이닝 (Chaining)

• 각 배열 인덱스가 연결 리스트를 가지며 충돌된 키들을 리스트에 추가
• 공간 낭비는 줄지만, 평균 탐색 시간은 O(n/k)로 느려질 수 있음

2. 선형 탐사 (Linear Probing)

• 충돌 발생 시, 다음 인덱스로 이동하여 빈 자리를 찾는 방법
• 클러스터링 문제 발생 가능

int hash(int key) {
    int index = key % TABLE_SIZE;
    while (table[index] != EMPTY) {
        index = (index + 1) % TABLE_SIZE;
    }
    return index;
}

3. 이차 탐사 (Quadratic Probing)

• 선형이 아닌 제곱 간격으로 이동: index + i^2
• 클러스터링을 완화할 수 있음

4. 더블 해싱 (Double Hashing)

• 두 개의 해시 함수를 사용하여 충돌 시 보조 해시 함수로 재계산
• 가장 효과적인 오픈 어드레싱 방식 중 하나

---

🔁 리사이징 (Resizing)

• 해시 테이블의 크기를 동적으로 늘리는 방법
• 보통 **로드 팩터(load factor)**가 일정 비율 이상이 되면 리사이징 수행
• 리사이징 시 모든 원소를 새로운 해시 테이블로 재해싱(rehash) 해야 함

---

⏱ 시간 복잡도

연산	평균	최악
검색(Search)	O(1)	O(n)
삽입(Insert)	O(1)	O(n)
삭제(Delete)	O(1)	O(n)

• 충돌이 없다면 O(1), 충돌이 많아질수록 O(n)에 가까워짐

---

🟩 장점

• 매우 빠른 검색/삽입/삭제 연산 가능 (평균 O(1))
• 정렬이 필요 없는 환경에서 효율적

🟥 단점

• 메모리 사용량 증가 가능
• 해시 함수 설계가 성능에 결정적
• 충돌 처리 알고리즘이 필요

---

✅ 활용 예시

• 데이터베이스 인덱싱
• 캐시 시스템 (예: LRU Cache)
• 중복 검사 (중복 문자 탐지 등)
• 사전(Dictionary), 집합(Set) 구현

---

✅ 핵심 요약

Hashing은 **규칙성 있는 키 변환 함수(hash function)**와 충돌 대응 전략을 통해 데이터를 빠르고 효율적으로 다루는 자료구조이다.