Java LinkedHashMap 밑바닥 실현 원리 분석

실현 에 있어 링크 드 하 쉬 맵 은 여러 가지 방법 으로 하 쉬 맵 에서 직접 계승 하여 양 방향 링크 를 유지 하기 위해 일부 방법 을 복사 했다.따라서 링크 드 하 쉬 맵 의 소스 코드 를 알 아 보 려 면 하 쉬 맵 의 소스 코드 를 먼저 알 아 봐 야 한다.
기본 적 인 상황 에서 링크 드 HashMap 의 교체 순 서 는 노드 를 삽입 하 는 순서에 따른다.또한 accessOrder 매개 변수의 값 을 바 꾸 어 방문 순서에 따라 출력 할 수 있 습 니 다.
여기 서 저 희 는 링크 드 하 쉬 맵 과 하 쉬 맵 의 차이 점 만 토론 합 니 다.링크 드 하 쉬 맵 의 다른 조작 과 특성 은 구체 적 으로 하 쉬 맵 을 참고 하 시기 바 랍 니 다.
우 리 는 먼저 둘 의 차 이 를 살 펴 보 자.

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>();
        map.put("ahdjkf", "1");
        map.put("ifjdj", "2");
        map.put("giafdja", "3");
        map.put("agad", "4");
        map.put("ahdjkge", "5");
        map.put("iegnj", "6");
        System.out.println("LinkedHashMap     (accessOrder=false)：");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
        map1.put("ahdjkf", "1");
        map1.put("ifjdj", "2");
        map1.put("giafdja", "3");
        map1.put("agad", "4");
        map1.put("ahdjkge", "5");
        map1.put("iegnj", "6");

        map1.get("ahdjkf");
        map1.get("ifjdj");
        System.out.println("LinkedHashMap     (accessOrder=true)：");
        Iterator iterator1 = map1.entrySet().iterator();
        while (iterator1.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator1.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map2 = new HashMap<>();
        map2.put("ahdjkf", "1");
        map2.put("ifjdj", "2");
        map2.put("giafdja", "3");
        map2.put("agad", "4");
        map2.put("ahdjkge", "5");
        map2.put("iegnj", "6");

        System.out.println("HashMap     ：");    
        Iterator iterator2 = map2.entrySet().iterator();
        while (iterator2.hasNext()) {
            Map.Entry aMap = (Map.Entry) iterator2.next();
            System.out.println(aMap.getKey() + "=" + aMap.getValue());
        }
    }
}
Output：
LinkedHashMap     (accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap     (accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap     ：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5

링크 드 HashMap 은 데 이 터 를 삽입 할 때마다 데 이 터 를 방문 하고 수정 할 때 링크 의 노드 순 서 를 조정 하 는 것 을 볼 수 있 습 니 다.교체 시 출력 순 서 를 결정 합 니 다.
링크 드 하 쉬 맵 이 어떻게 실현 되 었 는 지 살 펴 보 겠 습 니 다.
LinkedHashMap 은 HashMap 을 계 승 했 고 내부 정적 클래스 Entry 는 HashMap 의 Entry 를 계 승 했 습 니 다.그러나 LinkedHashMap.Entry 는 두 개의 필드 를 더 했 습 니 다.before 와 after,before 는 이 노드 전에 LinkedHashMap 의 그 노드 를 추 가 했 고 after 는 이 노드 뒤에 LinkedHashMap 의 그 노드 를 추 가 했 습 니 다.여기 의 앞 과 뒤 는 시간의 선후 순 서 를 말 합 니 다.

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

이 동시에 클래스 에는 두 개의 구성원 변수 head 와 tail 이 있 는데 각각 내부 양 방향 링크 의 표 두,표 꼬리 를 가리킨다.

//        
transient LinkedHashMap.Entry<K,V> head;
//        
transient LinkedHashMap.Entry<K,V> tail;

링크 드 HashMap 의 accessOrder 필드 를 true 로 설정 한 후,매번 해시 표 에 있 는 노드 를 방문 할 때마다 이 노드 를 링크 의 끝으로 이동 시 켜 이 노드 가 최신 방문 노드 임 을 표시 합 니 다.즉,양 방향 링크 를 순환 하 는 머리 는 가장 오래 방문 한 노드 나 가장 먼저 삽입 한 노드 이 고 꼬리 는 최근 에 방문 하거나 최근 에 삽입 한 노드 이다.
accessOrder 속성 이 증가 하기 때문에 LinkedHashMap 은 HashMap 에 비해 교체 순 서 를 제어 하 는 구조 방법 을 추가 했다.

final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//         ，
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//         ，        
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//         ，        ，           
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
//     Map    
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //        ，      map            。
    putMapEntries(m, false);
}

요소 추가
링크 드 하 쉬 맵 은 요 소 를 추가 할 때 하 쉬 맵 의 put 방법 을 사용 합 니 다.다른 것 은 링크 드 HashMap 에서 new Node()방법 을 다시 썼 습 니 다.새로운 노드 를 구축 할 때마다 링크 Node Last(p)를 통 해.새 노드 를 내부 양 방향 링크 의 끝 에 연결 합 니 다.

//      ，        
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    //         
    if (last == null)
        head = p;
    else {//            
        p.before = last;
        last.after = p;
    }
}

요소 삭제
링크 드 HashMap 은 HashMap 의 reove()방법 을 다시 쓰 지 않 았 으 나,그 는 after Node Removal()방법 을 다시 썼 다.이 방법 은 한 노드 를 삭제 할 때 이 노드 를 양 방향 링크 에서 동시에 삭제 하 는 역할 을 한다.이 방법 은 remove 에서 리 셋 될 것 이다.

