[Java] LinkedHashMap

사용자가 입력한 이름 순서대로 플레이어의 카드를 보여줘야하는 요구사항이 있다.

 

해당 요구사항을 만족시키기 위해 어떤 코드를 작성할 수 있을까?

플레이어 리스트를 맵으로 변환하면 되지 않을까?

public Map<String, List<Card>> getPlayerToCard(List<Player> players) {
    return players.stream()
        .collect(Collectors.toMap(Player::getName, Player::getCards));
}

위와 같이 코드를 작성했고, 위의 코드에서는 stream으로 List를 순회하며 map으로 바꾸어준다.

우리는 당연히 요구사항에 맞는 결과값을 예상한다.

 

예상이 맞을까? 한 번 출력해 확인해보자.

아쉽게도 순서가 지켜지지 않았다.

 

그 이유는 무엇일까?

Collectors.toMap 구현을 들여다보자.

public static <T, K, U>
Collector<T, ?, Map<K,U>> toMap(Function<? super T, ? extends K> keyMapper,
                                Function<? super T, ? extends U> valueMapper) {
    return new CollectorImpl<>(HashMap::new,
                               uniqKeysMapAccumulator(keyMapper, valueMapper),
                               uniqKeysMapMerger(),
                               CH_ID);
}

 

내부적으로 새로운 HashMap 객체를 만든다.

HashMap은 Hash값을 이용하여 저장하기 때문에 순서를 보장하지 않는다.

 

그러면 어떻게 순서를 보장해줄 수 있을까?

바로 LinkedHashMap을 사용하면 entry를 map에 추가한 순서를 유지할 수 있다!

 

LinkedHashMap은 어떻게 순서를 보장할 수 있을까?

LinkedHashMap은 이름에서도 알 수 있듯 HashMap의 확장 버전이다.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

LinkedHashMap 구현을 보면, 실제로도 HashMap을 상속받는 것을 알 수 있다.

 

하지만 HashMap과 다르게 Entry내 before, after 엔트리를 저장한다!

 

LinkedHashMap의 Entry들은 이중 연결 리스트로 구현되어있다.

 

    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);
        }
    }

    transient LinkedHashMap.Entry<K,V> head;

    transient LinkedHashMap.Entry<K,V> tail;

즉 LinkedHashMap은  LinkedList와 유사한 방식으로 순서를 보장한다.

 

LinkedHashMap으로 기존 코드를 개선해보자.

다음은 기존 코드이다.

// 기존 코드
public Map<String, List<Card>> getPlayerToCard(List<Player> players) {
    return players.stream()
        .collect(Collectors.toMap(Player::getName, Player::getCards));
}

이를 HashMap이 아닌 LinkedHashMap으로 collect해보자

// 변경된 코드
public Map<String, List<Card>> getPlayerToCard(List<Player> players) {
    return players.stream()
        .collect(Collectors.toMap
            (Player::getName, Player::getCards, (x, y) -> y, LinkedHashMap::new));
}

LinkedHashMap을 사용하니 순서가 보장됐다!

 

stream을 사용하지 않고 for문을 돌면서 요소를 추가하는 방법을 사용해도 된다.

(나는 이 방법을 선택했다. stream을 사용하니 가독성이 떨어지는 느낌이 들어서이다.)

public Map<String, List<Card>> getPlayerToCard(List<Player> players) {
    Map<String, List<Card>> playerToCard = new LinkedHashMap<>();
    for (Player player : players) {
        playerToCard.put(player.getName(), player.getCards());
    }
    return playerToCard;
}

 

 

LinkedHashMap의 복사

지난 포스팅에서 java의 복사 방법에 대해 알아봤다.

[Java] 복사와 불변 (new, unmodifiable, copyOf)

이를 LinkedHashMap에 적용해보자.

copyOf를 이용한 복사 -> 순서보장 X

결론부터 말하면, LinkedHashMap을 Map.copyOf로 복사하는 순간 순서보장이 깨진다.

public static void main(String[] args) {
    Map<Integer, String> originMap = new LinkedHashMap<>();
    originMap.put(1, "1");
    originMap.put(2, "2");
    originMap.put(3, "3");
    originMap.put(4, "4");
    Map<Integer, String> copiedMap = Map.copyOf(originMap);
    printValues(copiedMap);
}


private static void printValues(Map<Integer, String> map) {
    for (Entry<Integer, String> entry : map.entrySet()) {
        System.out.print(entry.getKey());
    }
    System.out.println();
}

그 이유는 Map.copyOf 의 내부 구현을 보면 알 수 있다.

static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
    if (map instanceof ImmutableCollections.AbstractImmutableMap) {
        return (Map<K,V>)map;
    } else {
        return (Map<K,V>)Map.ofEntries(map.entrySet().toArray(new Entry[0]));
    }
}

