[Java] HashMap & HashTable & ConcurrentHashMap & LinkedHashMap의 차이

🍁 해시 (Hash)

---

🔹 해시(Hash) 란 단방향 암호화 기법인 해시함수(HashFunction)를 이용하여 생성된 고정된 길이의 비트열을 의미한다. 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(Hash Value) 또는 해시코드 라고 하며, 키(key)와 값(value)으로 매핑되는 과정 자체를 해싱(Hashing) 이라고 한다.

 

변환이 이루어진 후 변환된 값이 중복되는 경우가 발생할 수 있는데 이를 해시충돌(Hash Collision) 이라고 하고, 해시 충돌을 해결할 수 있는 방법에는 대표적으로 체이닝(Seperating Chaining), 개방 주소법(Open Addressing)이 있다.

 

🍁 Seperating Chaining

---

🔹 이 방법은 JDK내부에서도 사용하고 있는 충돌 처리 방식인데, Linked List를 이용하는 방식이다. Linked List뿐만이 아니라 Tree(Red-Black Tree)를 사용하기도 한다. 두 개를 사용하는 기준은 data가 6개 이하이면 linked list를 사용하고 8개 이상이면 tree를 사용한다. 이때 7개가 아닌 6개와 8개를 기준으로 선택하는 이유는, 데이터를 추가하거나 삭제할 때 발생하는 오버헤드를 최소화하기 위함이다. 예를 들어, 7개일 때는 데이터를 삭제하면 연결 리스트로 변경해야 하고, 추가하면 트리로 변경해야 하는데, 이러한 변경 작업에는 오버헤드가 발생하기 때문에 기준이 6과 8로 설정된다.

 

충돌이 발생한 인덱스에 대해, 해당 인덱스가 가리키고 있는 연결 리스트에 새로운 노드를 추가하여 값을 삽입한다. 데이터를 검색할 때는 해당 키에 대한 인덱스가 가리키고 있는 연결 리스트를 선형 검색하여 데이터를 반환한다. 삭제하는 것도 비슷하게, 키에 대한 인덱스가 가리키고 있는 Linked list에서, 그 노드를 삭제한다. Separate changing 방식은 Linked List 구조를 사용하고 있기 때문에, 추가할 수 있는 데이터 수의 제약이 작다.

Seperating Chaining 장단점

• 장점
  1. 한정된 저장소(Bucket)을 효율적으로 사용할 수 있다.
  2. 해시 함수(Hash Function)을 선택하는 중요성이 상대적으로 적다.
  3. 상대적으로 적은 메모리를 사용한다. 미리 공간을 잡아 놓을 필요가 없다.
• 단점
  1. 한 Hash에 자료들이 계속 연결된다면(쏠림 현상) 검색 효율을 낮출 수 있다.
  2. 외부 저장 공간을 사용한다.
  3. 외부 저장 공간 작업을 추가로 해야 한다.

🍁 Open Addressing

---

🔹 이 방법은 인덱스에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈 공간을 사용하는 방법이다. 추가적인 메모리 공간을 사용하지 않기 때문에 Separate chaining방식에 비해서 메모리를 덜 사용한다. Linear Probing, Quadratic Probing, Double hashing 등이 있다. 

 

• 선형 탐색(Linear Probing) : 다음 해시(+1)나 n개(+n)를 건너뛰어 비어있는 해시에 데이터를 저장한다.
• 제곱 탐색(Quadratic Probing) : 충돌이 일어난 해시의 제곱을 한 해시에 데이터를 저장한다.
• 이중 해시(Double Hashing) : 다른 해시함수를 한 번 더 적용한 해시에 데이터를 저장한다.

Linear Probing방식은 인덱스가 중복되는 충돌이 발생할 때 인덱스 뒤에 있는 버킷중에 빈 버킷을 찾아서 데이터를 넣는다. 그림에서 Sandra(key)의 인덱스는 152이다. 하지만 키 John과 충돌이 나기 때문에 그다음 인덱스인 153에 데이터를 넣는다. Linear Probing방식에서의 탐색은 Sandra(key)에 대해서 검색을 하면, index가 152이기 때문에, key가 일치하지 않기 때문에 뒤의 index를 검색해서 같은 키가 나오거나 또는 Key가 없을 때까지 검색을 진행한다. 삭제는 더미 노드를 넣어서 검색할 때 다음 인덱스까지 검색을 연결해 주는 역할을 해줘야 한다. (즉, 삭제가 어렵다.)

Open Addressing 장단점

