자료구조: 해시테이블(Hash Table)

해시테이블은 효율적인 데이터 저장과 검색을 위해 해시 함수를 사용하여 키(key)를 해시값(hash value)으로 변환하고, 이를 통해 데이터의 위치를 결정하는 자료구조입니다. 해시맵과 해시테이블은 개념적으로 유사하지만, 구현 방식과 충돌 해결 방법에 따라 차이가 있습니다. 이번 글에서는 해시테이블의 기본 개념부터 다양한 충돌 해결 방법까지 자세히 알아보겠습니다.

hash table

---

해시테이블이란?

해시테이블(Hash Table)은 키를 해시 함수로 해시값으로 변환하고, 이 해시값을 인덱스로 사용하여 데이터를 저장하는 자료구조입니다. 이를 통해 평균적으로 O(1)의 시간 복잡도로 데이터에 접근할 수 있습니다. 그러나 해시 함수의 성능과 충돌 해결 방법에 따라 실제 성능은 달라질 수 있습니다.

해시테이블의 동작 원리

해시테이블의 동작 원리를 이해하기 위해 필요한 주요 용어와 개념은 다음과 같습니다.

해시 함수(Hash Function): 키를 입력받아 해시값을 생성하는 함수입니다. 해시 함수는 키를 해시테이블의 인덱스로 매핑하는 역할을 합니다.

해시값(Hash Value): 해시 함수의 결과로 얻은 정수 값입니다. 이 값은 해시테이블 내에서 데이터가 저장될 위치를 결정합니다.

인덱스(Index): 해시값을 해시테이블의 크기로 나눈 나머지 값을 사용하여 실제 데이터가 저장될 위치를 결정합니다.

버킷(Bucket): 해시테이블의 각 인덱스 위치로, 데이터를 저장하는 공간입니다.

노드(Node): 버킷에 저장되는 실제 데이터로, 키와 값의 쌍으로 이루어져 있습니다.

충돌(Collision): 서로 다른 키들이 동일한 해시값을 갖게 되는 현상입니다. 해시 함수의 특성상 충돌은 불가피하며, 이를 해결하기 위한 방법이 필요합니다.

로드 팩터(Load Factor): 해시테이블이 얼마나 채워져 있는지를 나타내는 값으로, 해시테이블의 성능에 영향을 미칩니다.

리사이징(Resizing): 로드 팩터가 일정 수준을 넘으면 해시테이블의 크기를 늘려 성능을 유지합니다.

 

충돌 해결 방법

충돌이 발생했을 때 이를 해결하는 방법은 크게 두 가지로 나뉩니다: **체이닝(Chaining)**과 오픈 어드레싱(Open Addressing).

체이닝(Chaining)

• 개념: 각 버킷에 연결 리스트나 다른 자료구조를 사용하여 여러 노드를 저장합니다.
• 장점: 해시테이블의 크기에 제한이 없으며, 동적으로 확장 가능합니다.
• 단점: 해시 함수가 나쁘거나 로드 팩터가 높으면 성능이 저하될 수 있습니다.

구조

Bucket 0: -> Node(key1, value1) -> Node(key2, value2)
Bucket 1: -> Node(key3, value3)
Bucket 2: -> null
...

오픈 어드레싱(Open Addressing)

• 개념: 충돌이 발생하면 해시테이블 내에서 빈 버킷을 찾아 데이터를 저장합니다.
• 장점: 추가적인 메모리 사용이 없으며, 캐시 효율이 좋습니다.
• 단점: 로드 팩터가 높아지면 충돌이 빈번해져 성능이 저하됩니다.

오픈 어드레싱에는 여러 가지 탐사 방법이 있습니다.

선형 탐사(Linear Probing)

• 방법: 충돌이 발생하면 한 칸씩 이동하여 빈 버킷을 찾습니다.
• 탐사 함수:

• 장점: 구현이 간단합니다.
• 단점: 클러스터링(Clustering) 문제가 발생하여 성능이 저하될 수 있습니다.

제곱 탐사(Quadratic Probing)

• 방법: 탐사 간격이 제곱 수로 증가합니다.
• 탐사 함수:

• 장점: 클러스터링 문제가 완화됩니다.
• 단점: 테이블의 크기가 소수(prime number)가 아니면 모든 버킷을 탐색하지 못할 수 있습니다.

이중 해싱(Double Hashing)

• 방법: 두 번째 해시 함수를 사용하여 탐사 간격을 결정합니다.