//     e ，   e        
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //       p           
    p.before = p.after = null;
    //       null，                a
    if (b == null)
        head = a;
    else//       b       a
        b.after = a;
    //         null ，      b
    if (a == null)
        tail = b;
    else//        a      b
        a.before = b;
}

삭제 과정 은 전체적으로 세 단계 로 나 눌 수 있 습 니 다.
hash 위치 에 따라 통 위치 로4.567917.링크 를 옮 겨 다 니 거나 빨 간 검 은 나무 와 관련 된 삭제 방법

애 프 터 Node Removal 을 되 돌려 링크 드 HashMap 에서 삭제 할 노드 를 제거 합 니 다.

요소 업데이트

//                 
public void clear() {
    super.clear();
    head = tail = null;
}

원소 찾기
LinkedHashMap 은 get()과 getOrDefault()방법 을 다시 썼 습 니 다.
기본적으로 링크 드 HashMap 은 삽입 순서에 따라 링크 를 유지 합 니 다.그러나 링크 드 HashMap 을 초기 화 할 때 accessOrder 인 자 를 true 로 지정 하면 방문 순서에 따라 링크 를 유지 할 수 있 습 니 다.접근 순서 의 원 리 는 get/getOrDefault/replace 등 방법 을 호출 할 때 이 방법 들 이 접근 하 는 노드 를 링크 의 끝으로 이동 하 는 것 입 니 다.

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  //   afterNodeAccess(Node<K,V> e)
        afterNodeAccess(e);  //    e         （      ）
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);    //     
   return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;//    
    //  accessOrder  true ，        e
    if (accessOrder && (last = tail) != e) {
        //  e         p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //p      ，        null
        p.after = null;
        //  p      null， p      ，           p     a
        if (b == null)
            head = a;
        else//    p     b       a
            b.after = a;
        //  p       null，       a      b
        if (a != null)
            a.before = b;
        else//    p      null， p     。      last     p     b
            last = b;
        if (last == null) //      null   ，        
            head = p;
        else {//          p           last， last      p
            p.before = last;
            last.after = p;
        }
        //         p
        tail = p;
        //  modCount。
        ++modCount;
    }
}
//   LinkedHashMap               HashMap                 
LinkedHashMap
public boolean containsValue(Object value) {     
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {   //          
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}
HashMap
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

기타 방법
링크 드 하 쉬 맵 에는 또 하나의 신기 한 존재 가 있다.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //                     
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
//              ，                 
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

위의 방법 은 일반적으로 실행 되 지 않 지만 링크 드 HashMap 을 기반 으로 캐 시 를 실현 할 때 removeEldestEntry 방법 을 덮어 쓰 면 사용자 정의 정책 의 LRU 캐 시 를 실현 할 수 있 습 니 다.예 를 들 어 우 리 는 노드 수량 에 따라 최근 에 가장 적 게 방문 한 노드 를 제거 할 지 여 부 를 판단 하거나 노드 의 생존 시간 에 따라 이 노드 를 제거 할 지 여 부 를 판단 할 수 있다.
교체 기

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        //  LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
    }
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
    abstract class LinkedHashIterator {
        //     
        LinkedHashMap.Entry<K,V> next;
        //    
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;
        LinkedHashIterator() {
            //    ，next   LinkedHashMap            
            next = head;
            //    modCount，   fail-fast
            expectedModCount = modCount;
            //     null
            current = null;
        }
        //      next
        public final boolean hasNext() {
            //    next   null，  next head    
            return next != null;
        }
        //nextNode()        next()   。
        //          ，  LinkedHashMap，                    。
        final LinkedHashMap.Entry<K,V> nextNode() {
            //      e。
            LinkedHashMap.Entry<K,V> e = next;
            //  fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //         null，  
            if (e == null)
                throw new NoSuchElementException();
            //       e
            current = e;
            //        e     
            next = e.after;
            //  e
            return e;
        }
        //            HashMap removeNode  
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

이 방법의 실현 을 통 해 알 수 있 듯 이 교체 링크 드 HashMap 은 내부 에서 유지 하 는 더 블 링크 의 헤더 부터 순환 출력 을 시작 하 는 것 이다.한편,더 블 링크 노드 의 순 서 는 링크 드 HashMap 의 증가,삭제,수정,검사 할 때 모두 업데이트 된다.삽입 순서에 따라 출력 할 지,접근 순서에 따라 출력 할 지 만족 합 니 다.
총결산
일상적인 개발 에서 링크 드 하 쉬 맵 의 사용 빈 도 는 하 쉬 맵 보다 높 지 않 지만 중요 한 실현 이다.
자바 집합 프레임 워 크 에서 HashMap,LinkedHashMap,TreeMap 세 개의 매 핑 클래스 는 서로 다른 데이터 구 조 를 바탕 으로 서로 다른 기능 을 실현 했다.
HashMap 바 텀 은 지퍼 식 의 해시 구 조 를 바탕 으로 JDK 1.8 에 빨 간 검 은 나 무 를 도입 하여 너무 긴 링크 를 최적화 하 는 문제 입 니 다.이러한 구 조 를 바탕 으로 HashMap 은 효율 적 인 첨삭 검사 조작 을 제공 할 수 있다.
링크 드 HashMap 은 그 위 에 양 방향 링크 를 유지 함으로써 해시 데이터 구조의 질 서 를 실현 합 니 다.
TreeMap 밑바닥 은 붉 은 검 은 나무 로 이 루어 지고 붉 은 검 은 나무의 성질 을 이용 하여 키 값 정렬 기능 을 실현 합 니 다.구체 적 으로 우리 의 다음 분석 을 실현 하 다.
이상 은 자바 링크 드 하 쉬 맵 바 텀 실현 원리 분석의 상세 한 내용 입 니 다.자바 링크 드 하 쉬 맵 바 텀 실현 원리 에 관 한 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!