HashTable과 HashMap

1. ThreadSafety

 HashTable: ThreadSafety하다.

 HashMap: ThreadSafety하지 않다.

 

 HashTable은 내부적으로 synchronization을 사용하기 때문에 race condition과 같은 동시성 문제가 발생하지 않는다. 따라서 여러 개의 스레드가 데이터에 접근하더라도 문제가 발생하지 않는다.(동시성 문제, deadlock 등) 반면 Synchronization 때문에 오직 하나의 스레드만 데이터에 접근할 수 있기 때문에 성능이 느릴 수 있다.

 동시성 문제(Concurrency problem)란 여러 스레드가 공유하는 데이터를 동시에 접근할 때, 예측할 수 없는 상황이 발생하는 문제를 말한다. 예를 들어 아래 코드를 실행하면, A 스레드가 counter 값이 10이라는 것을 읽어 11로 증가시키고, 동시에 B 스레드도 counter 값이 10이라는 것을 읽어서 11로 증가시키는 상황이 발생할 수 있다. counter 값을 2번 증가시켰지만, 예상하지 못한 결과로 결괏값은 1번 증가한다. 이로 인해 counter 변수의 출력값은 실행할 때마다 달라질 수 있다.

import kotlin.concurrent.thread

var counter = 0

fun main() {
    repeat(100) {
        thread {
            for (i in 1..1000) {
                counter++
            }
        }
    }
    Thread.sleep(5000)
    println("Counter: $counter")
}

 Counter 코드를 Synchronized 블록으로 감싸면 동시성 문제를 해결할 수 있다. 스레드가 synchronized 블록을 만나면, 먼저 lock(monitor 또는 mutex라고도 함)을 획득할 수 있는지 확인한다. 만약 다른 스레드가 이미 lock을 획득한 경우, 해당 lock이 해제될 때까지 기다린다. lock이 해제되면 스레드는 lock을 얻어 다른 스레드가 블록에 들어오지 못하도록 한다. 작업이 완료되면 lock을 해제하여 다른 스레드가 lock을 얻을 수 있도록 한다.

synchronized(this) {
	counter++
}

 deadlock의 4가지 조건: 상호 배제(Mutual exclusion), 점유와 대기(Hold and wait), 선점 불가(No preemption), 순환 대기(Circular wait)

 deadlock에 대해서는 아래 블로그에 자세하게 정리되어 있다.

https://kukuta.tistory.com/281

데드락(Deadlock) 개념 정리

2. Null Values

 HashTable: null key, null values를 허용하지 않는다.

 HashMap: null key, null values를 허용한다.

 

 

 HashTable의 hashing 알고리즘은 key를 사용하여 hash 값을 생성한다. 하지만 hashing 알고리즘에서는 null을 사용할 수 없으므로, null key나 null value를 허용하지 않는다. 예를 들어, null 과 Int를 곱할 수 없다. ( null * 31 )

 HashTable의 put 함수는 if문을 이용해 null check를 하며, get 함수는 null check를 수행하지 않지만 key가 null이면 NullPointerException이 발생한다.

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;
}

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
 * then this method returns {@code v}; otherwise it returns
 * {@code null}.  (There can be at most one such mapping.)
 *
 * @param key the key whose associated value is to be returned
 * @return the value to which the specified key is mapped, or
 *         {@code null} if this map contains no mapping for the key
 * @throws NullPointerException if the specified key is null
 * @see     #put(Object, Object)
 */
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

 HashMap은 key가 null인 경우, 해시값으로 0을 반환하는 if문을 사용한다. key가 null이 아닌 경우에는 hashCode 함수를 사용하여 해시값을 반환한다. hashCode 함수는 0이 아닌 integer 값을 반환하므로, null의 해시값과 충돌하지 않는다.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 HashTable도 HashMap처럼 key의 null check 이후 0을 리턴하면 될텐데 왜 그렇게 하지 않았을까? ChaptGPT에 따르면 Internal data structure의 Consistency와 Correctness를 유지하기 위해서 라고 한다.