• 탐사 함수:

• 장점: 클러스터링 문제가 최소화됩니다.
• 단점: 해시 함수 두 개를 계산해야 하므로 오버헤드가 있습니다.

해시테이블의 활용 예시

1. 어휘 분석기(Lexical Analyzer): 컴파일러에서 토큰을 식별하고 저장하는 데 사용됩니다.
2. 데이터베이스 인덱스: 대용량 데이터에서 키를 기반으로 빠르게 레코드를 검색합니다.
3. 캐시(Cache) 시스템: 최근에 사용된 데이터를 저장하여 접근 속도를 향상시킵니다.
4. 기록 시스템(Log System): 이벤트나 오류 메시지를 키로 분류하여 저장합니다.
5. 네트워크 라우팅 테이블: IP 주소를 키로 하여 해당 경로 정보를 저장합니다.
6. 게임 개발: 게임 오브젝트의 상태나 속성을 관리합니다.
7. 중복 제거 시스템: 대량의 데이터에서 중복된 항목을 빠르게 식별하고 제거합니다.

쉬운 예시로 이해하기

도서관의 책 관리

도서관에서 책을 관리한다고 가정해봅시다. 각 책에는 고유한 ISBN 번호(키)가 있습니다.

• 해시 함수 사용: ISBN 번호를 해시 함수에 입력하여 해시값을 생성합니다.
• 버킷에 저장: 생성된 해시값을 인덱스로 사용하여 해당 버킷에 책 정보를 저장합니다.
• 충돌 발생 시: 다른 책이 동일한 해시값을 가질 수 있습니다. 이때 충돌 해결 방법을 사용하여 책을 저장합니다.
  • 체이닝: 해당 버킷에 연결 리스트로 책 정보를 추가합니다.
  • 오픈 어드레싱: 다른 빈 버킷을 찾아 책 정보를 저장합니다.

코드 예제

Golang으로 체이닝 해시테이블 구현하기

package main

import (
    "fmt"
)

type HashNode struct {
    key   string
    value int
    next  *HashNode
}

type HashTable struct {
    buckets []*HashNode
    size    int
}

// Constructor
func NewHashTable(size int) *HashTable {
    buckets := make([]*HashNode, size)
    return &HashTable{buckets: buckets, size: size}
}

// Hash function
func (h *HashTable) getBucketIndex(key string) int {
    hash := 0
    for i := 0; i < len(key); i++ {
        hash = (31*hash + int(key[i])) % h.size
    }
    return hash
}

// Put method
func (h *HashTable) Put(key string, value int) {
    index := h.getBucketIndex(key)
    head := h.buckets[index]

    // Update if key exists
    for node := head; node != nil; node = node.next {
        if node.key == key {
            node.value = value
            return
        }
    }

    // Insert new node
    newNode := &HashNode{key: key, value: value, next: head}
    h.buckets[index] = newNode
}

// Get method
func (h *HashTable) Get(key string) (int, bool) {
    index := h.getBucketIndex(key)
    head := h.buckets[index]

    for node := head; node != nil; node = node.next {
        if node.key == key {
            return node.value, true
        }
    }

    return 0, false // Key not found
}

// Remove method
func (h *HashTable) Remove(key string) {
    index := h.getBucketIndex(key)
    head := h.buckets[index]
    var prev *HashNode

    for node := head; node != nil; node = node.next {
        if node.key == key {
            if prev != nil {
                prev.next = node.next
            } else {
                h.buckets[index] = node.next
            }
            return
        }
        prev = node
    }
}

// 사용 예시
func main() {
    hashTable := NewHashTable(10)

    hashTable.Put("Alice", 1234)
    hashTable.Put("Bob", 5678)

    if value, ok := hashTable.Get("Alice"); ok {
        fmt.Println("Alice's number:", value)
    }

    hashTable.Remove("Bob")

    if _, ok := hashTable.Get("Bob"); !ok {
        fmt.Println("Bob's number not found")
    }
}

 

• 명시: 이 코드는 체이닝(Chaining) 방법을 사용하여 충돌을 해결하는 해시테이블입니다.
• 이유: 각 버킷에 연결 리스트를 사용하여 여러 노드를 저장함으로써 충돌을 해결합니다.

Java로 체이닝 해시테이블 구현하기

import java.util.LinkedList;

class HashNode<K, V> {
    K key;
    V value;

    // Constructor
    public HashNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

public class ChainingHashTable<K, V> {
    private LinkedList<HashNode<K, V>>[] bucketArray;
    private int numBuckets;

