[기초 자료구조] HashTable

0. Hash Function

• 임의의 크기의 입력을 고정된 크기의 출력으로 변환하는 함수

 

특징 (자료구조)

특징	설명
빠른 계산	해시값을 매우 빠르게 계산해야 함.	➡️ 테이블 크기를 2의 거듭제곱으로 두면 mod 연산 빠름
균등 분산	데이터가 가능한 한 모든 버킷에 고르게 분포해야 함. ✅ 군집 방지: 특정 버킷에 데이터가 몰리지 않도록 함.	➡️ 2의 멱수에 가깝지 않은 소수를 기반으로 한 해시가 균등성이 높음.

 

 

특징 (보안/암호학)

특징	설명
Diffusion (확산)	비슷한 입력이어도 완전히 다른 출력이 생성되어야 함. (Avalanche 효과) ✅ 차분 공격 방지: 입력 구조를 출력에서 추론 불가하게 함
Confusion (혼돈)	입력과 출력 사이에 패턴이 없어야 하며, 관계를 예측할 수 없어야 함. ✅ 선형 관계 방지: 입력 구조를 출력에서 추론 불가하게 함
One-way (단방향성)	출력만 보고 입력을 역으로 복원할 수 없어야 함. ✅ 비밀번호 원칙: 입력을 보고 해당 해시값인지는 알 수 있으나, 해시로 원본을 알 수 없어야 함
Collision Resistance (충돌 저항성)	서로 다른 두 입력이 같은 출력을 만들지 않도록 해야 함 (찾기 매우 어려워야 함). ✅ 디지털 서명 핵심: 충돌이 있으면 위조 가능하므로 필수

 

1. HashTable 이란?

• 매핑할 수 있는 자료구조 입니다. (key-value)
• key를 사용하여 해당되는 value를 빠르게 찾을 수 있습니다.
• 해시 함수로 HashCode를 Key로 사용함

 

Key

• 특정 value에 접근하기 위한 고유한 식별자입니다.
• hash function을 사용하여 계산된 값을 bucket의 인덱스로 사용합니다.
• 같은 Key값을 가진 가진 두 개의 다른 데이터가 HashTable에 저장될 경우 충돌이 발생합니다.

 

HashCode

• HashTable의 인덱스로 사용됩니다.
• ✅ 총 버킷 갯수로 나머지 연산을 수행합니다
• ➡️ h(x) = M % m

 

2. Hash Collision

• 두 개 이상의 키가 동일한 해시 값을 가질 경우 충돌이 발생합니다.
• 충돌을 해결하기 위해 특정 로직이 수행되므로 성능이 저하됩니다.

 

충돌 발생 이유

• Hash Function은 임의의 입력을 고정 크기의 값으로 매핑합니다.
• 출력 공간이 입력 공간보다 작기 때문에 충돌이 발생할 수 있습니다.

 

해결 방법

Separate Chaining 

• 충돌이 일어나는 Entry를 Linked List로 연결해서 저장하는 방식입니다.
• 특정 Entry에 충돌이 많이 일어나면 검색 성능이 떨어집니다.

 

Open Addressing

• 추가 공간을 사용하지 않고 충돌을 해결합니다.
• 충돌이 일어나면 해당 Key가 아닌 다른 위치에 저장합니다.
• Linear Probing
  
  • 충돌이 발생한 bucket의 다음 위치에 저장하는 방식입니다.
  • 일차 함수의 보폭으로 점프
  • 가장 간단한 충돌 해결 규칙
• 유의사항
  • 연산하여 얻어낸 key값에 value가 저장된다는 보장이 없습니다. (충돌로 인해 점프했을 가능성 존재)
  • 데이터를 삭제할 경우, 삭제된 자리에 표시 필요 (검색시,계속해서 탐색을 시도하기)

 

3. Load Factor

• HashTable이 가득 찬 정도를 뜻하는 값입니다.
• Load Factor값이 임계값을 초과하면 리사이징을 시도합니다. (충돌 줄임 목적)

 

적정값

• 0 <= Load Factor <= 1

 

4. Resizing

• HashTable의 크기를 동적으로 조정하는 작업입니다.
• HashTable 두 배의 크기를 가진 배열에 기존의 데이터를 re-hashing하여 저장합니다.

 

시점

• Load Factor의 특정 임계값이 초과할 경우 발생합니다.

 

5. 구현

seperate chaining

public class MyHashTable<K, V> {
    class Node<K, V> {
        final K key;
        V value;
        Node<K, V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    Node<K, V>[] arr;
    final int size;

    public MyHashTable(int size) {
        this.arr = new Node[size];
        this.size = size;
    }

    public void put(K key, V value) {
        int idx = hash(key) % size;

        Node<K, V> curNode = arr[idx];
        Node<K, V> newNode = new Node<>(key, value);

        if (curNode == null) {
            arr[idx] = newNode;
            return;
        }

        Node<K, V> prevNode = null;
        while (curNode != null) {
            if (curNode.key.equals(key)) {
                curNode.value = value;
                return;
            }

            prevNode = curNode;
            curNode = curNode.next;
        }

        prevNode.next = newNode;
    }

    public V get(K key) {
        int idx = hash(key) % size;
        Node<K, V> curNode = arr[idx];

        while (curNode != null) {
            if (curNode.key.equals(key)) return curNode.value;
            curNode = curNode.next;
        }

        return null;
    }

    public void remove(K key) {
        int idx = hash(key) % size;

        Node curNode = arr[idx];

        if (curNode == null) return;

        Node prevNode = null;

        while (curNode != null) {
            if (curNode.key.equals(key)) {
                if (prevNode == null) arr[idx] = curNode.next;
                else prevNode.next = curNode.next;
                return;
            }

            prevNode = curNode;
            curNode = curNode.next;
        }
    }

    private int hash(K key) {
        return Math.abs(Objects.hashCode(key));
    }
}

 

 

 

출처

• Wiki - HashTable