자바 HashTable 과 HashMap

HashTable 이란

- 해시 함수를 사용해서 변환한 값을 index 로 삼아 key 와 value 를 저장하는 자료구조

- 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.

- 순차적으로 데이터를 저장하지 않는다.

- 해시 테이블은 key-value 가 1:1 매핑되어 있어 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1) 의 시간복잡도를 갖는다. (공간 복잡도는 O(n))

- 이진탐색 트리나 배열에 비해서 속도가 획기적으로 빠르다.

 

• 해시 동작 원리

https://en.wikipedia.org/wiki/Hash_table

- 원래 데이터인 keys 를 Hashing 이라는 과정(hash fucntion) 을 거친다.

- Hashign 과정을 거친 후 Hash value(hashing 후 데이터의 값) 로 매핑한다.

- Hash value 를 index 로 삼아 데이터의 value 를 buckest(slots) 에 저장한다.

 

• 해시 충돌(Hash Collision)
  • 해시 충돌이란 어떤 해시 함수가 서로 다른 두 입력에 대해 동일한 출력 값을 나타내는 경우
  • 해시 함수에 입력할 수 있는 데이터의 가짓수는 무한한데, 출력으로 나올 수 있는 해시 값이 유한하기 때문에 발생한다.

 

• 해시 충돌 완화
  • 개방주소법(open addressing)
    • 선형 탐사법(Linear Probing)
      • 해시 함수로 나온 해시 index 에 이미 다른 값이 저장되어 있어, 다음 해시값에서 고정 폭을 옮겨 다음 해시값에 해당하는 버킷에 액세스 한다.
      • 클러스터링 문제가 발생할 수 있고, 이는 시간 및 공간 복잡성에 영향을 미친다. > O(log n)
    • 제곱 탐사법(Quadratic Probing)
      • 선형 탐사법과 동일하며 고정폭이 아니라 제곱으로 늘어난다.
  • 분리 연결법(separate chaining)
    • 한 버킷에 들어갈 엔트리의 수에 제한을 두지 않고, 링크드 리스트나 트리를 사용한다.

 

 

Java HashMap

 

• 해시 테이블 기반
  • HashMap은 해시 테이블을 기반으로 구현되고, 해시 함수를 사용하여 각 키를 해시 값으로 변환하고, 해당 값의 버킷에 저장합니다.
  • 자바 초기에는 Hashtable 이 해시 기반의 key-value 를 저장하는데 사용되었고, 이후 java 1.2 에서 HashMAp 이 유연하고 성능이 향상되게 도입되었다.
  • HashMap 은 단일 스레드 환경에서 빠르게 동작하나 멀티스레드 환경에서는 취약하다. 그래서 나온 것이 ConcurrentHashMap 입니다.
  • 해시 충돌 시 Separate chaining 방식을 사용한다.
    • (참고) Python 의 dictionary 는 해시 충돌 시에 Open addressing 방식 사용.

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        ...
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;              
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        
             //////////// 해시 충돌 ////////////
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

 

• 일정함 임계값을 넘기면 해당 버킷의 연결 리스트는 트리로 변환된다
• 트리 구조는 충돌된 요소들을 보다 효율적으로 관리할 수 있으며, 검색 작업의 성능을 개선시킨다.
  따라서 해시 충돌이 발생하더라도 성능 저하를 최소화하고 더 효율적으로 처리할 수 있다.
• 그러나 연결 리스트와 트리 중 어떤 구조를 사용할지는 충돌된 요소들의 수에 따라 자동으로 결정되므로, 프로그래머가 직접 선택하거나 제어할 수는 없다.

• HashMap은 내부적으로 버킷 배열을 사용하여 데이터를 저장하고, 각 키의 해시 코드에 기반하여 해당하는 버킷에 값을 저장한다.
• 그러나 해시 충돌이 발생하면 같은 버킷에 연결 리스트를 사용하여 여러 개의 값이 저장될 수 있다.
• 이 때문에 데이터가 저장된 순서와 출력되는 순서가 일치하지 않습니다.
• 검색 시간 복잡도
  • 해시 테이블의 특성 상, 검색 시간 복잡도는 O(1)에 가깝습니다. 이는 매우 빠른 검색 속도를 제공합니다.
