Linked HashMapのソースコード（JDK 1.7）の解読

前の主なHashMapのソースコードの解読。今回はLinked HashMapを研究しています。
 Linked HashMapはHashMapを継承し、双方向チェーンを追加してハッシュ衝突を解決します。
一、コンストラクタ
コンストラクタはHashMapと同じで、HashMapのコンストラクタを呼び出して、accessOrder変数を追加しました。いろいろなコンストラクタを呼び出してtrueまたはfalseを設定します。同時にinit（）方法を書きました。

    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

この方法では、ハッシュ衝突を解決するために双方向チェーンテーブルを初期化する。accessOrderはアクセス順序を制御し、trueであれば、get()要素の時に要素を並べ替え、先ほどgetした元素をリンクの最後のノードに調整し、falseであれば、挿入順に要素を格納する。
二、保存データput（）
まず今のチェーンのノードを見てください。

    private static class Entry extends HashMap.Entry {
       //          、     
        Entry before, after;

        Entry(int hash, K key, V value, HashMap.Entry next) {
            super(hash, key, value, next);
        }

        /**
         *       ，                      
         *                    
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         *     
         */
        private void addBefore(Entry existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         *             
         */
        void recordAccess(HashMap m) {
            LinkedHashMap lm = (LinkedHashMap)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap m) {
            remove();
        }
    }

データを保存しても呼び出されるのは、親タイプのHashMapのput（）です。つまりkeyとvalueに加入する時：
1）keyがnullであれば、keyに対応するhash値を0とし、テーブル配列の0番目の位置に置く。
2）keyがnullでない場合、hash関数から対応するhash値を得て、hash値から対応するテーブル配列のインデックス値を見つけます。
3）対応する位置のチェーン要素に該当するkey値があれば、直接データを更新する
4）新しいkeyとvalueをチェーンに追加しないと、Linked HashMapでaddEntry()とcreateEntry()を複写します。
addEntry()は、最初に要素を加えるかどうかを判定するロジックを追加しました。デフォルトはfalseです

void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        //              
        Entry eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

 createEntryとは、この双方向チェーンを作成することであり、HashMapでシングルチェーンテーブルを作成する考え方と同じです。

 void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry old = table[bucketIndex];
        Entry e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        e.addBefore(header);
        size++;
    }

三、データgetを取る（）
同じHashMapで、直接呼び出したのはshMapのget（）です。

    public V get(Object key) {
        Entry e = (Entry)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

データを取る時、根拠が見えます。 accessOrderはtrueでアクセス順序を調整するかどうか、trueであれば、現在訪問しているkeyに対応するノードをリンクの最後のノードに調整します。
四、まとめ
 
スレッド同期
key/valueはnullを許可しますか？
key/valueは重複を許可していますか？
Linked HashMap
サポートしない
許可
keyは重複を許さない/valueは重複を許さない
HashMapとの違いは、Linked HashMap内部では、ハッシュ・衝突とレコードの挿入順序を解決するための双方向チェーン・テーブルを維持することにある。