[JAVA] 컬렉션 프레임워크(3) 맵 Map | HashMap, TreeMap, LinkedHashMap

맵(Map)

{키:값}으로 구성된 객체를 저장하는 자료구조이다. 키는 중복 저장할 수 없으나 값은 중복 저장이 가능하다. 중복된 키에 대해서는 새로운 값으로 대체한다.

인덱스가 없어 리스트처럼 인덱스로 접근하는 방식이 아닌 키로 값에 접근한다.

 

 

HashTable

컬렉션 프레임워크가 만들어지기 전 jdk1.0부터 있었던 API이다. 

해시테이블과 해시맵 둘 다 키에 대한 해시 값을 사용하여 값을 저장, 조회, 동적으로 크기가 증가하는 자료구조이라고 할 수 있다.

해시테이블 생성

Map map = new Hashtable();
Hashtable<Integer, String> map = new Hashtable<Integer, String>();
Hashtable<Integer, String> map = new Hashtable<Integer, String>(10); // 초기 용량 지정

과거 사용되던 자료구조로 사용은 지양된다.

 

기본 capaticy는 11, load factor는 0.75, 크기가 부족하여 늘릴 때는 2배로 늘린다.

/**
 * Constructs a new, empty hashtable with a default initial capacity (11)
 * and load factor (0.75).
 */
public Hashtable() {
    this(11, 0.75f);
}

/**
 * Constructs a new hashtable with the same mappings as the given
 * Map.  The hashtable is created with an initial capacity sufficient to
 * hold the mappings in the given Map and a default load factor (0.75).
 *
 * @param t the map whose mappings are to be placed in this map.
 * @throws NullPointerException if the specified map is null.
 * @since   1.2
 */
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

해시맵과 다르게 해시테이블은 멀티스레드 환경에서 동기화를 보장한다. 클래스 내부 메서드들에 synchronized 키워드가 사용된 것을 확인할 수 있다.

public synchronized int size() {
    return count;
}

public synchronized boolean isEmpty() {
    return count == 0;
}

public synchronized Enumeration<K> keys() {
    return this.<K>getEnumeration(KEYS);
}

...

 

 

HashMap

Java2부터 등장한 컬렉션 프레임워크의 API로 해시테이블과 마찬가지로 Map 인터페이스를 구현하고 있다.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

해시테이블과 다르게 보조 해시 함수를 사용하기 때문에 해시 충돌이 덜 발생할 수 있어 성능상으로 이점이 있다. 

 

해시테이블과 다르게 thread-safe 하지 않다.하지만 단일 스레드 환경에서 해시맵의 성능이 더 좋기 때문에 해시맵을 사용하며 동기화가 필요한 시점에 ConcurrentHashMap을 사용하는 것을 권장한다.

해시테이블은 키값에 null을 허용하지 않지만 해시맵은 키값에 null이 허용된다.

해시테이블은 not fail-fast Enumeration을 제공하지만 해시맵은 Enumeration이 아닌 Iterator(fail-fast)를 제공한다.

 

* Enumeration vs Iterator

자바에서 제공하는 컬렉션에 대해 순차적으로 접근할 때 사용된다.

Enumeration은 초기 사용되었으나 jdk1.2 이후 등장한 Iteraotr은 컬렉션 인터페이스를 구현 상속한 모든 컬렉션 클래스에서 사용 가능하다.

Enumeration은 컬렉션 집합을 통째로 복사하여 사용하기 때문에 Fail-Fast를 지원하지 않지만 Iterotordms Fail-Fast 방식으로 동작하여 접근자 생성 후 컬렉션에 변화가 생기면 ConcurrentModificationException이 발생한다.

Fail-Fast 방식이란 접근자 생성 후 컬렉션에 추가, 수정 등 변화가 생기면 에러가 발생하는 방식이다.

 

해시맵 생성

HashMap<String, Integer> map = new HashMap<String,Integer>();
HashMap<String,Integer> map = new HashMap<>();
HashMap<String, Integer> map = new HashMap<>(map); // 다른 map으로 초기화
HashMap<String, Integer> map = new HashMap<>(10); // 초기용량
HashMap<String, Integer> map = new HashMap<>(10, 0.7f); // 초기용량, load factor
HashMap<String,String> map6 = new HashMap<String,String>(){{ 
    put("a","b"); // 초기화하면서 추가
}};

추가

map.put("hello", 1);
map.put("world", 2);
// {world=2, hello=1}

조회 

// key: world / value: 2
// key: hello / value: 1

// entrySet() 키와 값 모두 조회
for(Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("key: " + entry.getKey() + " / value: " + entry.getValue());
}

// keySet() 키 조회
for(String s : map.keySet()) {
    System.out.println("key: " + s + " value: " + map.get(s));
}