• 장점
  1. 또 다른 저장공간 없이 해시테이블 내에서 데이터 저장 및 처리가 가능하다.
  2. 또 다른 저장공간에서의 추가적인 작업이 없다.
• 단점
  1. 해시 함수(Hash Function)의 성능에 전체 해시테이블의 성능이 좌지우지된다.
  2. 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해 두어야 한다.

⛓ HashMap

---

🔹HashMap은 Map 인터페이스를 구현하고 있는 대표적인 클래스다. 그리고 Map의 구조인 key-value쌍으로 구성되어 있고 Map의 대표적인 특징으로 하나의 key는 정확히 하나의 value만 가지고있다.

 

이러한 HashMap이 필요한 이유로는 시간복잡도가 있다. list를 예시로 들자면 list의 경우는 원소를 검색하는 시간복잡도가 O(n)이 나오지만 HashMap의 경우 삽입, 검색에 O(1)이라는 시간복잡도가 나온다. 이처럼 HashMap은 성능상으로도 메모리상으로도 list보다 우위에 있게 된다. 

 

⛓ HashTable

---

🔹 Hash Table은 키(key)와 값(value)이 하나의 쌍을 이루는 데이터 구조이다. Hash Table이 빠른 이유는 내부적으로 배열 (버킷)을 갖고 있기 때문이다. Hash Table은 Hash Function을 활용하여 키를 매핑해 배열의 index로 사용하는데 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자 값을 해시값 또는 해시코드 라고 한다. 즉, key 값을 해시 함수를 통해서 배열의 인덱스로 바꿔주고, 그 자리에 데이터를 저장한다.

 

📑 HashTable과 HashMap 특징

---

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(Index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시 테이블(Hash Table) 혹은 해시맵(Hash Map) [자바에서는 두 자료구조가 다르다] 이라고 한다. 이때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 한다. 

 

HashTable과 HashMap 차이

◈ Thread-safe 여부

    ◈   Hashtable은 Thread-safe 하고, HashMap은 Thread-safe 하지 않다는 특징을 가지고 있다.

 

◈ Null 값 허용 여부

    ◈ Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

 

HashMap이 Thread-safe하지 않은 이유

➡️ 위의 글에서 HashMap은 Thread-safe하지 않다고 말했는데 이는 여러 스레드가 동시에 접근할 경우, 동시에 객체의 data를 조작해 data가 깨질 수 있고 데이터 일관성 문제가 발생할 수 있다는 것을 의미한다. 이는 다음과 같은 상황에 발생할 수 있다.

    1. 해시 충돌이 발생하는 경우, 같은 인덱스에 여러 데이터가 중복되어 저장될 수 있다. 이때는 링크드 리스트를 이용하여 데이터를 추가로 연결하는데, 데이터가 많이 쌓이면 검색 속도가 느려지게 된다.

    2. 여러 스레드에서 동시에 HashMap에 데이터를 추가하면, 배열의 크기가 늘어나야 하는 상황에서도 여러 스레드가 동시에 배열의 크기를 조정하려고 할 수 있다. 이런 경우 서로 다른 스레드가 동시에 배열의 크기를 증가시키려고 할 수 있으며, 이로 인해 배열의 크기가 너무 작아져서 데이터의 재배치(rehashing)가 자주 발생하게 된다.

*재배치란?
◈ HashMap은 내부적으로 배열과 링크드 리스트를 사용하여 데이터를 저장한다. 이때 배열의 크기는 HashMap의 초기 크기와 로드 팩터(load factor)에 따라 결정된다. 만약 배열의 크기가 초기에 설정된 값보다 작아지면, 배열의 크기를 늘리고 모든 데이터를 새로운 배열에 다시 해싱해야 한다. 이 작업이 바로 데이터의 재배치(rehashing)이다.
 
이러한 문제를 해결하기 위해서는 ConcurrentHashMap을 사용하거나, HashMap을 동기화하는 방법을 사용해야 한다. ConcurrentHashMap은 동시에 여러 스레드가 접근해도 안전하게 데이터를 관리할 수 있도록 동기화를 제공하고 또한, HashMap을 동기화할 경우에는 동기화된 블록으로 HashMap의 접근을 제어하여 데이터의 일관성을 보장할 수 있다.

 

HashTable의 동기화 제공 방식

➡️ HashTable은 모든 메서드에 synchronized 키워드를 사용하여, 스레드 간에 동기화를 제공한다. synchronized 키워드를 사용하면, 여러 스레드가 동시에 Hashtable의 메서드에 접근하더라도 하나의 스레드가 해당 메서드를 실행하는 동안 다른 스레드가 대기하도록 한다. 따라서, 동기화를 제공함으로써 멀티스레드 환경에서 데이터 일관성 문제를 방지할 수 있다.

하지만, synchronized 키워드를 사용하면 성능이 저하될 수 있기 때문에, 자바 1.5부터는 ConcurrentHashMap이나 Collections.synchronizedMap 메서드를 사용하여 동시성을 보장하는 Map 자료구조를 사용하는 것이 권장된다. 이러한 자료구조들은 HashTable과 달리, 락(lock)을 더욱 세분화하여 성능을 향상할 수 있다.

 

HashMap과 HashTable 예제

코드의 결과를 보면 알 수 있듯이 HashMap의 결괏값이 예상과는 다르게 나온다.

import java.util.HashMap;
import java.util.Hashtable;

class Main {
    public static void main(String[] args) {
        // HashMap을 사용한 경우
        HashMap<Integer, String> hashMap = new HashMap<>();

        Thread hashMapThread1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                hashMap.put(i, "Value" + i);
            }
        });

        Thread hashMapThread2 = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                hashMap.put(i, "Value" + i);
            }
        });

        hashMapThread1.start();
        hashMapThread2.start();

        try {
            hashMapThread1.join();
            hashMapThread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("HashMap size: " + hashMap.size()); // 예상 결과는 2000이 아닐 수 있음

        // Hashtable을 사용한 경우
        Hashtable<Integer, String> hashtable = new Hashtable<>();

        Thread hashtableThread1 = new Thread(() -> {
            for (int i = 0; i < 1000; i++) {
                hashtable.put(i, "Value" + i);
            }
        });

        Thread hashtableThread2 = new Thread(() -> {
            for (int i = 1000; i < 2000; i++) {
                hashtable.put(i, "Value" + i);
            }
        });

        hashtableThread1.start();
        hashtableThread2.start();

        try {
            hashtableThread1.join();
            hashtableThread2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("Hashtable size: " + hashtable.size()); // 예상 결과는 2000
    }
}