어디에도 LinkedHashMap에 관련된 내용이 없다.

실제로 copiedMap의 구체 타입은 LinkedHashMap이 아닌, ImmutableCollections.MapN 이다.

그리고, ImmutableCollections.MapN은 순서 보장을 지원하지 않는다.

 

new LinkedHashMap을 이용한 복사 -> 순서보장 O

new LinkedHashMap() 을 통해, 기존 LinkedHashMap 을 복사하면 순서가 보장된다.

public static void main(String[] args) {
    Map<Integer, String> originMap = new LinkedHashMap<>();
    originMap.put(1, "1");
    originMap.put(2, "2");
    originMap.put(3, "3");
    originMap.put(4, "4");
    Map<Integer, String> copiedMap = new LinkedHashMap<>(originMap);
}

 

 

하지만, 기본적으로 LinkedHashMap은 가변이기 때문에 요소를 추가/수정/삭제 할 수 있다.

이러한 연산을 막기 위해선 Collections.unmodifiableMap으로 감싸주면 된다.

public static void main(String[] args) {
    Map<Integer, String> originMap = new LinkedHashMap<>();
    originMap.put(1, "1");
    originMap.put(2, "2");
    originMap.put(3, "3");
    originMap.put(4, "4");
    Map<Integer, String> copiedMap = Collections.unmodifiableMap(new LinkedHashMap<>(originMap));
    copiedMap.put(5, "5");
}

put 연산을 수행할 경우 UnsupportedOperationException 예외가 발생한다.

 

HashMap -> LinkedHashMap 순서보장?

이미 선언된 HashMap을 new LinkedHashMap() 해줌으로써, 순서를 보장시킬 수 있을까?

실험해보자.

public static void main(String[] args) {
    Map<Integer, String> originMap = Map.of(
        1, "[old]1",
        2, "[old]2",
        3, "[old]3",
        4, "[old]4");
    Map<Integer, String> copiedMap = new LinkedHashMap<>(originMap);
    copiedMap.put(5, "[new]5");
    copiedMap.put(6, "[new]6");
    copiedMap.put(7, "[new]7");
    copiedMap.put(8, "[new]8");
    for (Entry<Integer, String> entry : copiedMap.entrySet()) {
        System.out.println(entry.getValue());
    }
}

기존 oldMap(HashMap)에서 엔트리들은 순서가 보장되지 않았고,

이후 copiedMap(LinkedHashMap)에 추가한 엔트리들은 순서가 보장되었다.

 

이는 당연한 결과이다.

새로운 LinkedHashMap 객체를 생성 후 복사할 때, 기존의 엔트리들은 before/after 엔트리를 저장하고 있지 않기 때문에 임의로 지정된다.

하지만, 한 번 임의로 지정된 순서는 계속해서 유지된다.

public static void main(String[] args) {
    /***/
    printValues(copiedMap);
    printValues(copiedMap);
    printValues(copiedMap);
    printValues(copiedMap);
}

private static void printValues(Map<Integer, String> map) {
    for (Entry<Integer, String> entry : map.entrySet()) {
        System.out.print(entry.getKey());
    }
    System.out.println();
}

계속해서 같은 순서로 print된다

LinkedHashMap의 accessOrder 필드

다음은 LinkedHashMap 생성자 코드이다.

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

accessOrder 필드는 뭘까..?

accessOrder 필드 주석을 보면 이와 같은 내용이 적혀있다

The iteration ordering method for this linked hash map: true for access-order, false for insertion-order.

 

대충, accessOrder가 true이면 access-order를 따르고, false면 insertion-order를 따른다는 뜻 같다.

(default는 false 즉, insertion-order이다.)

 

access-order를 임의로 지정해주기 위해선 다음 생성자를 사용하여 LinkedHashMap 객체를 생성하면 된다.

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

 

실험해보자!

public static void main(String[] args) {
    Map<Integer, String> insertOrder = new LinkedHashMap<>(16, 0.75f, false);
    Map<Integer, String> accessOrder = new LinkedHashMap<>(16, 0.75f, true);

    insertOrder.put(1, "1");
    insertOrder.put(2, "2");
    insertOrder.put(3, "3");
    insertOrder.put(4, "4");
    insertOrder.get(2);

    accessOrder.put(1, "1");
    accessOrder.put(2, "2");
    accessOrder.put(3, "3");
    accessOrder.put(4, "4");
    accessOrder.get(2);

    printValues("insertOrder", insertOrder);
    printValues("accessOrder", accessOrder);
}

insertOrder는 put한 순서(맵에 삽입된 순서)가 유지된다. -> FIFO

accessOrder는 삽입/수정/조회된 순서가 유지된다. (최근에 put/get된 요소일수록 뒤에 존재한다.) -> LRU