// keySet() + Iterator
Iterator<String> keys = map.keySet().iterator();
while(keys.hasNext()) {
    String key = keys.next();
    System.out.println("key: " + key + " / value: " + map.get(key));
}

특정 값이 있는지 확인

// 특정 키가 있는지
boolean isContains = map.containsKey("hi");
// 특정 키에 대한 값 조회
map.get("hello"); // key==hello 값 조회

수정

map.replace("hello", 100);

삭제

map.remove("hello"); // key로 삭제
map.clear();

 

 

TreeMap

해시맵과 다르게 데이터가 트리 구조로 저장되어 있다. 여기서 트리는 레드-블랙 트리(Red-Black Tree)로 구현되어 있어 높이에 따라 성능이 저하되는 것을 방지하고자 한다.

키 값으로 정렬되어 있으며 이는 Comparator를 구현하여 정렬 순서를 변경할 수 있다.

TreeMap<String, Integer> map = new TreeMap<String,Integer>();
TreeMap<String,Integer> map = new TreeMap<>();
TreeMap<String, Integer> map = new TreeMap<>(map1); // 맵으로 초기화
TreeMap<String,String> map = new TreeMap<String,String>(){{ 
    put("a", "b"); // 초기화하면서 추가
}};

정렬 상태를 이용한 Entry 조회

TreeMap<Integer, String> map = new TreeMap<Integer, String>(){{
    put(1, "hello");
    put(2, "world");
    put(3, "bye");
    put(4, "world!");
}};

Integer firstKey = map.firstKey(); // 첫번째 키
System.out.println(firstKey); // 1

Integer floorKey = map.floorKey(3); // n 이하의 키 중 가장 큰 값
System.out.println(floorKey); // 3

Map.Entry<Integer, String> firstEntry = map.firstEntry(); // 가장 첫번째 {키:값}
System.out.println(firstEntry); // 1=hello

Map.Entry<Integer, String> floorEntry = map.floorEntry(4); // 키가 n 이하 중 최댓값의 {키:값}
System.out.println(floorEntry); // 4=world!

Map.Entry<Integer, String> ceilingEntry = map.ceilingEntry(2); // 키가 n 이상 중 최솟값의 {키:값}
System.out.println(ceilingEntry); // 2=world

키 기준 정렬

map.descendingMap() // 내림차순

그 외 추가, 조회, 검색, 수정, 삭제 메서드 해시맵과 동일

 

참고) https://moreget.github.io/dev-00000053-Java-TreeMap,Set/

Java TreeMap, Set을 이용한 자료구조 | Get

 

 

LinkedHashMap

연결해시맵은 다른 맵과 다르게 입력된 순서를 기억한다. 구현체 내 befor, after가 저장되어 있어 이를 통해 순서를 보장한다.

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
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);
    }
}

 

 

++) SortedMap

맵 인터페이스를 상속받은 정렬된 맵 인터페이스이다. 

public interface SortedMap<K,V> extends Map<K,V> {

키가 Integer나 Double과 같이 비교 가능한(Comparable) 타입이거나 SortedMap을 생성하는 시기에 별도의 Comparator를 등록해서 정렬할 수 있다.

맵의 키가 정렬되기 위해서는 아래 두 조건이 필요하다.

- 키가 Comporable 인터페이스를 구현한다(비교가능).

- 맵 인스턴스 생성 단계에 Comparator 구현 객체를 등록한다.

 

대표적인 구현 클래스는 TreeMap이다(SortedMap 인터페이스를 상속한 NavigableMap을 구현한다).

 

** Comparable vs Comparator

Comparable은 정렬 수행 시 기본적으로 적용되는 정렬 기준 메서드를 정의하는 인터페이스이다. 자바에서 제공되는 정렬이 가능한 모든 클래스는 Comparable 인터페이스를 구현하고 있으며 정렬 시 이에 맞게 수행된다.

Comparator는 정렬 가능한 클래스들의 기본 정렬과 다륵 정렬하고 싶을 때 사용하는 인터페이스이다. 기본적인 정렬 방법인 오름차순 정렬을 내림차순으로 정렬할 때 많이 사용된다.

 

 

++) NavigableMap

SortedMap 인터페이스를 구현하는 인터페이스이다. NavigableMap은 주어진 타겟을 이용해 가장 가까운 값을 반환한다.

메서드로 lowerEntry(), floorEntry(), ceilingEntry(), higherEntry(), firstEntry(), ... 가 있고 각각의 반환 타입은 MapEntry이다. 주어진 타겟을 찾지 못하면 null을 반환한다.

 

키의 정렬을 유지하는 TreeMap은 NavigableMap 인터페이스를 상속받는다.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{

* 타겟을 이용하는 연산들(크기 비교를 통해 타겟을 얻는 연산들)은 NavigableMap을 구현한 TreeMap에서만 가능하다.