By consistency, we mean that the state of the data structure remains well-defined and predictable throughout its lifetime, even as operations are performed on it. For example, if an element is added to a
HashTable, we expect that it will be stored in the correct slot and that it will be accessible using the key that was used to add it. Similarly, if an element is removed from the HashTable, we expect that it will be removed from the correct slot and that the table will remain well-formed. By correctness, we mean that the behavior of the data structure conforms to its specification and does not produce unexpected or incorrect results. For example, if we add an element to a
HashTable with a given key and value, we expect that the element will be added to the table, and subsequent lookups with the same key will retrieve the same value.

 

 또한 ChatGPT는 null을 허용하지 않으면 LinkedList 대신 Array에 Key를 저장할 수 있어서 탐색이 더 빨라진다고 답변했지만, 실제로는 HashTable과 HashMap 모두 LinkedList로 Key를 관리하고 있다. 두 자료구조의 차이는 null key나 value를 확인한 후 처리하는 코드뿐이다. 그래서 ChatGPT에게 null key나 value가 LinkedList와 직접적으로 관련이 없지 않냐고 다시 물어보니 그렇다고 한다. LinkedList는 해시 충돌과 hash code를 처리하기 위해 필요하다고 한다. 그러나 null을 허용하면 개발자가 null을 처리해야 하는데, 이때 발생할 수 있는 실수로 인해 null을 허용하지 않는 것이 좋다고 한다.

 결론적으로 HashTable에서 null key나 null value를 지원하지 않는 이유는 HashTable을 설계한 사람들의 의도라고 할 수 있다.

3. Iteration

 HashTable: Internal synchronization으로 인한 overhead 때문에 내부 원소를 탐색하는 속도가 느리다.

 HashMap: HashTable보다 빠르다.

 

4. Iteration Order

 HashTable: 추가된 원소의 순서대로 탐색하는 것이 보장되지 않는다.

 HashMap: 추가된 원소의 순서대로 탐색하는 것이 보장되지 않는다.

 

 추가된 원소는 key의 해시 값에 의해 저장될 bucket index가 결정된다. Hash의 목적은 가능한 모든 버킷에 원소를 균등하게 분배하는 것이다. 따라서 삽입 순서와는 관계없이 랜덤한 bucket에 원소가 저장된다. 또한, 원소의 삽입 또는 삭제로 인해 전체 크기가 변경되면, 이전과 다르게 어떤 원소가 어떤 bucket에 어떤 순서로 저장되는지가 변경될 수 있다.

 따라서 HashTable과 HashMap은 추가된 원소의 순서대로 탐색하는 것을 보장하지 않는다.

 만약 입력된 원소의 순서가 보장되어야 한다면, LinkedHashTable과 LinkedHashMap을 사용하는 것이 좋다. 이 두 자료구조는 HashTable과 HashMap에 doubly-linked list가 추가된 형태다. 이 리스트를 통해 입력된 원소의 순서를 관리한다.

 원소를 저장하기 위해 linked list 대신 doubly-linked list를 사용하는 이유는 무엇일까? ChatGPT의 답변은 중간에 원소를 삽입하거나 삭제하는 경우에 더 효율적이지만, 코드 실행 결과에 따라 두 구현체 간의 시간 차이가 없을 수도 있다는 것이다. 따라서 linked list와 doubly-linked list 중 어떤 것을 사용할지는 사용하는 상황과 코드 실행 결과에 따라 결정되어야 한다. ChatGPT는 두 자료구조의 차이를 확인할 수 있는 아래의 코드를 예시로 알려주었으나, 로컬 컴퓨터에서 실행해보니 두 자료구조 간의 시간적 차이가 없다는 결과를 확인했다.(1ms) 따라서 ChatGPT가 제공한 예시는 참고할 수는 있지만, 그 결과에 절대적으로 의존해서는 안 되며, 이에 대한 검증이 필요하다는 것을 느꼈다.

import kotlin.system.measureTimeMillis

class Node(var value: Int, var next: Node? = null, var prev: Node? = null)

