이 글의 목적?
면접의 단골 질문이라고 하는 HashTable, HashMap, ConcurrentHashMap에 대해 정리해보자.
이전에 포스팅에서도 언급했지만, 시작하기 전에 해시에 대해서 다시 넘겨짚고 가자. 🚀
-
해시
단방향 암호화 기법으로 해시 함수를 이용하여 고정된 길이의 암호화된 문자열로 바꿔버리는 것을 의미한다. -
해시 함수
해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수다. 매핑 전 원래 데이터를 키로, 매핑 후 데이터를 해시 값으로 매핑하는 과정을 해싱이라고 한다. -
해시 테이블
해시 테이블은 키-값 형태로 저장되며 내부적으로 배열을 이용하여 데이터를 저장하기 때문에 데이터를 빠르게 검색할 수 있는 자료구조다. 키 값에는 해시 함수를 적용해 배열의 고유한 인덱스를 생성하고, 이 인덱스를 이용하여 값을 저장하거나 검색하는데 사용한다. 실제로 값이 저장되는 장소를 버킷이라고 한다. -
해시 값 충돌
해시 알고리즘은 입력값에 대해 항상 같은 해시 값을 반환한다. 또한 입력값은 길이 제한이 없기에 무한정으로 만들 수 있지만, 해시 값은 항상 고정된 길이의 값으로 나타내기에 두 개의 서로 다른 입력값임에도 동일한 결과가 나오는 경우가 있는데 이를 해시 값 충돌이라고 한다. 해결 방법으로는 동일한 인덱스에 있는 버킷에 다음 키 값을 연결하는 체이닝(연결리스트) 방법과 내부적으로 비어있는 빈 공간(버킷)을 찾아 피하는 방식인 오픈어드레싱 방법으로 해결할 수 있다. -
hashCode(), equals()
equals()메소드는 값이 같은지 다른지 - 동등성을 비교한다면,hashCode()는 같은 객체의 고유값에 대해 같은지 다른지 동일성 비교를 한다. 따라서 어떤 두 객체가 같은지 판별하기 위해서는 두 메소드 모두 오버라이딩을 해주어야 한다.equals()만 오버라이딩을 한다면 각각 다른 버킷의 값에 대해서만 비교를 하는 경우가 있을 것이고,hashCode()만 오버라이딩을 했다면, 동일한 버킷을 가르키지만 내부의 값은 비교할 수 없는 문제가 발생하기 때문이다.
HashTable vs HashMap
공통적으로는 Map 인터페이스를 구현했다는 점과 내부적으로 키 값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성하고 이 인덱스를 이용하여 값을 저장하는 것이 동일하다.
// 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() 메소드
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
(생략)...
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}그렇다면 차이가 뭘까? 🤔
HashTable은 Java 1.1에서 등장했고, HashMap은 Java 1.2에서 추가되었다.
위의 코드에서도 살펴볼 수 있듯이, HashTable은 데이터 변경 메소드가 모두 synchronized 예약어가 달린 동기화 메소드로 구현되어있다. 따라서 메소드 호출 전에 스레드간 동기화 락을 걸어 멀티 스레드 환경에서도 데이터의 무결성을 보장해준다. 반대로 HashMap의 경우 동기화를 지원하지 않기 때문에 여러 스레드에서 동시에 접근하게 되면 데이터의 무결성이 손상될 수 있다.
그럼 왜 데이터의 무결성을 보장하지 않는 HashMap이 등장했을까? 🤔
동기화 락 작업은 매우 느린 동작이기 때문에 HashTable은 데이터의 무결성을 지키기 위한 동기화로 인해 속도가 느리다. 따라서 상대적으로 동기화를 처리하지 않는 HashMap이 매우 빠른 처리 속도를 가진다. 즉, 데이터의 무결성을 고려할 필요가 없는 단일 스레드에서는 HashMap을 사용하는 것이 훨씬 효율적이다. 또한 무결성 문제가 발생할 수 있음에도 불구하고 프로그래밍상의 편의성으로 인해 멀티스레드 환경에서도 HashTable보다 HashMap을 많이 선호하는 편이다.
SynchronizedMap
그렇다면 속도와 데이터의 무결성을 지킬 수 있는 방법은 없을까? 당연히 존재한다! 👊
데이터의 처리 속도와 데이터의 무결성은 중요한 문제다. 따라서 빠른 데이터의 처리를 자랑하는 HashMap을 이용하고도 동기화 문제를 해결할 수 있도록 등장한 개념이 SynchronizedMap이다. 어떤 Map 인터페이스를 사용하더라도 Collections.synchronizedMap()로 랩핑해주면, 해당 Map 객체는 동기화 맵이 된다. (SynchronizedMap은 HashTable보다 더 빠른 처리 속도를 가지게 되었다. 😜)
코드를 보면, 내부 클래스로 선언되어있는 것을 알 수 있다. 그리고 'm'이라는 Map 변수와 'mutex'라는 객체를 가지고 있다. 생성자에서는 인자로 받은 Map을 대입하는 부분이 있다.
private static class SynchronizedMap<K,V>
implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
(생략)...그리고 다른 주요 메소드를 확인해보면, 메소드단이 아닌 메소드 내부에 synchronized 예약어가 사용되는 것을 알 수 있다. 코드를 해석해보면 이미 'mutex'에 누군가 접근해있는 상태일 때, 다른 스레드가 접근하려고 하면 블락되는 구조로 구성되어있는 것을 알 수 있다.
public V get(Object key) {
synchronized (mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}ConcurrentHashMap
그럼 Java 1.5 부터 사용가능한 ConcurrentUtil에서 제공하는 ConcurrentHashMap은 뭘까?
앞의 설명을 간단하게 다시 하자면, SynchronizedMap은 Map을 Synchronized로 감싼것이고, 이 내부에 'mutex'라는 잠금 객체를 이용해 동기화를 제공한다.
그리고 get(), put() 메소드를 살펴보면 모두 'mutex'에 synchronized 예약어를 달아두었는데, 이 메소드들이 버킷 단위로 돌아가는 Hash 기반의 자료구조에서 어떤 문제점을 발생시키는지 알아보자.
Map에 '버킷0'에는 0을, '버킷2'에는 2가 들어간다고 가정해보자. '버킷0'에 0을 넣는 동안에 'mutex' 객체로 락을 해두었기 때문에 다른 스레드에서는 접근을 하지 못하는 상태가 된다. 만약 '버킷0'에 0을 넣는 작업이 완료되면 '버킷2'에 2가 들어가는 작업이 수행될 것이다.
이 예시에서 생각해보면, 같은 버킷의 데이터에 접근하는 경우에는 동기화 작업이 필요하지만 서로 다른 버킷에 데이터를 넣을 경우에는 동기화 작업이 필요없다는 것을 알 수 있다. 즉, SynchronizedMap은 전체 단위로 동기화를 수행하다보니 병렬로 수행될 수 있을 작업을 수행하지 못하는 경우가 발생하는 것을 알 수 있다.
그렇다면 ConcurrentHashMap은 어떤 것을 기준으로 락을 걸까? 🔒
ConcurrentHashMap의 put() 메소드만 살펴보자.
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// 빈 버킷에 노드를 삽입하는 경우 락을 사용하지 않고 CompareAndSwap을 이용해 새로운 노드를 해시 버킷에 삽입
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// f = tabAt() : 몇 번째 버킷에 접근할지 계산해서 접근해야할 버팃을 반환
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// casTabAt() : 여러 스레드에서 쓰기 작업을 할 수 있기 때문에 CAS 알고리즘으로 한번 더 안전장치를 거침
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
// synchronized(f) : f 라는 버킷하나를 기준으로 락 (서로 다른 스레드가 같은 해시 버킷에 접근할 때만 해당 블록이 잠기게 됨)
// synchronized(f) 내부 로직 : HashMap과 비슷한 로직으로, 동일한 키면 노드를 새로 바꾸고 해시 충돌인 경우 Seperate Chaining에 추가하거나 TreeNode에 추가하고 TREEFITY_THRESHOLD 값에 따라 링크드리스트를 트리로 변경
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 새로운 노드로 교체
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
// Seperate Chaining에 추가
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
// 트리에 추가
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}코드 내부에 synchronized 예약어가 사용되는 것을 확인할 수 있는데, 이를 통해 알 수 있는 점은 락이 걸리는 단위가 Map 전체가 아닌 버킷 단위로 줄어드는 것을 알 수 있다.
예시를 다시 가져와서 설명한다면, '버킷0'에 0이 추가되는 상황이라면 락이 다음과 같이 걸리게 된다.
이 때, Map 전체에 락이 걸린 것이 아니라 '버팃0'에만 걸린 상태이므로 '버킷2'에도 무리없이 2가 추가된다.
get() 메소드에도 동기화 부분이 없는 것을 알 수 있다.
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}다시 개념을 잡아보자.
앞서 설명한 것과 같이 SynchronizedMap은 Map 컬렉션이 멀티스레드에 안정되게 하기 위한 메소드다. 하지만 동기화를 시켰을 때 하나의 스레드가 전체 컬렉션의 모든 자원을 락시키기 때문에 전체적으로 빠르게 처리하지는 못한다. 그리고 이러한 현상을 해결하기 위해 등장한 것이 바로 ConcurrentHashMap이다.
즉, ConcurrentHashMap은 부분 락을 제공하기 때문에 멀티스레드 환경에서 안정적으로 동작하고 데이터를 병렬적으로 처리할 수 있다. 따라서 HashTable, SynchronizedMap보다 더 나은 성능을 가지고 있다. (단, HashMap과는 다르게 키-값에 null을 허용하지 않는다)
동시성 보장하기 위한 방법
멀티스레드의 경우 공유하는 필드에 대해서 Thread-safe를 보장해주어야 한다. 동시성을 처리하기 위한 방법으로는 volatile, synchronized, Atomic(CAS)가 있다.
volatile
자바에서 변수값을 메인 메모리에 저장하겠다고 명시하는 키워드이다. 매번 변수의 값을 읽을 때마다 CPU의 캐시에 저장된 값이 아닌 메인 메모리에서 읽는 것이다. (추가로, 변수의 값을 쓸 때마다 메인 메모리에까지 작성이 됨)
volatile 변수를 사용하고 있지 않는 멀티스레드 애플리케이션에서는 작업을 수행하는 동안 성능 향상을 위해 메인 메모리에서 읽은 변수 값을 CPU 캐시에 저장한다. 만약 한 스레드가 변경된 값을 캐시 메모리에서 메인 메모리로 데이터를 저장하기전에 다른 스레드에서 메인 메모리의 해당 값을 읽어 변경되기 이전의 값을 처리한다면 데이터가 불일치하는 현상이 발생한다. 하지만 이 경우에 volatile 변수를 이용한다면, 메인 메모리에서 데이터를 읽어오기 때문에 문제를 해결할 수 있다.
단, 여러 스레드가 동시에 쓰기 작업을 수행한다면 문제가 발생한다. 하단의 이미지처럼 동시에 메인 메모리에서 데이터를 읽어와 각각의 CPU 캐시에 저장을 하고, 각 스레드에서 해당 데이터를 수정한 후 메인 메모리에 해당 데이터를 저장할 때 - 각 스레드별로 처리한 결과가 달라져 데이터의 일관성이 깨지는 문제가 발생한다. (가시성 문제)
정리해보자. 결국 volatile은 메인 메모리에 데이터를 저장하는 것으로 동시성을 보장하지만, 한 스레드가 쓰기 작업을, 나머지 스레드는 읽기 작업만을 수행하는 상황에서만 동시성 보장을 할 수 있다는 전제가 붙는다.
synchronized
여러 개의 스레드가 특정 자원을 사용하고자 할 때, 현재 데이터를 사용하고 있는 해당 스레드를 제외하고 나머지 스레드들은 데이터에 접근할 수 없도록 하는 자바의 예약어이다. Thread-safe를 보장해야할 코드만 synchronized 블록으로 감싸주면 더 효율적인 프로그래밍이 가능하다.
단, synchronized에 해당하는 자원에 대해서는 병렬 프로그래밍을 제공하지 않기 때문에 한계가 있다. 이는 대상 자원에 대해 락을 잡는 것이기 때문에 오버헤드가 있고, 데드락을 발생시킬 수 있어 치명적인 단점이 있다. 따라서 실무에서는 거의 사용하지 않는 방식이다.
그럼에도 해당 키워드에 대해 숙지가 필요한 이유는 실무에서 동시성 이슈를 해결한 라이브러리들 간의 코드 비교로 선택지를 좁힐 수 있기 때문이다.
Atomic(CAS - CompareAndSwap)
Atomic은 CAS 방식을 기반으로 멀티스레드 환경에서의 동시성 문제를 해결한다. CAS는 변수의 값을 변경하기 전에 기존에 가지고 있던 값이 내가 예상하던 값과 같을 경우에만 새로운 값을 할당하는 방법이다. 즉, CAS는 값을 변경하기 전에 한 번 더 확인하는 방법이다.
자바에서 제공하는 Atomic 타입들은 CAS를 하드웨어(CPU)의 도움을 받아 한순간에 단 하나의 스레드만 변수의 값을 변경할 수 있도록 제공하고 있다. CAS를 사용하는 이유는 synchronized와 달리 병렬성을 해치지 않으면서 동시성을 보장하기 때문에 더 좋은 성능을 기대할 수 있기 때문이다. 또한 volatile이 가진 가시성 문제도 해결을 할 수 있다.
자바의 Concurrent 패키지의 타입들은 현재 스레드에서 사용되는 값이 메인 메모리의 값과 같은지 비교하고 불일치하면 업데이트된 값을 가져와 계산하는 CAS 알고리즘을 이용해 데이터의 원자성을 보장하고 좋은 성능을 보장한다.
위에서 살펴본 ConcurrentHashMap에서도 CAS를 이용하는 것을 확인할 수 있다.
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}이 글의 레퍼런스
- https://www.youtube.com/watch?v=Vi0hauJemxA (⭐️ 강추)
- https://codingdog.tistory.com/entry/%EC%99%9C-concurrenthashmap%EC%9D%84-%EC%93%B0%EB%8A%94%EC%A7%80-%EA%B0%84%EB%8B%A8%ED%95%98%EA%B2%8C-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4
- https://applefarm.tistory.com/100
- https://didrlgus.github.io/java/05-post/
- https://devlog-wjdrbs96.tistory.com/269
