해시(Hash), 해시 자료 구조, 해시 충돌 및 완화 방법

1. 해시(Hash)란?

해시(Hash)는 임의의 데이터를 고정된 길이의 값으로 변환하는 과정을 의미합니다.
이때 사용되는 변환 함수가 해시 함수(Hash Function) 입니다.

✔ 특징

• 고속 데이터 검색: O(1) 또는 O(N/k) 수준의 빠른 검색 성능.
• 고정된 크기의 해시 값(Hash Value) 생성.
• 동일한 입력 → 동일한 해시 값을 생성 (결정론적).
• 다른 입력 → 다른 해시 값이 될 확률이 높아야 함.
• 역변환이 어려움(단방향 함수).

✔ 사용 예시

• 비밀번호 저장 (SHA-256, bcrypt)
• 데이터 무결성 검증 (MD5, SHA)
• 블록체인, 암호화
• 해시 테이블(Hash Table) 기반 데이터 저장 및 검색

---

2. 해시 자료 구조(Hash Data Structure)

2.1 해시 테이블(Hash Table)

해시 테이블은 Key-Value 형태로 데이터를 저장하는 자료구조입니다.
해시 함수(Hash Function)를 이용하여 키를 해시 값으로 변환한 후, 배열의 인덱스로 매핑하여 빠르게 데이터를 저장하고 검색할 수 있습니다.

✔ 구조

해시 함수(Key) → 해시 값(Index) → 해시 테이블(배열)에서 데이터 저장

✔ 해시 테이블 예시 (java Dictionary)

import java.util.HashMap;
import java.util.Map;