fun main() {
    // Create a singly-linked list with 100000 elements
    var head = Node(0)
    var tail = head
    for (i in 1..99999) {
        val node = Node(i)
        tail.next = node
        tail = node
    }

    // Benchmark removing 10000 elements from the middle of the singly-linked list
    val removeTimeSingly = measureTimeMillis {
        var current = head
        repeat(50000) {
            current = current.next!!
        }
        repeat(10000) {
            current.next = current.next?.next
        }
    }
    println("Time to remove 10000 elements from singly-linked list: $removeTimeSingly ms")

    // Create a doubly-linked list with 100000 elements
    head = Node(0)
    tail = head
    var prev: Node? = null
    for (i in 1..99999) {
        val node = Node(i, prev = prev)
        tail.next = node
        prev = tail
        tail = node
    }

    // Benchmark removing 10000 elements from the middle of the doubly-linked list
    val removeTimeDoubly = measureTimeMillis {
        var current = head
        repeat(50000) {
            current = current.next!!
        }
        repeat(10000) {
            current.next?.prev = current.prev
            current.prev?.next = current.next
            current = current.next!!
        }
    }
    println("Time to remove 10000 elements from doubly-linked list: $removeTimeDoubly ms")
}


// Time to remove 10000 elements from singly-linked list: 1163 ms
// Time to remove 10000 elements from doubly-linked list: 5 ms

 double-linked list를 사용하는 이유는 LRU 캐싱 구현 과정에서 더 유리하기 때문이다. 그러나 왜 더 유리한지 잘 이해되지 않아서, 그대로 답변을 첨부했다.

 By using a doubly-linked list, LinkedHashMap can maintain a predictable and consistent iteration order that is based on the order in which elements were inserted. This allows clients to iterate over the map in the same order that elements were added, which can be useful in a variety of scenarios.
 For example, LinkedHashMap's predictable iteration order can be used to implement LRU (Least Recently Used) caching, where the least recently accessed elements are removed from the cache in the order they were added. By using a doubly-linked list to store the insertion order, LinkedHashMap can efficiently remove the least recently accessed elements by simply removing elements from the beginning of the list.
 In contrast, a singly-linked list would not be able to efficiently remove elements from the beginning of the list because it does not have a prev pointer that allows efficient traversal in reverse order. Therefore, a singly-linked list would require iteration over the entire list to remove the least recently accessed element, which would be slower and less efficient.
 In summary, LinkedHashMap uses a doubly-linked list to store the insertion order of elements because it provides fast and efficient iteration in the order elements were added, while still providing constant-time lookup and insertion of elements.

 

5. Time Complexity

 HashTable과 HashMap의 함수는 일반적으로 O(1)에 실행되지만, 최악의 경우에는 O(n)이 소요될 수도 있다. 이는 collision이 많거나 linked list가 매우 긴 경우다. 따라서 적절한 hash function과 load factor를 설정하여 충돌을 최소화하여 O(1) 수준으로 유지하는 것이 중요하다.

 load factor는 bucket에 얼만큼 채워질 수 있는지를 나타내는 비율을 나타내며, 일반적으로 0.75로 설정된다. 이는 bucket이 75%까지 채워지면 resize가 발생한다는 것을 의미한다. resize는 bucket 내 linked list의 길이가 길어져 탐색 속도가 느려질 때 실행되며, bucket의 개수를 늘리는 작업이다. resize는 비용이 큰 작업이므로, 적절한 load factor를 설정하여 메모리 사용과 탐색 속도를 균형있게 유지하는 것이 중요하다.

 

6. Inheritance

 HashTable: Java 1.0의 legacy class이며 하위 호환성을 위해 Java API의 일부로 존재한다.

 HashMap: Java 1.2에서 도입된 클래스로 Java Collections Framework의 일부로 존재한다.

 

  Java API는 자바 언어로 작선된 프로그램에서 사용할 수 있는 다양한 라이브러리와 클래스, 인터페이스, 그리고 다른 자원들을 제공한다. 이를 통해 입/출력, 네트워킹, 그래픽, 사용자 인터페이스 등 다양한 분야에서 프로그래밍이 가능하다.

 Java Collections Framework는 Java API의 일부로, 핵심 자료구조 인터페이스(List, Set, Map 등)와 그 구현체들만 모아둔 것이다.

 즉, Java API는 입/출력, 네트워킹, 그래픽, 사용자 인터페이스와 같은 다양한 상황에 적용할 수 있는 모든 것들을 제공하고, Java Collections Framework는 List, Set, Map, Queue와 같은 Collection과 관련된 클래스와 인터페이스를 제공한다. Java Collections Framework에 있는 것은 Java API에도 있지만, Java API에 있는 것이 Java Collections Framework에 없을 수도 있다.