자바 HashMap, HashSet, LinkedHashMap, LinkedHashSet은 모두 해시 테이블이라는 개념을 기반으로 구현되어 있다. 각 클래스는 해시 테이블의 기본 특성을 활용하면서도 추가적인 기능을 위해 조금씩 다르게 구현되어 있다. 각각의 차이점을 알아보자.
1. HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, SerializableHashMap은 자바에서 가장 기본적인 해시 테이블 기반의 맵이다.
키-값 쌍으로 데이터를 저장하며 값(Value)은 중복을 허용하지만 키(Key)는 중복을 허용하지 않는다.
element의 삽입 순서를 보장하지 않는다.
데이터의 순서가 중요하지 않고, 단순히 키-값 매핑이 필요한 경우에 사용하기 적합하다.
2. HashSet
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
// ...
transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
static final Object PRESENT = new Object();
// ...
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// ...
}HashSet은 중복을 허용하지 않는 Set의 구현체로, 내부적으로 HashMap을 기반으로 동작한다.
element의 순서는 보장하지 않는다.
HashSet의 add() 메소드를 보면 element를 키(key)로, 고정된 상수 값(PRESENT)을 값(Value)로 사용하는 HashMap을 내부적으로 사용한다는 것을 알 수 있다. HashMap이 키의 중복을 허용하지 않는다는 점을 활용한 것이다.
데이터의 순서가 중요하지 않고, 중복된 element 없이 고유한 element만 저장해야 할 때 사용한다.
3. LinkedHashMap
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements SequencedMap<K,V>
{
// ...
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
// ...
}LinkedHashMap은 HashMap 클래스를 확장(extends)하며 추가적으로 삽입 순서를 유지하는 클래스이다.
HashMap과 동일하게 키-값 쌍으로 데이터를 저장하지만, HashMap과는 다르게 이중 연결 리스트(LinkedList)도 활용하여 순서를 유지한다. 코드이 before와 after 인스턴스 변수가 각각 이전 Entry와 다음 Entry를 가리키는 포인터 역할을 하는 변수이다.
데이터를 삽입한 순서대로 유지하면서 키-값 매핑이 필요할 때 사용한다.
4. LinkedHashSet
public class LinkedHashSet<E>
extends HashSet<E>
implements SequencedSet<E>, Cloneable, java.io.Serializable {
// ...
public LinkedHashSet() {
super(16, .75f, true);
}
}LinkedHashSet은 HashSet을 확장(extends)하며 추가적으로 삽입 순서를 유지하는 클래스이다.
생성자를 보면 super 클래스인 HashSet의 생성자 중 하나를 호출하는데,
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}따라가보면 위 HashSet 생성자인 것을 알 수 있다. 이로써 LinkedHashSet이 내부적으로 LinkedHashMap을 기반으로 동작한다는 것을 알 수 있다.
LinkedHashSet이 내부적으로 LinkedHashMap을 사용하기 때문에 LinkedHashSet도 순서를 유지하기 위해 내부적으로 이중 연결 리스트(LinkedList)를 사용한다는 것을 의미한다.
중복된 element 없이 고유한 element만 저장해야 하지만, 삽입 순서를 유지해야 할 때 사용한다.
Hashtable 클래스와의 차이점
지금까지 설명한 자료구조와 Hashtable 클래스와의 차이점이 있다. 그것은 지금까지 설명한 클래스들은 스레드 세이프(Thread safe)하지 않다는 것이고 Hashtable은 스레드 세이프하다는 점이다. Hashtable은 스레드의 동기화가 지원되어 스레드 세이프하다.
용어 정리
스레드 세이프 : 여러 스레드가 동시에 특정 코드나 데이터에 접근하더라도 예상치 못한 동작이나 데이터 손상이 발생하지 않도록 보장하는 특성을 말한다. 즉, 멀티 스레드 환경에서도 안전하게 동작할 수 있도록 설계된 것을 의미한다.
동기화 : 여러 개체(프로세스, 스레드, 시스템 등) 간에 데이터를 일치시키는 것(일관되게 유지하는 것). 만약 안드로이드에서 두 개의 리스트가 있는데 하나는 전체 리스트이고 다른 하나는 북마크 리스트라고 가정하자. 북마크 리스트에서 북마크를 해제하면 전체 리스트의 북마크 표시에서도 해제된 상태로 되어 있어야 한다.
스레드 동기화 : 멀티 스레드에서 공유 자원에 접근할 때 한 번에 하나의 스레드만 접근할 수 있도록 제어하는 것(한 스레드가 진행 중인 작업을 다른 스레드가 간섭하지 못하도록 막는 것). 자바의 synchronized 키워드를 이용하면 해당 메서드나 블록을 한번에 한 스레드씩 수행하도록 보장한다.
스레드 세이프에 대한 차이를 알아보기 위해 내부 코드를 살펴보자.
// HashMap.java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}HashMap, HashSet, LinkedHashMap, LinkedHashSet은 데이터를 추가할 때 내부적으로 HashMap의 put() 메소드를 사용한다.
// Hashtable.java
public synchronized V put(K key, V value) {
// ...
}Hashtable의 put() 메소드는 synchronized 키워드를 사용한다. 위에서 설명했지만, synchronized 키워드를 통해 스레드의 동기화를 지원하여 해당 메소드를 한 번에 하나의 스레드만 수행하도록 보장한다.
Hashtable 클래스의 다른 메소드들도 synchronized 키워드가 붙어있다. 하지만 HashMap, HashSet, LinkedHashMap, LinkedHashSet의 메소드들에는 synchronized 키워드가 붙어있지 않다. 그래서 이를 통해 Hashtable은 스레드 세이프하고 이 글에서 설명한 다른 자료구조는 스레드 세이프하지 않다는 차이점을 알 수 있었다.
그리고 한 가지 더 차이점은, HashMap은 키나 값에 null이 저장 가능하지만 Hashtable에서는 불가능하다.
public class Sample {
HashMap map = new HashMap();
Hashtable table = new Hashtable();
public void doSomething() {
map.put("key", null);
table.put("key", null);
}
public static void main(String[] args) {
Sample sample = new Sample();
sample.doSomething();
}
}
/* 실행 결과 :
Exception in thread "main" java.lang.NullPointerException
at java.base/java.util.Hashtable.put(Hashtable.java:477)
at Sample.doSomething(Sample.java:10)
at Sample.main(Sample.java:15)
*/HashMap과 LinkedHashMap의 성능 차이
HashSet과 LinkedHashSet이 내부적으로 각각 HashMap과 LinkedHashMap을 사용하기 때문에 제목을 HashMap과 LinkedHashMap의 성능 차이로 지었다.
HashMap과는 다르게 LinkedHashMap은 순서를 유지하기 위해 추가적으로 이중 연결 리스트(LinkedList)도 같이 사용해야 한다. 그래서 메모리 사용량이 HashMap보다 LinkedHashMap이 더 높고, 일반적으로 HashMap이 LinkedHashMap보다 더 빠른 성능을 제공한다.
그런데 이 글을 보면 실제로 사용할 때 속도 차이는 별로 없다고 한다. 해당 글에서 stackoverflow 링크로 연결된다. stackoverflow 답변의 테스트 결과를 보면 LinkedHashMap이 맵을 Create하는 시간이 조금 더 걸리는 반면, Access속도와 Iterate속도가 조금 더 빠르다.
참고자료
