HashMap vs ConcurrentHashMap vs HashTable in Java

들어가며

자바에서 key value 형태로 저장되는 대표적인 자료구조인 HashMap, HashTable, ConcurrentHashMap에 대해서 설명해보려 한다.

HashMap vs HashTable

HashMap과 ConcurrentHashMap은 공통적으로 Entry라는 개념을 가지고 있다. Entry는 key value 한 쌍을 의미하며, 하나의 Entry는 여러개의 Entry를 가지고 있다. Bucket은 Entry를 하나 또는 여러개를 가진 HashMap의 구성 요소이다. HashMap을 초기화 시킬 때, initialCapacity 파라미터를 통하여 Bucket의 크기를 정해줄 수 있다.

 

만약 initialCapacity 보다 많은 버킷을 HashMap에 넣게 된다면 리사이징 과정이 일어나게 된다. 리사이징은 사이즈가 늘어난 새로운 HashMap 생성 + 기존 HashMap 복사 + 새로운 값과 기존 HashMap 붙여넣기 이렇게 세가지 과정으로 이루어진다. 여기서 주목할 점은 리사이징 과정이 원자적 연산이 아니기 때문에 흔히 말하는 동시성 문제가 (멀티 쓰레드 환경에서 데이터의 무결성이 보장 되지 않는 문제) 발생 가능성이 있다.

 

예제 코드를 통해 이해하기 쉽게 설명 해보려 한다.

    final HashMap<Integer, String> map = new HashMap<>(16);
    final Integer targetKey = Integer.MAX_VALUE;
    final String value = "v";

    map.put(targetKey, value);

    Executors.newFixedThreadPool(1).execute(() -> {
      IntStream.range(0, targetKey).forEach(key -> map.put(key, "someValue"));
    });

    while (true) {
      if (map.get(targetKey) == null)
        System.out.println("RESULT IS NULL");
    }

 

위 코드는 멀티 쓰레드 상황에서 동시성 문제가 발생하는 경우를 재현한다. 코드에서 주목할 부분은 while loop 이다. while loop에서는 앞 코드에서 분명 Integer.MAX_VALUE를 키값으로 v라는 값을 넣었지만 null이라는 값을 무한히 내뱉는다.

 

 

이유는 initialCapacity로 설정한 16을 넘기는 Bucket을 HashMap에 넣게되면 리사이징 과정이 진행되기 때문이다. 리사이징 과정은 원자적 연산이 아니기 때문에, 멀티쓰레드 환경에서 값을 복사해서 붙여 넣기 전에 (새로운 사이즈의 HashMap이 생성되었을때) 값을 불러오는 과정에서 NULL 값을 가져오는 결과가 생긴다. 이 문제를 동시성 문제라고 한다.

 

HashMap을 사용하면 앞에서 설명한 것처럼 동시성 문제가 생기게 된다. 동시성 문제를 해결할 수 있는 방법 중의 하나는 HashMap 대신 HashTable를 사용하는 것이다.

 

HashTable은 모든 연산을 수행할 때 하나의 쓰레드만 접근할 수 있도록 한다. 간단한 방법이지만, 이 방법은 멀티쓰레드 환경에서 성능에 큰 영향을 주게 된다. 이유는 하나의 쓰레드 이외에 다른 쓰레드들은 하나의 쓰레드의 연산이 끝날때까지 기다려야 하기 때문이다.

 

성능, 동시성 문제를 동시에 해결하기 위해 ConcurrentHashMap이 등장했다.

HashMap vs ConcurrentHashMap

ConcurrentHashMap은 Lock Striping 기법을 사용한다. Lock Striping 기법이란, 하나의 객체가 여러개의 락을 가질 수 있도록 구현 하여, 여러개의 쓰레드가 동시에 접근할 수 있도록 만들어주는 기법을 의미한다.

 

Lock Striping 기법을 더 깊이있게 이해하기 위해 코드로 직접 구현해 보았다.

public class SegmentExample<K, V> {
  private static class Segment<K, V> {
    private final ReentrantLock lock = new ReentrantLock();
    // 세그먼트 내부의 데이터를 저장하는 해시 맵
    private HashMap<K, V> map = new HashMap<>();