HashMap size: 1978
Hashtable size: 2000

 

⛓ ConcurrentHashMap

---

🔹 ConcurrentHashMap은 멀티스레드 환경에서 안전하게 사용할 수 있는 해시 테이블 구조이다. HashMap과 비슷하지만, 동기화를 적용하는 대신 세분화된 락(lock)을 사용하여 성능을 향상시켰다. 

ConcurrentHashMap의 세분화된 Lock 방식

1.세그먼트(Segment) 락
➡️ ConcurrentHashMap은 내부적으로 여러 개의 세그먼트(Segment)로 나뉘어 있다. 각 세그먼트는 자체적으로 락을 가지고 있으며, 서로 독립적으로 작동한다. 이를 통해 여러 스레드가 동시에 접근해도 서로 다른 세그먼트에서 작업하므로, 락 충돌이 발생할 확률을 줄일 수 있다.
 
2.엔트리(Entry) 락
➡️ ConcurrentHashMap은 각 엔트리(Entry)에 대해 락을 가질 수 있다. 각 세그먼트는 엔트리 락을 사용하여, 해당 세그먼트 내에서 동시에 접근하려는 여러 스레드 간의 경쟁을 제어한다. 엔트리 락은 세그먼트 락보다 작은 범위에서 락 충돌이 발생할 확률을 줄일 수 있다.

 

⛓ LinkedHashMap

---

🔹 LinkedHashMap은 데이터의 삽입 순서를 유지하는 해시 테이블과 연결 리스트를 결합한 자료구조이다. 데이터를 저장할 때 순서대로 저장하기 때문에, 데이터의 순서가 중요한 상황에서 사용하기 적합하다. LinkedHashMap은 동기화가 되어있지 않기 때문에 멀티스레드 환경에서 사용할 때는 주의가 필요하다.

 

🧪 내용 정리

---

HashMap	HashTable	ConcurrentHashMap	LinkedHashMap
멀티스레드 O, 성능↓, 안전성X null값 허용O 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	동기화 지원 null값 허용X 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	멀티스레드 O, 성능↑ 내부적으로 배열과 해시 함수를 사용하여 데이터를 저장	데이터의 순서가 중요한 상황에서 사용 내부적으로 해시 테이블과 링크드 리스트를 사용하여 데이터를 저장

 

📸 참조

---

https://peonyf.tistory.com/entry/JAVA-HashMap%EC%99%80-Enum

https://hee96-story.tistory.com/48