선형 표 데이터 구조 해석 (6) 체인 해시 표 구조 - Link dHashMap

지난 글 에서 저 는 여러분 과 함께 HashMap 의 원리 소스 코드 를 읽 었 습 니 다. 어린이 신발 은 링크 를 클릭 하여 선형 표 데이터 구조 해석 (5) 해시 표 구조 - hashMap 을 볼 수 있 습 니 다.    이번 에는 링크 드 하 쉬 맵 을 살 펴 보 겠 습 니 다. 삽입 순 서 를 유지 하고 출력 순서 가 입력 과 같 으 면 링크 드 하 쉬 맵 을 선택 하 십시오.링크 드 하 쉬 맵 의 경우 하 쉬 맵 을 계승 하고 바 텀 에 서 는 하 쉬 표 와 양 방향 링크 를 사용 하여 모든 요 소 를 저장 합 니 다.기본 동작 은 부모 클래스 HashMap 과 비슷 합 니 다. 부모 클래스 와 관련 된 방법 을 다시 써 서 자신의 링크 목록 특성 을 실현 합 니 다.    링크 드 HashMap 은 Map 인터페이스의 해시 표 와 링크 목록 이 실현 되 고 예측 가능 한 교체 순서 가 있 습 니 다.이것 은 선택 할 수 있 는 모든 맵 작업 을 제공 하고 null 값 과 null 키 를 사용 할 수 있 습 니 다.비 치 는 순 서 를 보장 하지 않 습 니 다. 특히 이 순 서 는 영원히 변 하지 않 습 니 다.    링크 드 HashMap 실현 과 HashMap 의 차이 점 은 후자 가 모든 항목 에서 실행 되 는 이중 링크 목록 을 유지 하고 있다 는 것 이다.이 링크 목록 은 교체 순 서 를 정의 합 니 다. 이 교체 순 서 는 삽입 순서 나 방문 순서 일 수 있 습 니 다.
4. 567917. 첫 번 째 는 대열 과 마찬가지 로 기본 값 은 삽입 순서에 따라 순 서 를 매 긴 다. 먼저 들 어 온 것 은 가장 오래된 요소 이 고 팀 의 머리 에 놓 으 면 나중에 먼저 이동 되 고 마지막 에 들 어 온 것 은 새로운 요소 이다
4. 567917. 두 번 째 는 방문 순 서 를 바탕 으로 get 방법 을 호출 한 후에 매번 방문 하 는 요 소 를 팀 끝으로 옮 깁 니 다. 나중에 제거 할 때 팀 헤드 를 제거 합 니 다. 가장 먼저 방문 하 는 요 소 는 마지막 에 제거 되 고 계속 방문 하면 방문 순서에 따라 정렬 하 는 링크 를 형성 할 수 있 습 니 다
아래 그림 은 제 가 작은 칠판 에 손 으로 그린 더 블 체인 순환 링크 입 니 다.
링크 드 하 쉬 맵 의 소스 코드 를 분석 해 보 겠 습 니 다.
초기 화 및 구조 방법

/** *          */
public class LinkedHashMap<K, V> extends HashMap<K, V> {
    /** *          */
    transient LinkedEntry<K, V> header;
    /** * true       ，false       */
    private final boolean accessOrder;
    /** * Constructs a new empty {@code LinkedHashMap} instance. */
    public LinkedHashMap() {
        init();
        accessOrder = false;//        
    }

    public LinkedHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, false);
    }

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

    public LinkedHashMap(Map<? extends K, ? extends V> map) {
        this(capacityForInitSize(map.size()));
        constructorPutAll(map);

    //LinkedHashMap   init()  ，               ，          Entry      
    @Override 
    void init() {
        header = new LinkedEntry<K, V>();
    }

    /** *   HashMap Entry  ，          before      after    */
    static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
                    LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }
    /** *         * Returns the eldest entry in the map, or {@code null} if the map is empty. * @hide */
    public Entry<K, V> eldest() {
        LinkedEntry<K, V> eldest = header.nxt;
        return eldest != header ? eldest : null;
    }
   }

addNewEntry 방법

    /** *    HashMap          */
    @Override 
    void addNewEntry(K key, V value, int hash, int index) {
        //      
        LinkedEntry<K, V> header = this.header;
        //               
        LinkedEntry<K, V> eldest = header.nxt;
        //              （     ） removeEldestEntry true
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);//       key
        }
        // Create new entry, link it on to list, and put it into table
        //              ，      
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;//       table   
    }

아래 그림 은 제 가 작은 칠판 에 손 으로 그린 삽입 방법 으로 원리 도 를 실현 하 는 것 입 니 다. 그 중에서 지침 의 변화 에 주의 하 세 요.
remove 방법

    //        
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return false;
    }

get 방법

    /** * Returns the value of the mapping with the specified key. * @param key the key. * @return the value of the mapping with the specified key, or {@code null} * if no mapping for the specified key is found. */
    @Override public V get(Object key) {
        /* * This method is overridden to eliminate the need for a polymorphic * invocation in superclass at the expense of code duplication. */
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            if (e == null)
                return null;
            if (accessOrder)//       
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }
        return null;
    }

다음 블 로그 에서 저 는 여러분 에 게 LinkedHashMap 의 가장 좋 은 실천 을 가 져 다 드 리 겠 습 니 다. LruCache 캐 시 알고리즘 에 대한 분석 은 LinkedHashMap 의 가장 좋 은 실천: LruCache 를 찾 아 보 세 요.