    // Constructor
    public ChainingHashTable() {
        numBuckets = 10;
        bucketArray = new LinkedList[numBuckets];

        // Initialize buckets
        for (int i = 0; i < numBuckets; i++) {
            bucketArray[i] = new LinkedList<>();
        }
    }

    // Hash function
    private int getBucketIndex(K key) {
        int hashCode = key.hashCode();
        int index = Math.abs(hashCode % numBuckets);
        return index;
    }

    // Put method
    public void put(K key, V value) {
        int index = getBucketIndex(key);
        LinkedList<HashNode<K, V>> chain = bucketArray[index];

        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                node.value = value; // Update value
                return;
            }
        }

        // Insert new node
        chain.add(new HashNode<>(key, value));
    }

    // Get method
    public V get(K key) {
        int index = getBucketIndex(key);
        LinkedList<HashNode<K, V>> chain = bucketArray[index];

        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                return node.value;
            }
        }

        return null; // Key not found
    }

    // Remove method
    public V remove(K key) {
        int index = getBucketIndex(key);
        LinkedList<HashNode<K, V>> chain = bucketArray[index];

        for (HashNode<K, V> node : chain) {
            if (node.key.equals(key)) {
                V value = node.value;
                chain.remove(node);
                return value;
            }
        }

        return null; // Key not found
    }
}

// 사용 예시
public class Main {
    public static void main(String[] args) {
        ChainingHashTable<String, Integer> hashTable = new ChainingHashTable<>();

        hashTable.put("Alice", 1234);
        hashTable.put("Bob", 5678);

        System.out.println("Alice's number: " + hashTable.get("Alice"));

        hashTable.remove("Bob");

        System.out.println("Bob's number: " + hashTable.get("Bob")); // null 출력
    }
}

 

 

• 명시: 이 코드는 체이닝(Chaining) 방법을 사용하여 충돌을 해결하는 해시테이블입니다.
• 이유: 각 버킷에 LinkedList를 사용하여 여러 노드를 저장함으로써 충돌을 해결합니다.

Golang으로 오픈 어드레싱 해시테이블 구현하기

package main

import (
    "fmt"
)

type Entry struct {
    key       string
    value     int
    isDeleted bool
}

type HashTable struct {
    table []*Entry
    size  int
}

func NewHashTable(size int) *HashTable {
    table := make([]*Entry, size)
    return &HashTable{table: table, size: size}
}

// Hash function
func (h *HashTable) hash(key string, i int) int {
    hash := 0
    for _, ch := range key {
        hash = (31*hash + int(ch)) % h.size
    }
    return (hash + i) % h.size // 선형 탐사 사용
}

// Put method
func (h *HashTable) Put(key string, value int) {
    for i := 0; i < h.size; i++ {
        index := h.hash(key, i)
        entry := h.table[index]

        if entry == nil || entry.isDeleted {
            h.table[index] = &Entry{key: key, value: value}
            return
        } else if entry.key == key {
            entry.value = value // Update value
            return
        }
    }

    // 테이블이 가득 찼을 때 리사이징 필요
    h.resize()
    h.Put(key, value)
}

// Get method
func (h *HashTable) Get(key string) (int, bool) {
    for i := 0; i < h.size; i++ {
        index := h.hash(key, i)
        entry := h.table[index]

        if entry == nil {
            return 0, false
        } else if !entry.isDeleted && entry.key == key {
            return entry.value, true
        }
    }
    return 0, false // Key not found
}

// Remove method
func (h *HashTable) Remove(key string) {
    for i := 0; i < h.size; i++ {
        index := h.hash(key, i)
        entry := h.table[index]

        if entry == nil {
            return
        } else if !entry.isDeleted && entry.key == key {
            entry.isDeleted = true
            return
        }
    }
}

// Resize method
func (h *HashTable) resize() {
    oldTable := h.table
    h.size *= 2
    h.table = make([]*Entry, h.size)

    for _, entry := range oldTable {
        if entry != nil && !entry.isDeleted {
            h.Put(entry.key, entry.value)
        }
    }
}

// 사용 예시
func main() {
    hashTable := NewHashTable(10)

    hashTable.Put("Alice", 1234)
    hashTable.Put("Bob", 5678)

    if value, ok := hashTable.Get("Alice"); ok {
        fmt.Println("Alice's number:", value)
    }

    hashTable.Remove("Bob")

    if _, ok := hashTable.Get("Bob"); !ok {
        fmt.Println("Bob's number not found")
    }
}