• 중복된 키 허용 안함
  • HashMap은 중복된 키를 허용하지 않습니다. 즉, 같은 키로 여러 번 값을 저장할 수 없습니다. 중복된 키를 사용하면 기존 값이 대체됩니다.
• Null 값 및 Null 키 허용
  • HashMap은 null 값을 키 또는 값으로 허용합니다. 즉, null 키와 null 값을 사용하여 데이터를 저장할 수 있습니다.
  • null 을 허용하기 때문에 hashTable 보다 더 많은 유연함을 제공합니다.
• ConcurrentHashmap
  • Hashtable은 멀티스레드 환경에서 스레드 안전성을 보장하기 위해 모든 메서드에 동기화를 제공합니다. 이에 비해 ConcurrentHashMap은 동기화된 부분을 최소화하여 더 나은 동시성을 제공합니다. 특히 ConcurrentHashMap은 분할된 잠금(lock-striping)과 세분화된 잠금을 통해 성능을 향상시킵니다.

 

* 초기 용량과 부하 계수

 - HashMap은 초기 용량과 부하 계수(load factor)를 설정할 수 있다.
 - 초기 용량은 HashMap이 내부 배열을 초기화할 때 사용되며, 부하 계수는 배열이 얼마나 채워졌을 때 배열 크기를 조정할지를 결정한다.
- 기본적으로 초기 용량은 16이고, 부하 계수는 0.75입니다.

아래의 HashMap 클래스를 보면

...
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8;

    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;

    ...

• DEFAULT_INITIAL_CAPACITY : 초기 용량을 나타내며 기본적으로 16
• MAXIMUM_CAPACITY : 최대 용량 약 10억
• DEFAULT_LOAD_FACTOR : 로드 팩터로 해시 맵의 용량을 나타낸다. 0.75
• TREEIFY_THRESHOLD : 연결리스트가 트리로 변환되는 임계값. (일정 수준 이상의 충돌이 발생할 때 버킷의 연결리스트가 트리로 변환되는 값)
• UNTREEIFY_THRESHOLD : 트리 구조가 연결 리스트로 변환되는 임계값
• MIN_TREEIFY_CAPACITY : 트리로 변환될 수 있는 최소한의 해시 테이블 크기

 

 

HashMap vs TreeMap

• HashMap은 해시 테이블을 기반으로 하며, 키-값 쌍의 순서를 유지하지 않는다.
  반면에 TreeMap은 이진 검색 트리를 기반으로 하며, 키-값 쌍을 자동으로 정렬하여 저장한다.
• TreeMap은 이진 검색 트리를 사용해서 요소를 저장하고, 각 노드가 최대 두 개의 자식 노드를 가지고, 왼쪽 자식은 현재 노드보다 작은 값이고,
  오른쪽 자식은 현재 노드보다 큰 값이다.
  해당 컬렉션의 검색,삽입,삭제 작업의 시간 복잡도는 평균 O(log n) 입니다.

 

 

HashMap vs LinkedHashMap

• LinkedHashmap은 모든 요소들의 순서를 유지하고, 순회할 때 오소의 순서가 보장된다. 그렇기 때문에 삽입된 순서대로 순회할 때 유용하다.
• LinkedHashmap 은 내부적으로 해시 테이블과 연결 리스트를 사용해서 요소를 저장하기 때문에 HashMap 보다 더 많은 메모리를 사용할 수 있고, 연결 리스트 유지를 위해 추가적인 연산이 필요해서 성능이 느릴 수 있다.

 

 

HashMap vs HashSet

• HashSet 은 중복을 허용하지 않는 요소들의 모임
• 내부적으로는 HashMap 을 사용하여 요소들을 저장하고, 요소들은 키로 저장된다.
  따라서 HashSet 은 중복된 요소를 추가할 때 키가 이미 존재하는지 확인해서 중복을 허용하지 않게 한다.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    @java.io.Serial
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    ...
    
        public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
    ...
    
}