해시 테이블[ Hash Table ] 및 해싱 [ Hashing ]

해시 테이블은 효율적으로 데이터를 저장하고 검색하는 자료 구조입니다. 해싱은 데이터를 해시 함수를 사용해 특정 위치에 매핑하여 저장하는 기법을 말합니다. 이 포스팅에서는 해시 테이블의 기본 개념과 해싱 방법, 그리고 Java와 C로 해시 테이블을 구현하는 방법을 설명합니다.

1. 해시 테이블이란?

해시 테이블(Hash Table)은 키-값 쌍을 저장하는 자료 구조로, 데이터를 빠르게 검색할 수 있도록 설계되었습니다. 키 값을 해시 함수(Hash Function)에 넣어 해시 값을 생성하고, 이 값을 인덱스로 사용하여 배열 형태의 메모리에 데이터를 저장합니다. 이러한 방식 덕분에 해시 테이블은 평균적으로 O(1)의 시간 복잡도로 데이터를 삽입하고 검색할 수 있습니다.

해시 테이블의 주요 구성 요소

• 해시 함수(Hash Function): 입력된 키 값을 해시 값으로 변환하는 함수입니다. 해시 값은 일반적으로 배열의 인덱스로 사용됩니다.
• 충돌(Collision): 서로 다른 키가 같은 해시 값을 가질 때 발생합니다. 충돌을 처리하는 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있습니다.
• 버킷(Bucket): 데이터를 저장하는 장소입니다. 충돌을 해결하기 위해 버킷이 리스트 형태로 구성되기도 합니다.

2. 해시 함수

해시 함수는 임의의 크기의 데이터를 고정된 크기의 해시 값으로 매핑합니다. 좋은 해시 함수는 키를 균등하게 분포시키며, 충돌 가능성을 최소화하는 특성이 있습니다. 예를 들어, 숫자 키에 대해 간단한 해시 함수를 사용한다면 다음과 같이 작성할 수 있습니다.

int hash(int key, int size) {
    return key % size;
}

3. 충돌 해결 방법

해시 테이블에서 충돌이 발생하는 것은 피할 수 없으므로, 이를 해결하기 위한 방법들이 필요합니다. 대표적인 충돌 해결 방법은 다음과 같습니다.

3.1 체이닝 (Chaining)

체이닝은 각 버킷에 연결 리스트를 사용하여 동일한 해시 값을 가지는 여러 개의 요소를 저장하는 방법입니다.

3.2 개방 주소법 (Open Addressing)

개방 주소법은 충돌이 발생할 경우 다른 빈 버킷을 찾아 데이터를 저장하는 방법입니다. 대표적인 개방 주소법의 예로는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있습니다.

4. 해시 테이블 구현 (Java)

아래는 Java를 사용해 체이닝을 이용한 간단한 해시 테이블을 구현한 예제입니다.

import java.util.LinkedList;

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

    static class Entry {
        int key;
        String value;

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

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

    private int hash(int key) {
        return key % size;
    }

    public void put(int key, String value) {
        int hashValue = hash(key);
        for (Entry entry : table[hashValue]) {
            if (entry.key == key) {
                entry.value = value;
                return;
            }
        }
        table[hashValue].add(new Entry(key, value));
    }

    public String get(int key) {
        int hashValue = hash(key);
        for (Entry entry : table[hashValue]) {
            if (entry.key == key) {
                return entry.value;
            }
        }
        return null;
    }
}

public class Main {
    public static void main(String[] args) {
        HashTable hashTable = new HashTable(10);
        hashTable.put(1, "One");
        hashTable.put(2, "Two");
        hashTable.put(11, "Eleven");

        System.out.println(hashTable.get(1));   // 출력: One
        System.out.println(hashTable.get(11));  // 출력: Eleven
        System.out.println(hashTable.get(3));   // 출력: null
    }
}

위 예제에서는 해시 테이블을 배열로 구현하고, 각 배열의 요소는 연결 리스트입니다. 충돌이 발생할 때 같은 버킷에 여러 항목을 저장할 수 있도록 하였습니다.

5. 해시 테이블 구현 (C)

C 언어를 사용해 체이닝을 이용한 해시 테이블을 구현한 예제는 다음과 같습니다.

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

#define TABLE_SIZE 10

typedef struct Entry {
    int key;
    char value[100];
    struct Entry* next;
} Entry;

Entry* table[TABLE_SIZE];

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

void put(int key, const char* value) {
    unsigned int hashValue = hash(key);
    Entry* newEntry = (Entry*)malloc(sizeof(Entry));
    newEntry->key = key;
    strcpy(newEntry->value, value);
    newEntry->next = NULL;

    if (table[hashValue] == NULL) {
        table[hashValue] = newEntry;
    } else {
        Entry* current = table[hashValue];
        while (current->next != NULL) {
            if (current->key == key) {
                strcpy(current->value, value);
                free(newEntry);
                return;
            }
            current = current->next;
        }
        current->next = newEntry;
    }
}

char* get(int key) {
    unsigned int hashValue = hash(key);
    Entry* current = table[hashValue];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return NULL;
}

int main() {
    put(1, "One");
    put(2, "Two");
    put(11, "Eleven");

    printf("%s\n", get(1));   // 출력: One
    printf("%s\n", get(11));  // 출력: Eleven
    printf("%s\n", get(3));   // 출력: (null)

    return 0;
}

위 예제에서는 C 언어로 연결 리스트를 이용해 해시 테이블을 구현했습니다. put() 함수는 새로운 키-값 쌍을 삽입하고, get() 함수는 특정 키에 대한 값을 검색합니다.

6. 해시 테이블의 시간 복잡도

해시 테이블의 평균적인 시간 복잡도는 다음과 같습니다.

• 삽입(Insertion): O(1)
• 삭제(Deletion): O(1)
• 검색(Lookup): O(1)

하지만, 충돌이 많이 발생하거나 해시 함수가 효율적이지 않으면 최악의 경우 시간 복잡도는 O(n)이 될 수 있습니다. 따라서, 좋은 해시 함수와 충돌 해결 방법을 선택하는 것이 중요합니다.

7. 결론

해시 테이블은 효율적인 데이터 저장 및 검색을 위한 강력한 자료 구조입니다. 그러나 충돌 문제와 메모리 사용에 대한 고려가 필요합니다. Java와 C를 사용한 구현 예제를 통해 해시 테이블의 기본 개념을 이해하고, 이를 실제로 활용할 수 있는 방법을 배웠습니다. 좋은 해시 함수를 설계하고, 적절한 충돌 해결 방법을 적용하는 것이 해시 테이블의 성능을 최적화하는 데 중요합니다.