• 명시: 이 코드는 오픈 어드레싱(Open Addressing) 방법 중 **선형 탐사(Linear Probing)**를 사용하여 충돌을 해결하는 해시테이블입니다.
• 이유: 충돌이 발생했을 때 다음 버킷을 순차적으로 탐색하여 빈 버킷을 찾습니다.

Java로 오픈 어드레싱 해시테이블 구현하기

class OpenAddressingHashTable<K, V> {
    private Entry<K, V>[] table;
    private int numBuckets;
    private int size;

    private static class Entry<K, V> {
        K key;
        V value;
        boolean isDeleted;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
            this.isDeleted = false;
        }
    }

    // Constructor
    public OpenAddressingHashTable() {
        numBuckets = 10;
        table = new Entry[numBuckets];
        size = 0;
    }

    // Hash function
    private int hash(K key, int i) {
        int hashCode = key.hashCode();
        return (Math.abs(hashCode) + i) % numBuckets; // 선형 탐사 사용
    }

    // Put method
    public void put(K key, V value) {
        for (int i = 0; i < numBuckets; i++) {
            int index = hash(key, i);
            Entry<K, V> entry = table[index];

            if (entry == null || entry.isDeleted) {
                table[index] = new Entry<>(key, value);
                size++;
                return;
            } else if (entry.key.equals(key)) {
                entry.value = value; // Update value
                return;
            }
        }

        // 테이블이 가득 찼을 때 리사이징 필요
        resize();
        put(key, value);
    }

    // Get method
    public V get(K key) {
        for (int i = 0; i < numBuckets; i++) {
            int index = hash(key, i);
            Entry<K, V> entry = table[index];

            if (entry == null) {
                return null;
            } else if (!entry.isDeleted && entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null; // Key not found
    }

    // Remove method
    public void remove(K key) {
        for (int i = 0; i < numBuckets; i++) {
            int index = hash(key, i);
            Entry<K, V> entry = table[index];

            if (entry == null) {
                return;
            } else if (!entry.isDeleted && entry.key.equals(key)) {
                entry.isDeleted = true;
                size--;
                return;
            }
        }
    }

    // Resize method
    private void resize() {
        numBuckets *= 2;
        Entry<K, V>[] oldTable = table;
        table = new Entry[numBuckets];
        size = 0;

        for (Entry<K, V> entry : oldTable) {
            if (entry != null && !entry.isDeleted) {
                put(entry.key, entry.value);
            }
        }
    }
}

// 사용 예시
public class Main {
    public static void main(String[] args) {
        OpenAddressingHashTable<String, Integer> hashTable = new OpenAddressingHashTable<>();

        hashTable.put("Alice", 1234);
        hashTable.put("Bob", 5678);

        System.out.println("Alice's number: " + hashTable.get("Alice"));

        hashTable.remove("Bob");

        System.out.println("Bob's number: " + hashTable.get("Bob")); // null 출력
    }
}

• 명시: 이 코드는 오픈 어드레싱(Open Addressing) 방법 중 선형 탐사(Linear Probing)를 사용하여 충돌을 해결하는 해시테이블입니다.
• 이유: 충돌이 발생했을 때 다음 버킷을 순차적으로 탐색하여 빈 버킷을 찾습니다.

마무리

해시테이블은 효율적인 데이터 저장과 검색을 가능하게 하는 강력한 자료구조입니다. 충돌은 해시테이블에서 불가피한 현상이지만, 다양한 충돌 해결 방법을 통해 이를 효과적으로 관리할 수 있습니다.

• 체이닝(Chaining): 각 버킷에 연결 리스트를 사용하여 충돌을 해결합니다. 구현이 간단하며 동적으로 확장 가능합니다.
• 오픈 어드레싱(Open Addressing): 테이블 내에서 빈 버킷을 찾는 방법으로 충돌을 해결합니다. 추가적인 메모리 사용이 없지만, 로드 팩터에 민감합니다.

각 방법은 장단점이 있으므로, 사용하려는 목적과 상황에 따라 적절한 충돌 해결 방법을 선택해야 합니다.

위의 예제 코드들을 통해 해시테이블의 동작 원리와 충돌 해결 방법을 이해하시길 바랍니다. 실제로 구현해보면서 해시테이블의 작동 방식을 체험해보는 것도 큰 도움이 될 것입니다.