public class HashTableExample {
    public static void main(String[] args) {
        // HashMap을 사용하여 해시 테이블 구현
        Map<String, Object> hashTable = new HashMap<>();

        // 데이터 삽입
        hashTable.put("name", "Alice");
        hashTable.put("age", 25);

        // 데이터 조회
        System.out.println("name: " + hashTable.get("name")); // Alice
        System.out.println("age: " + hashTable.get("age"));   // 25

        // 데이터 삭제
        hashTable.remove("age");
        System.out.println("age after removal: " + hashTable.get("age")); // null

        // 모든 키-값 출력
        for (Map.Entry<String, Object> entry : hashTable.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

• "name" 키는 해시 함수에 의해 특정 인덱스로 변환되어 저장됨.
• 검색 시 해시 값을 기반으로 즉시 찾을 수 있어 빠름(O(1)).

---

2.2 해시 함수(Hash Function)

해시 함수는 입력(Key)을 일정한 크기의 해시 값(Index)으로 변환하는 함수입니다.

✔ 좋은 해시 함수의 조건
1. 충돌(Collision)이 적어야 함: 다른 키가 같은 해시 값으로 변환되지 않아야 함.
2. 고른 분포(Uniformity): 해시 값이 특정 범위에 몰리지 않고 고르게 분포해야 함.
3. 빠른 계산 속도: O(1) 수준으로 해시 값을 생성해야 함.

✔ 대표적인 해시 함수

• 나머지 연산법 (Modulo Hashing): h(x) = x % N
• 비트 연산(Hash Mixing): x ^ (x >> shift)
• Cryptographic Hash (SHA-256, MD5 등): 암호화 목적으로 사용.

---

3. 해시 충돌(Hash Collision)

해시 충돌은 서로 다른 입력값이 동일한 해시 값을 갖게 되는 문제입니다.
해시 함수의 출력 범위가 제한적이므로 어떤 해시 함수라도 충돌이 발생할 수밖에 없음.

✔ 충돌 예시

h("apple") = 3
h("banana") = 3  # 충돌 발생!

• "apple"과 "banana"가 같은 해시 값을 가짐 → 해시 충돌 발생

---

4. 해시 충돌 완화 방법

해시 충돌을 해결하는 대표적인 방법에는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다.

4.1 체이닝(Chaining)

해시 테이블의 각 슬롯(버킷)에 연결 리스트(Linked List)를 사용하여 여러 개의 키-값을 저장하는 방식.

✔ 구조

Index  0  →  (key1, value1) → (key2, value2) → ...
Index  1  →  (key3, value3) → (key4, value4) → ...

✔ 장점

• 충돌이 많아도 저장 가능.
• 테이블 크기를 미리 크게 잡을 필요 없음.

✔ 단점

• 연결 리스트를 탐색해야 하므로 최악의 경우 O(N) 성능.

✔ 체이닝 방식 해시 테이블 구현 (Java)

import java.util.LinkedList;

class ChainingHashTable {
    private int size;
    private LinkedList<Entry>[] table;

    static class Entry {
        String key;
        String value;

        public Entry(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public ChainingHashTable(int size) {
        this.size = size;
        table = new LinkedList[size];
        for (int i = 0; i < size; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int hashFunction(String key) {
        return Math.abs(key.hashCode()) % size;
    }

    public void put(String key, String value) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value; // 기존 값 업데이트
                return;
            }
        }
        table[index].add(new Entry(key, value)); // 새로운 데이터 추가
    }

    public String get(String key) {
        int index = hashFunction(key);
        for (Entry entry : table[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null; // 데이터가 존재하지 않음
    }

    public void remove(String key) {
        int index = hashFunction(key);
        table[index].removeIf(entry -> entry.key.equals(key));
    }

    public static void main(String[] args) {
        ChainingHashTable hashTable = new ChainingHashTable(10);
        hashTable.put("name", "Alice");
        hashTable.put("age", "25");
        System.out.println("name: " + hashTable.get("name")); // Alice
        System.out.println("age: " + hashTable.get("age"));   // 25

        hashTable.remove("name");
        System.out.println("name after removal: " + hashTable.get("name")); // null
    }
}

---

4.2 개방 주소법(Open Addressing)

충돌이 발생하면 다른 빈 슬롯을 찾아 저장하는 방법입니다.
체이닝과 달리 추가적인 연결 리스트 없이 배열 내에서 해결.

✔ 탐색 방식
1. 선형 탐사(Linear Probing): h(key) + i % N

• 순차적으로 다음 빈 슬롯을 찾음.

2. 이차 탐사(Quadratic Probing): h(key) + i² % N
   • 충돌 발생 시, i²씩 증가하며 탐색.
3. 이중 해싱(Double Hashing): h1(key) + i * h2(key) % N
   • 두 개의 해시 함수를 사용하여 충돌을 분산.

✔ 장점

• 연결 리스트 사용 없이 저장 공간 절약.

✔ 단점

• 충돌이 많으면 클러스터링(Clustering) 문제 발생 → 성능 저하.

✔ 개방 주소법 해시 테이블 구현 (Java)

import java.util.Arrays;

class OpenAddressingHashTable {
    private int size;
    private Entry[] table;
    private static final Entry DELETED = new Entry(null, null); // 삭제된 자리 표시

    static class Entry {
        String key;
        String value;

        public Entry(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public OpenAddressingHashTable(int size) {
        this.size = size;
        table = new Entry[size];
    }

    private int hashFunction(String key) {
        return Math.abs(key.hashCode()) % size;
    }

    public void put(String key, String value) {
        int index = hashFunction(key);
        int originalIndex = index;

        while (table[index] != null && table[index] != DELETED) {
            if (table[index].key.equals(key)) {
                table[index].value = value; // 기존 값 업데이트
                return;
            }
            index = (index + 1) % size; // 선형 탐사(Linear Probing)
            if (index == originalIndex) return; // 테이블이 꽉 참
        }
        table[index] = new Entry(key, value);
    }

    public String get(String key) {
        int index = hashFunction(key);
        int originalIndex = index;

        while (table[index] != null) {
            if (table[index] != DELETED && table[index].key.equals(key)) {
                return table[index].value;
            }
            index = (index + 1) % size;
            if (index == originalIndex) break;
        }
        return null;
    }

    public void remove(String key) {
        int index = hashFunction(key);
        int originalIndex = index;

        while (table[index] != null) {
            if (table[index] != DELETED && table[index].key.equals(key)) {
                table[index] = DELETED; // 삭제된 자리 표시
                return;
            }
            index = (index + 1) % size;
            if (index == originalIndex) break;
        }
    }

    public void printTable() {
        System.out.println(Arrays.toString(table));
    }

    public static void main(String[] args) {
        OpenAddressingHashTable hashTable = new OpenAddressingHashTable(10);
        hashTable.put("name", "Bob");
        hashTable.put("age", "30");

        System.out.println("name: " + hashTable.get("name")); // Bob
        System.out.println("age: " + hashTable.get("age"));   // 30

        hashTable.remove("name");
        System.out.println("name after removal: " + hashTable.get("name")); // null
    }
}

---

5. 체이닝 vs 개방 주소법 비교

비교 항목	체이닝 (Chaining)	개방 주소법 (Open Addressing)
충돌 해결 방식	연결 리스트로 해결	빈 슬롯을 찾아 저장
저장 공간 사용	추가적인 연결 리스트 필요	테이블 크기 내에서 해결
성능(O)	평균 O(1), 최악 O(N)	평균 O(1), 최악 O(N)
삭제 처리	간단히 노드 삭제	삭제 후 탐사 필요(클러스터링 문제)
장점	많은 데이터 저장 가능, 공간 활용 효율적	추가적인 연결 리스트 필요 없음
단점	연결 리스트 관리 필요	충돌이 많으면 탐색 성능 저하

---

6. 해시 자료 구조의 활용 사례

✔ 빠른 검색과 조회

• 해시 테이블을 사용하여 O(1) 성능의 데이터 조회 제공.

✔ 데이터 중복 검사

• 해시 값을 활용하여 중복된 데이터 탐지 가능(예: 이미지 해시, Bloom Filter).

✔ 캐싱(Cache)

• LRU(Least Recently Used) 캐시, DNS 캐시 등 빠른 데이터 조회 용도로 활용.

✔ 블록체인 및 암호화

• 블록체인에서 SHA-256 해시를 사용하여 데이터 변조를 방지.

---

7. 결론

✅ 해시(Hash)는 데이터를 고정된 길이로 변환하는 방식으로, 빠른 검색을 위해 사용됨.
✅ 해시 테이블(Hash Table)은 Key-Value 구조를 가지며, O(1) 성능으로 데이터 검색이 가능.
✅ 해시 충돌은 불가피하며, 체이닝(Chaining)과 개방 주소법(Open Addressing)으로 해결 가능.
✅ 웹 서비스, 데이터베이스, 블록체인 등 다양한 분야에서 해시 자료구조가 활용됨.

---

추가 학습 자료

• [10분 테코톡] 👩‍🏫코니의 #️⃣Hash Function
• [NAVER - D2] Java HashMap은 어떻게 동작하는가?
• [IT 기술면접 준비자료] 해시(Hash)와 해시충돌(Hash Collision)