[기초 자료구조] HashTable

1. HashTable 이란?

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

 

Hash Function

• 임의 크기의 데이터를 고정된 크기의 데이터로 매핑하는 함수
• Key를 입력받아 HashCode를 출력합니다.

 

HashCode

• 정수값
• HashTable의 인덱스로 사용됩니다.
  • 총 버킷 갯수로 나머지 연산을 수행합니다.  (인덱스 값으로 사용하기 위함)
  • h(x) = M % m

 

좋은 해시함수의 특징

• 일관성
  • 같은 키 값으로 항상 동일한 해시 코드를 생성해야 합니다.
• 빠른 계산
  • 효율적이며 빠르게 해시 코드를 생성해야 합니다.
  • 테이블 크기를 2의 거듭제곱으로 설정하면 모듈러 연산을 빠르게 할 수 있습니다.
• 균등성
  • 가능한 한 모든 버킷에 균등하게 데이터를 분산시켜야 합니다. 
  • 특정 버킷에 데이터가 몰리는 현상을 방지할 수 있습니다. (충돌 회피)
  • 2의 멱수에 가깝지 않은 소수를 선택하면 균등성이 높아질 가능성이 커집니다.

 

Key

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

 

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값이 임계값을 초과하면 HashTable을 리사이징을 시도합니다. (충돌 줄임을 목적)

 

적정값

• 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