Set과 Hash Table

Set은 중복된 원소를 포함하지 않고 순서가 상관없는 원소들의 컬렉션을 나타내는 개념으로 집합의 개념과 같다.(집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없다.)

Set은 여러 가지 방법으로 구현될 수 있지만, 가장 일반적으로 사용되는 구현 방법은 해시 테이블(Hash Table)을 기반으로 한다.

해시 테이블에서는 Key가 중복될 수 없고 데이터는 순차적이 아니라 랜덤하게 저장한다.

해시 테이블의 이런 특징은 Set의 개념과 일치하기 때문에 Set을 구현할 때는 해시 테이블의 Key에 데이터를 저장하는 형태로 구현을 하게 된다.

Hash Table

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조다.
해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(buckets)을 사용하여 데이터를 저장하기 때문이다.

해시 테이블을 사용한 Set 구현의 핵심 아이디어는 각 원소를 해시 함수(hash function)를 사용하여 해시 코드로 변환하고, 이 코드를 기반으로 원소를 저장하거나 검색하는 것이다.

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다.
여기서 실제 값이 저장되는 장소를 bucket 또는 slot이라고 한다.

출처 : 위키백과 - 해시테이블(https://en.wikipedia.org/wiki/Hash_table)

이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 따라서 해시 테이블의 평균 시간복잡도는 O(1)이다.

또한 해시 테이블을 사용할때 해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황이 발생할 수가 있는데 이를 해시 충돌(Hash Collsion)이 발생했다고 한다.

Hash Collision

해시 테이블에서 해시 충돌을 해결하는 방법은 대표적으로 두가지가 있습니다.

분리 연결법(Separate Chaining)

분리 연결법 방식으로, `Linked List`를 사용하여 Key-Value 쌍을 저장하는 방식이다.

같은 인덱스에 속한 Key-Value 쌍을 연결 리스트에 추가하여 저장하고, 검색 시에는 해당 인덱스의 연결 리스트를 순회하여 검색한다.

이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

개방 주소법(Open Addressing)

개방 주소법 방식으로, 충돌이 발생한 경우 다른 빈 인덱스를 찾아 해당 Key-Value 쌍을 저장하는 것이다.

대표적으로 선형 조사(Linear Probing), 이차 조사(Quadratic Probing), 이중 해시(Double Hashing) 등의 방법이 있다.

• 선형 조사: 충돌 발생 시, 다음 인덱스를 차례대로 검색하여 빈 공간을 찾는 방식
• 이차 조사: 충돌 발생 시, 다음 인덱스를 일정한 간격으로 건너뛰면서 빈 공간을 찾는 방식
• 이중 해시: 두 개의 해시 함수를 사용하여 충돌 발생 시, 다른 위치를 찾아 Key-Value 쌍을 저장하는 방식

Java에서 Hash Table 활용

HashSet

Java의 HashSet은 Set 인터페이스를 구현한 컬렉션으로 내부적으로 `HashMap`으로 구현되어 있다.

HashMap과 HashTable

Java에서 두 API의 차이는 동기화 지원 여부에 있다.

// HashTable의 put
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    addEntry(hash, key, value, index);
    return null;
}

// HashMap의 put
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Java의 `HashTable` 클래스는 Java 1.0부터 있던 Java의 API이고, HashMap은 Java 2에서 처음 선보인 `Java Collections Framework`에 속한 API다. HashMap 과 Hashtable 사이의 관계는 ArrayList와 Vector의 관계와 같다고 보면 된다.

 

동적으로 크기가 조정되는 배열인 것은 같지만, ArrayList는 동기화 되지 않았기 떄문에 Thread Safe하게 동기화된 Vector보다 더 빠른 성능을 보여준다. 이와 마찬가지로 HashTable 클래스는 동기화를 보장하므로 멀티스레드 환경에서 안전하게 사용할 수 있지만, 동기화로 인해 성능이 느릴 수 있다. 반면에 HashMap 클래스는 동기화를 보장하지 않기 때문에 단일 스레드 환경에서 더 빠른 성능을 보일 수 있다.

 

그 뿐만 아니라 HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다.
거기에 더하여 Java 1.5 이후부터는 `ConcurrentHashMap` 클래스가 도입되어, 멀티스레드 환경에서 안전하면서도 HashMap 클래스보다 빠른 성능을 보여주는 자료구조가 제공되고 있다.

HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다.

Java 8 HashMap에서의 Separate Chaining

Java 8에서 Separate Chaining 방식의 HashMap은 기존의 LinkedList 방식에 비해 성능이 향상되었다. 연결 리스트 대신에 자체 구현한 Tree 구조로 변경하여 충돌의 수를 줄이고 검색 성능을 개선했다.
이를 Red-Black Tree(Java Collections Framework의 TreeMap과 구현이 거의 같음)로 구현하여 O(log n)의 시간 복잡도를 갖게 되고 검색시 최악의 경우 O(n)이 될 수 있었던걸 방지한다.

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;

HashMap의 내부 구현을 보면 일부 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. (8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.)