탐색 - 5. 해싱(Hashing) 기법

📌 5. 해싱(Hashing) 기법

---

5.1 해싱(Hashing)의 개념과 필요성

🔹 해싱(Hashing)이란?

해싱(Hashing)은 데이터를 특정한 키(key)를 기반으로 해시 함수(Hash Function)를 통해 빠르게 검색하는 방법입니다.
해싱 기법은 데이터베이스, 캐싱 시스템, 암호화, 파일 시스템 등 다양한 곳에서 사용됩니다.

💡 해싱의 필요성

• 탐색 속도 향상 → O(1)로 탐색 가능 (이진 탐색 O(log n)보다 빠름)
• 데이터 저장 및 검색이 빠름 → 배열과 달리 특정 값 검색 시 빠르게 접근 가능
• 효율적인 메모리 사용 → 정렬된 배열을 유지할 필요 없이 키를 기반으로 데이터 관리 가능

---

5.2 해시 함수(Hash Function) 및 충돌 해결 방법

🔹 해시 함수(Hash Function)

해시 함수는 입력 값을 특정 크기의 해시 테이블의 인덱스로 변환하는 함수입니다.
해시 함수가 좋은 경우:

• 균등한 해시 값 분포: 데이터가 특정 영역에 몰리지 않도록 설계
• 빠른 계산: 해시 함수 자체가 느리면 해싱의 의미가 사라짐

예제: 간단한 해시 함수 (모듈로 연산)

index = key % table_size;

위 공식은 키(key)를 테이블 크기로 나눈 나머지를 사용하여 인덱스를 생성하는 방식입니다.

---

🔹 충돌 해결 방법

해시 함수가 동일한 해시 값을 반환하면 충돌(Collision)이 발생합니다.
이를 해결하는 대표적인 방법:

1. 체이닝(Chaining) 기법 → 연결 리스트(Linked List)로 동일한 해시 값을 가지는 데이터를 저장
2. 개방 주소법(Open Addressing) → 빈 슬롯을 찾아 데이터를 저장하는 방식

---

5.3 해시 테이블(Hash Table) 구현

해시 테이블(Hash Table)은 배열과 해시 함수를 조합하여 빠르게 데이터를 검색하는 자료구조입니다.

💡 해시 테이블의 기본 구성 요소

1. 해시 함수 → 키를 배열 인덱스로 변환
2. 해시 테이블 → 변환된 인덱스에 데이터를 저장
3. 충돌 해결 기법 → 충돌이 발생할 경우 데이터를 저장하는 방식

---

🔍 실습: 간단한 해시 테이블 구현 (C 언어)

1️⃣ struct와 배열을 이용한 간단한 해시 테이블 구현

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

// 해시 테이블 구조체
typedef struct {
    int key;
    int value;
} HashTable;

// 해시 함수 (키 % 테이블 크기)
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 해시 테이블에 데이터 삽입
void insert(HashTable table[], int key, int value) {
    int index = hashFunction(key);

    while (table[index].key != 0) { // 충돌 발생 시 다음 슬롯으로 이동 (개방 주소법)
        index = (index + 1) % TABLE_SIZE;
    }

    table[index].key = key;
    table[index].value = value;
}

// 해시 테이블에서 값 검색
int search(HashTable table[], int key) {
    int index = hashFunction(key);

    while (table[index].key != 0) {
        if (table[index].key == key) {
            return table[index].value;
        }
        index = (index + 1) % TABLE_SIZE; // 개방 주소법 충돌 해결
    }

    return -1; // 찾지 못한 경우
}

int main() {
    HashTable table[TABLE_SIZE] = {0}; // 초기화

    insert(table, 15, 100);
    insert(table, 25, 200);
    insert(table, 35, 300);

    printf("키 25의 값: %d\n", search(table, 25));
    printf("키 35의 값: %d\n", search(table, 35));
    printf("키 10의 값: %d\n", search(table, 10)); // 존재하지 않는 값

    return 0;
}

📌 실행 결과

키 25의 값: 200
키 35의 값: 300
키 10의 값: -1

💡 개방 주소법(Open Addressing) 방식 사용
충돌이 발생하면 다음 빈 슬롯을 찾아 이동하면서 데이터를 저장하는 방식입니다.

---

🔍 실습: 충돌 해결을 위한 체이닝(Chaining) 기법 적용

개방 주소법 대신 체이닝(Chaining)을 이용하여 연결 리스트(Linked List)로 충돌을 해결할 수도 있습니다.

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

// 연결 리스트 노드 구조체
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

// 해시 테이블 (배열 + 연결 리스트)
Node* hashTable[TABLE_SIZE] = {NULL};

// 해시 함수
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 해시 테이블에 데이터 삽입 (체이닝 방식)
void insert(int key, int value) {
    int index = hashFunction(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 해시 테이블에서 값 검색
int search(int key) {
    int index = hashFunction(key);
    Node* current = hashTable[index];

    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }

    return -1; // 찾지 못한 경우
}

// 해시 테이블 출력
void printTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("[%d]: ", i);
        Node* current = hashTable[i];
        while (current != NULL) {
            printf("(%d, %d) -> ", current->key, current->value);
            current = current->next;
        }
        printf("NULL\n");
    }
}

// 메모리 해제
void freeTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node* current = hashTable[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
}

int main() {
    insert(15, 100);
    insert(25, 200);
    insert(35, 300);
    insert(45, 400); // 충돌 발생

    printf("키 25의 값: %d\n", search(25));
    printf("키 45의 값: %d\n", search(45));
    printf("키 10의 값: %d\n", search(10));

    printTable(); // 해시 테이블 출력
    freeTable();  // 메모리 해제

    return 0;
}

📌 실행 결과

키 25의 값: 200
키 45의 값: 400
키 10의 값: -1
[0]: NULL
[1]: NULL
[2]: NULL
[3]: NULL
[4]: NULL
[5]: (45, 400) -> (35, 300) -> (25, 200) -> (15, 100) -> NULL
...

💡 체이닝 방식 → 해시 충돌이 발생하면 연결 리스트에 데이터를 추가하여 해결

---

📌 마무리 및 정리

• 해싱(Hashing)은 키를 해시 함수로 변환하여 데이터를 빠르게 검색하는 기법
• 해시 함수(Hash Function)는 키를 인덱스로 변환하는 함수
• 충돌 해결 방법
  1. 개방 주소법(Open Addressing) → 충돌 시 다음 빈 슬롯 찾기
  2. 체이닝(Chaining) → 연결 리스트를 이용하여 충돌 해결
• C에서 해시 테이블 구현 방법
  • struct와 배열을 이용한 기본 해시 테이블
  • 연결 리스트(Chaining) 기법 적용하여 충돌 해결