해시테이블(Hash Table)와 해시충돌(Hash Collision)

해시테이블이란?

해시테이블은 Key-Value 형태로 저장되는 자료구조로, 평균 O(1)의 시간복잡도를 가진다. 흔히, HashMap이라고 불리기도 한다.
key 값을 Hash Function을 이용해, Hash Table에 저장할 위치를 정한다.
대표적인 Hash Function에는 Division Method(mod 연산)가 있다.

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

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

해시충돌(Hash Collision)이란?

해시 충돌은 어떤 entry를 넣으려고 할때, Hash Function으로 찾은 위치에 이미 다른 entry가 존재하는 경우 발생한다.
즉, 다른 키 값일때, Hash Function을 통해 같은 값을 가지게 되는 경우 해시 출돌이 발생한다.

해시충돌 해결 방법 1 : 체이닝(Chaining)

• 같은 주소로 해싱 될 때, 연결 리스트(Linked List)로 연결하는 방식
• 추가 공간 활용

구현

public class ChainingHashTable<K, V> {
    private LinkedList<Entry<K, V>>[] table; //buckets
    private int numberOfItems;

    public ChainingHashTable(int capacity) {
        table = new LinkedList[capacity];
        numberOfItems = 0;

        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    // TODO: Change hashcode -> Object.hashcode()
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    // TODO: when key duplicate, update value
    public void put(K key, V value) {
        int indexOfBucket = this.hash((String) key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

            for (Entry<K, V> entry : bucket) {
              if (entry.key.equals(key)) {
                  entry.value = value;
                      return;
                }
            }
            }

        bucket.add(0, new Entry<>(key, value));
        numberOfItems++;
    }

    public Entry<K, V> remove(K key) {
        if (isEmpty()) throw new RuntimeException("Hash Table is Empty!");

        int indexOfBucket = this.hash((String) key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

        for (Entry<K, V> entry: bucket) { // entry == node
            if (entry.key.equals(key)) {
                bucket.remove(entry);
                numberOfItems--;

                return entry;
            }
        }

        return null;
    }

    public V get(K key) {
        int indexOfBucket = this.hash((String) key);
        LinkedList<Entry<K, V>> bucket = table[indexOfBucket];

        for (Entry<K, V> entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null;

    }

    public boolean isEmpty() {
        return numberOfItems == 0;
    }

}

해시충돌 해결 방법 2 : 개방 주소법(Open Addressing)

추가 공간을 활용하지 않고 충돌을 해결하는 방법

1. 선형 탐색(Linear Probing)

• 충돌이 일어났을 때, 충돌 주소의 바로 다음 위치에 저장하는 방식
• 빈 bucket이 있을 때 까지 다음 위치를 탐색

구현

public class LinearHashTable<K, V> {
	private Entry<K, V>[] bucket;
	private int numberOfItems = 0;
	private int MOD;

	// Constructor : Create Bucket and set numberOfItems to 0
	public LinearHashTable(int capacity) {
		bucket = new Entry[capacity];
		MOD = capacity;
		numberOfItems = 0;
	}

	// Hash Function
	private int hash(K key) {
		return Math.abs(key.hashCode()) % MOD;
	}

	public void put(K key, V value) {
		int indexOfBucket = this.hash(key);

		while (indexOfBucket < bucket.length && !(bucket[indexOfBucket] == null || bucket[indexOfBucket].key == null)) {
			indexOfBucket++;
		}

		if (indexOfBucket == bucket.length)
			throw new RuntimeException("Hash Table is Full!");

		bucket[indexOfBucket] = new Entry<>(key, value);
		numberOfItems++;
	}

	public Entry<K, V> remove(K key) {
		if (isEmpty())
			throw new RuntimeException("Hash Table is Empty!");

		int indexOfBucket = this.hash(key);

		int indexOfTemp = indexOfBucket;

		while (true) {
			if (bucket[indexOfTemp].key.equals(key)) {
				Entry<K, V> entry = new Entry<K, V>(bucket[indexOfTemp].key, bucket[indexOfTemp].value);
				bucket[indexOfTemp].key = null;
				return entry;
			}
			indexOfTemp = (indexOfTemp + 1) % MOD;
			if (indexOfTemp == indexOfBucket)
				break;
		}

		return null;
	}

	public V get(K key) {
		int indexOfBucket = this.hash(key);

		int indexOfTemp = indexOfBucket;

		while (true) {
			if (bucket[indexOfTemp].key != null && bucket[indexOfTemp].key.equals(key)) {
				return bucket[indexOfTemp].value;
			}
			indexOfTemp = (indexOfTemp + 1) % MOD;
			if (indexOfTemp == indexOfBucket || bucket[indexOfTemp] == null)
				break;
		}

		return null;

	}

	public boolean isEmpty() {
		return numberOfItems == 0;
	}

	public static void main(String[] args) {
		LinearHashTable<Integer, Integer> hashTable = new LinearHashTable<Integer, Integer>(10);
		hashTable.put(0, 0);
		hashTable.put(10, 10);

		System.out.println(hashTable.get(0));
		System.out.println(hashTable.get(10));

		hashTable.remove(10);

		System.out.println(hashTable.get(0));
		System.out.println(hashTable.get(10));
	}

}

2. 제곱 탐색(Quadratic Probing)

• 충돌이 일어났을 때, 충돌 주소의 제곱만큼 건너뛴 위치에 저장하는 방식

3. 이중 해시(Double Hashing)

• 충돌이 일어났을 때, 다른 해시함수를 한번 더 적용한 위치에 저장하는 방식

체이닝 vs 개방주소법

구분	체이닝	개방주소법
추가공간	필요	필요없음
구현	연결리스트	새로운 위치를 나타내기 위한 구현이 조금 더 복잡함(해시함수, 제곱, 선형방식 etc)
오버헤드	해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생	삽입, 삭제시 오버헤드가 적다. 저장할 데이터가 적을 때 더 유리하다