[DataStructure] LinkedHashMap (Java)

1. LinkedHashMap

Java11

Module java.base
Package java.util
Class LinkedHashMap<K,​V>
java.lang.Object
    java.util.AbstractMap<K,​V>
        java.util.HashMap<K,​V>
            java.util.LinkedHashMap<K,​V>

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values

All Implemented Interfaces:
Serializable, Cloneable, Map<K,​V>

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

2. 설명

반복 순서를 예측할 수 있는 Map 인터페이스의 해시 테이블 및 Linked List 구현.
이 구현은 모든 entries를 통해 실행되는 doubly-linked list를 유지 관리한다는 점에서 HashMap과 다릅니다.
이 linked list는 일반적으로 키가 맵에 삽입된 순서(삽입 순서)인 반복 순서를 정의합니다.
키를 map에 다시 삽입해도 삽입 순서는 영향을 받지 않습니다.
(A key는 m.put 함수가 호출될때 m.contiansKey가 호출 직전에 true를 반환할 때 맵 m에 다시 재 삽입됩니다.)

이 구현은 TreeMap과 관련된 비용 증가 없이 HashMap(및 Hashtable)이 제공하는 지정되지 않은 일반적으로 혼란스러운 순서에서 클라이언트를 보호합니다. 이것은 원본 map의 구현에 관계없이 원본과 동일한 순서의 map 사본을 생성하는 데 사용할 수 있습니다.

void foo(Map m) {
    Map copy = new LinkedHashMap(m);
    ...
}

이 기술은 모듈이 입력 시 맵을 가져와 복사한 다음 나중에 복사본의 순서에 따라 순서가 결정되는 결과를 반환하는 경우에 특히 유용합니다. (사용자는 일반적으로 제공된 것과 동일한 순서로 결과를 받는 것을 좋아합니다.)

링크된 해시맵을 만들기 위해 특별한 생성자가 제공되는데, 이 반복 순서는 가장 적은 접근 횟수 부터(head) 가장 많이에 접근한 항목(tail) (액세스 순서)까지입니다. 이러한 종류의 맵은 LRU(Least Recently Used 가장 최근에 사용되지 않은 것) 캐시를 구축하는 데 적합합니다. put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent 또는 merge 메소드를 호출하면 해당 entry에 액세스 할 수 있습니다(호출이 완료된 후 entry가 존재한다고 가정).
replace 메소드는 값이 대체되는 경우에만 etnry에 액세스합니다.
putAll 메소드는 지정된 맵의 entry set iterator가 key-value 매핑에 대해 하나의 entry access를 생성합니다.
다른 method는 entry accesses를 생성하지 않습니다. 특히 컬레션 뷰에 대한 작업은 backing map의 반복 순서에 영향을 주지 않습니다.

removeEldestEntry(Map.Entry) 메서드는 새 매핑이 맵에 추가될 때 오래된 매핑을 자동으로 제거하는 정책을 적용하도록 재정의될 수 있습니다.

이 클래스는 모든 선택적 Map 작업을 제공하고 null 요소를 허용합니다.
HashMap과 마찬가지로 해시 함수가 버킷 간에 요소를 적절하게 분산한다고 가정하면 기본 작업(추가, 포함 및 제거)에 대해 O(1) 시간복잡도를 제공합니다.
한가지 예외를 제외하고 linked list를 유지관리하는 추가 비용으로 인해 성능은 HashMap보다 약간 낮을 수 있습니다:
LinkedHashMap의 collection-views를 반복하려면 용량에 관계없이 맵 크기에 비례하는 시간이 필요합니다.
HashMap에 대한 반복은 용량에 비례하는 시간을 필요로 하는 더 많은 비용이 들 수 있습니다.

linked hash map은 성능에 영향을주는 두개의 파라미터를 갖고 있습니다. initial capacity 과 load factor 입니다.
그것들은 HashMap처럼 정확하게 정의됩니다. 그러나 이 클래스의 반복 시간은 용량의 영향을 받지 않기 때문에 초기 용량에 대해 지나치게 높은 값을 선택하는 데 따른 패널티는 HashMap보다 이 클래스에서 덜 심각합니다.

이 구현은 동기화 되어 있지 않습니다. 여러 스레드가 연결된 해시 맵에 동시에 액세스하고 스레드 중 하나 이상이 구조적으로 맵을 수정하는 경우 외부에서 동기화되어야 합니다. 이것은 일반적으로 맵을 자연스럽게 캡슐화하는 일부 개체에서 동기화하여 수행됩니다. 그러한 객체가 없으면 Collections.synchronizedMap 메소드를 사용하여 맵을 "래핑"해야 합니다. 맵에 대한 우발적인 동기화되지 않은 액세스를 방지하려면 생성 시 수행하는 것이 가장 좋습니다.삽입 순서 연결된 해시 맵에서 이미 맵에 포함된 키와 연결된 값을 변경하는 것은 구조적 수정이 아닙니다. 액세스 순서 연결된 해시 맵에서 get으로 맵을 쿼리하는 것은 구조적 수정입니다.

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

구조적 수정은 하나 이상의 매핑을 추가 또는 삭제하거나 액세스 순서가 지정된 연결된 해시 맵의 경우 반복 순서에 영향을 미치는 모든 작업입니다.
이 클래스의 모든 컬렉션 보기 메서드에서 반환된 컬렉션의 iterator 메서드에서 반환된 반복기는 fail-fast입니다:반복자가 생성된 후 언제든지 맵이 구조적으로 수정되면 반복자의 자체 제거 메소드를 통하지 않는 방식으로 반복자가 ConcurrentModificationException을 던질 것입니다. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

iterator의 fail-fast 동작은 일반적으로 동기화되지 않은 동시 수정이 있는 상태에서 확실한 보장을 하는 것이 불가능하기 때문에 보장할 수 없습니다. Fail-fast iterator는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 정확성을 위해 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다. 반복기의 빠른 실패 동작은 버그를 감지하는 데만 사용해야 합니다.

이 클래스의 모든 컬렉션 보기 메서드에서 반환된 컬렉션의 spliterator 메서드에서 반환된 spliterators 는 late-binding, fail-fast 그리고 추가로 Spliterator.ORDERED를 보고합니다.

이 클래스는 Java Collections Framework의 멤버입니다.

구현 참고 사항:
이 클래스의 모든 컬렉션 보기 메서드에서 반환된 컬렉션의 spliterator 메서드에서 반환된 spliterators는 해당 컬렉션의 반복자에서 생성됩니다.

Since:
1.4

See Also:
Object.hashCode(), Collection, Map, HashMap, TreeMap, Hashtable, Serialized Form