[C언어] 기초 자료구조 - 해시(Hash)

c언어

---

1. 해시(Hash)란?

• 해시는 키(Key)를 기반으로 데이터를 저장하고 검색하는 데 사용되는 자료구조. 해싱(Hashing)기법을 통해 키를 해시 함수(Hash Function)로 처리하여 고유한 해시 값(Hash Value)을 생성.
• 특징
  1. 데이터의 삽입, 삭제, 검색을 O(1) 시간 복잡도로 처리
  2. 동일한 해시 값이 발생할 경우 충돌(Collision)이 발생할 수 있음
• 활용 사례
  1. 데이터베이스 인덱싱
  2. 캐싱
  3. 암호화 알고리즘
  4. 집합(Set)과 맵(Map) 구현

---

2. 해시 테이블(Hash Table)의 구조

• 키(Key): 고유한 값(문자열, 정수 등).
• 해시 함수(Hash Function)
  • 키를 일정 범위의 정수로 변환.
  • 예: hash(key) = key % table_size
• 해시 테이블
  • 배열 기반 자료구조로, 해시 값을 인덱스로 사용하여 데이터 저장
• 충돌 처리
  • 체이닝(Chaining): 같은 해시 값의 데이터를 연결 리스트로 저장.
  • 오픈 어드레싱(Open Addressing): 빈 공간을 찾아 데이터를 저장.

---

3. 해시 함수

해시 함수는 다음 속성을 만족해야 합니다.

• 빠르고 효율적 - 계산이 빠르며 일정한 시간 내에 완료.
• 고유성 유지 - 서로 다른 키는 가능한 한 다른 해시 값을 가져와야함.
• 충돌 최소화: 같은 해시 값이 생성되는 경우를 줄여야 함.
• 예시 - 모듈로연산

int hashFunction(int key, int tableSize) {
    return key % tableSize;
}

---

4. 체이닝(Chaining)을 사용한 해시 테이블 구현

체이닝은 충돌이 발생한 데이터를 연결 리스트로 저장하는 방식

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

#define TABLE_SIZE 10

// 노드 구조체 정의
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

// 해시 테이블 배열 정의
Node* hashTable[TABLE_SIZE];

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

// 데이터 삽입
void insert(int key, int value) {
    int hashIndex = hashFunction(key);

    // 새 노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;

    // 체이닝 처리
    if (hashTable[hashIndex] == NULL) {
        hashTable[hashIndex] = newNode;
    } else {
        Node* temp = hashTable[hashIndex];
        while (temp->next != NULL) {
            if (temp->key == key) {
                // 키가 이미 존재하면 업데이트
                temp->value = value;
                free(newNode);
                return;
            }
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 데이터 검색
int search(int key) {
    int hashIndex = hashFunction(key);
    Node* temp = hashTable[hashIndex];

    while (temp != NULL) {
        if (temp->key == key) {
            return temp->value;
        }
        temp = temp->next;
    }
    return -1; // 키가 존재하지 않음
}

// 데이터 삭제
void delete(int key) {
    int hashIndex = hashFunction(key);
    Node* temp = hashTable[hashIndex];
    Node* prev = NULL;

    while (temp != NULL) {
        if (temp->key == key) {
            if (prev == NULL) {
                hashTable[hashIndex] = temp->next;
            } else {
                prev->next = temp->next;
            }
            free(temp);
            printf("키 %d 삭제 완료\n", key);
            return;
        }
        prev = temp;
        temp = temp->next;
    }
    printf("키 %d를 찾을 수 없습니다.\n", key);
}

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

int main() {
    insert(1, 10);
    insert(2, 20);
    insert(11, 30); // 충돌 처리
    insert(21, 40); // 충돌 처리

    printHashTable();

    printf("키 11의 값: %d\n", search(11)); // 30 출력
    delete(11);
    printHashTable();

    return 0;
}

---

5. 오픈 어드레싱(Open Addressing)을 사용한 해시 테이블

오픈 어드레싱은 충돌 발생 시 해시 테이블의 빈 공간을 찾아 데이터를 저장하는 방식

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

#define TABLE_SIZE 10
#define EMPTY -1

typedef struct {
    int key;
    int value;
} Entry;

Entry hashTable[TABLE_SIZE];

// 초기화
void initHashTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i].key = EMPTY;
    }
}

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

// 데이터 삽입
void insert(int key, int value) {
    int hashIndex = hashFunction(key);
    while (hashTable[hashIndex].key != EMPTY) {
        hashIndex = (hashIndex + 1) % TABLE_SIZE;
    }
    hashTable[hashIndex].key = key;
    hashTable[hashIndex].value = value;
}

// 데이터 검색
int search(int key) {
    int hashIndex = hashFunction(key);
    int startIndex = hashIndex;

    while (hashTable[hashIndex].key != EMPTY) {
        if (hashTable[hashIndex].key == key) {
            return hashTable[hashIndex].value;
        }
        hashIndex = (hashIndex + 1) % TABLE_SIZE;
        if (hashIndex == startIndex) break; // 원래 위치로 돌아오면 검색 실패
    }
    return -1;
}

// 데이터 삭제
void delete(int key) {
    int hashIndex = hashFunction(key);
    int startIndex = hashIndex;

    while (hashTable[hashIndex].key != EMPTY) {
        if (hashTable[hashIndex].key == key) {
            hashTable[hashIndex].key = EMPTY;
            printf("키 %d 삭제 완료\n", key);
            return;
        }
        hashIndex = (hashIndex + 1) % TABLE_SIZE;
        if (hashIndex == startIndex) break;
    }
    printf("키 %d를 찾을 수 없습니다.\n", key);
}

// 해시 테이블 출력
void printHashTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (hashTable[i].key != EMPTY) {
            printf("[%d]: (%d, %d)\n", i, hashTable[i].key, hashTable[i].value);
        } else {
            printf("[%d]: EMPTY\n", i);
        }
    }
}

int main() {
    initHashTable();

    insert(1, 10);
    insert(2, 20);
    insert(11, 30); // 충돌 처리
    insert(21, 40); // 충돌 처리

    printHashTable();

    printf("키 11의 값: %d\n", search(11)); // 30 출력
    delete(11);
    printHashTable();

    return 0;
}

---

6. 해시 테이블의 장단점

• 장점
  • 데이터 삽입, 검색, 삭제가 O(1) 시간복잡도
  • 키와 값의 직접 매핑 가능
• 단점
  • 충돌 발생 가능
  • 효율적인 해시 함수 설계가 중요
  • 테이블 크기 고정 시 오버플로우 발생 가능