    public V get(K key) {
      lock.lock();
      try {
        return map.get(key);
      } finally {
        lock.unlock();
      }
    }

    public void put(K key, V value) {
      lock.lock();
      try {
        map.put(key, value);
      } finally {
        lock.unlock();
      }
    }

    // 추가적인 메서드들...
  }

  // 전체 해시 테이블
  private Segment[] segments;

  public SegmentExample(int numSegments) {
    segments = new Segment[numSegments];
    for (int i = 0; i < numSegments; i++) {
      segments[i] = new Segment<>();
    }
  }

  public void put(K key, V value) {
    int segmentIndex = getSegmentIndex(key);
    segments[segmentIndex].put(key, value);
  }

  public Object get(K key) {
    int segmentIndex = getSegmentIndex(key);
    return segments[segmentIndex].get(key);
  }

  // 추가적인 메서드들...

  private int getSegmentIndex(K key) {
    int hash = key.hashCode();
    return (hash & Integer.MAX_VALUE) % segments.length;
  }
  
}

 

영어 한국어 일본어 중국어 (간체) 중국어 (번체) 베트남어 인도네시아어 태국어 독일어 러시아어 스페인어 이탈리아어 프강스어

복사하기

 

이 확장을 지원합니다

 

코드를 보면 알 수 있듯이 여러개의 Segment 즉 Bucket을 만들고 Bucket마다 락을 걸어주고 있다. 락의 갯수는 생성자를 통해 변경할 수 있도록 구현했다.

HashTable vs ConcurrentHashMap

앞서 설명했던 것처럼 이론상 ConcurrentHashMap이 더 좋은 성능을 낼 것이다. 아래 코드는 실험을 위해 개발했다.

public class HashMapPerformance {
  public static int ITERATION_COUNT = 10000000;

  private static AtomicInteger exitThreadCount = new AtomicInteger(0);

  public static SegmentExample<Integer, Integer> myHashMap;

  public static void initData() {
    myHashMap = new SegmentExample<>(16);
    for (int counter = 0; counter < 1000; ++counter) {
      myHashMap.put(counter, counter);
    }
  }

  private static class Writer extends Thread {

    @Override
    public void run() {
      Random random = new Random();

      for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) {
        int counter = random.nextInt(1000 - 1);
        myHashMap.put(counter, counter);
      }
      exitThreadCount.incrementAndGet();
    }

  }

  private static class Reader extends Thread {

    @Override
    public void run() {
      Random random =  new Random();

      for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration) {
        int counter = random.nextInt(1000 - 1);
        myHashMap.get(counter);
      }

      exitThreadCount.incrementAndGet();
    }
  }

  public static void main(String[] args) throws InterruptedException {
    initData();

    long start = System.currentTimeMillis();

    for (int counter = 0; counter < 10; ++counter) {
      new Writer().start();
    }

    for (int counter = 0; counter < 10; ++counter) {
      new Reader().start();
    }

    while (exitThreadCount.get() < 20) {
      Thread.sleep(100);
    }

    System.out.println("Total execution Time(ms): " + (System.currentTimeMillis() - start));
  }
}

10개의 쓰레드들은 각각 천만번의 put, get 연산을 수행하게 된다. 성능이 어떻게 나올까? M1 Macbook Pro 16G 환경에서 실험을 진행해 보았다.

 

내가 개발한 Lock Striping HashMap = 13961(ms)

HashTable = 24171(ms)

ConcurrentHashMap = 2286(ms)

HashMap = 1851(ms)

 

생각한대로 HashMap, Concurrent HashMap, HashTable 순서대로 성능이 측정되었다.

 

 

 

English Korean Japanese Chinese (Simplified) Chinese (Traditional) Vietnamese Indonesian Thai German Russian Spanish Italian French

Copy

 

이 확장을 지원합니다

 

 

English Korean Japanese Chinese (Simplified) Chinese (Traditional) Vietnamese Indonesian Thai German Russian Spanish Italian French

Copy

 

이 확장을 지원합니다