日: 2019年8月10日

JDK

java.util.LinkedHashMap

はらだたかひこ

LinkedHashMapはHashMapクラスを，要素間にリンクを持たせて順序を保持するように拡張したクラスである。実装面においても，「extends HashMap<K, V>という記述がある。内部で保持するキーと値のペアについてもHashMapクラスのものを継承してEntry<K, V>というインナークラスが定義されている。

リンクリストの特徴を顕著に表したのが要素の先頭と末尾を表したエントリーの参照を格納したインスタンス変数headとtailだ。このほかに昇順か降順かを示すboolean型のaccessOrderというインスタンス変数が定義されている。

コンストラクタは，次の5種類が定義されている。最初の3つはスーパークラスのコンストラクタの定義とほぼ同じである。同じ引数をとるスーパークラスのコンストラクタを呼び出した上で，accessOrderはいずれもfalseをセットしている。4つめのコンストラクタは，同じようにスーパークラスの同じ引数をとるコンストラクタを呼び出して，accessOrderにfalseを設定した上で，更に， スーパークラスのputMapEntries(Map, boolean)メソッドを実行する。最後のコンストラクタは，accessOrderも設定できるコンストラクタである。
  • LinkedHashMap(int initialCapacity, float loadFactor)
  • LinkedHashMap(int initialCapacity)
  • LinkedHashMap()
  • LinkedHashMap(Map<? extends K, ? extends V> m)
  • LinkedHashMap(int initialCapacity,float loadFactor, boolean accessOrder)

    • containsValue(Object value)メソッドは，エントリーのvalueに引数と同じものが含まれるかをチェックする。先頭要素を表すhead要素からforループで順次そのafterの要素をたどっていく。そして，引数のオブジェクトと同一または同値のオブジェクトが含まれていればtrueを返す。同値または同一のオブジェクトがみつからなければ，メソッド内の最後の行でfalseを返す。

    get(Object key)メソッドは引数のキーに対応する値を取得する。処理内容はスーパークラスのgetNode()メソッドにキーのハッシュ値とキーを渡してノードを取得する。ハッシュ値を使って検索した方が高速にアクセスできる。

    値を取り出した後，afterNodeAccess(Node e)メソッドを実行して，取得したノードをリンクリストの最後に移動させている。エントリーの後ろの要素を表すafterにnullを設定し，これより後ろには要素がないことを示している。次に現在のエントリーの部分からそのエントリーへのリンクを取り除いて，前後のリンクをつなぎかえる。見つかったエントリーの前の要素が保持している自身へのリンクを，自身の次の要素へのリンクへ変更する。またみつかったエントリーの後の要素が保持している自身へのリンクを自身の前の要素へのリンクへ変更する。そして現在の最後の要素を自身の前の要素を表すbeforeへセットする。

    clear()メソッドは，スーパークラスのclear()メソッドを実行した後，先頭要素を表すheadと末尾要素を表すtailにnullをセットする。

    /*
     * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
     * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     *
     * This code is free software; you can redistribute it and/or modify it
     * under the terms of the GNU General Public License version 2 only, as
     * published by the Free Software Foundation.  Oracle designates this
     * particular file as subject to the "Classpath" exception as provided
     * by Oracle in the LICENSE file that accompanied this code.
     *
     * This code is distributed in the hope that it will be useful, but WITHOUT
     * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
     * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
     * version 2 for more details (a copy is included in the LICENSE file that
     * accompanied this code).
     *
     * You should have received a copy of the GNU General Public License version
     * 2 along with this work; if not, write to the Free Software Foundation,
     * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
     *
     * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
     * or visit www.oracle.com if you need additional information or have any
     * questions.
     */
    package java.util;
    import java.util.function.Consumer;
    import java.util.function.BiConsumer;
    import java.util.function.BiFunction;
    import java.io.IOException;
    public class LinkedHashMap<K,V>
        extends HashMap<K,V>
        implements Map<K,V>
    {
        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);
            }
        }
        private static final long serialVersionUID = 3801124242820219131L;
        transient LinkedHashMap.Entry<K,V> head;
        transient LinkedHashMap.Entry<K,V> tail;
        final boolean accessOrder;
        // internal utilities
        // link at the end of list
        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;
            }
        }
        // apply src's links to dst
        private void transferLinks(LinkedHashMap.Entry<K,V> src,
                                   LinkedHashMap.Entry<K,V> dst) {
            LinkedHashMap.Entry<K,V> b = dst.before = src.before;
            LinkedHashMap.Entry<K,V> a = dst.after = src.after;
            if (b == null)
                head = dst;
            else
                b.after = dst;
            if (a == null)
                tail = dst;
            else
                a.before = dst;
        }
        // overrides of HashMap hook methods
        void reinitialize() {
            super.reinitialize();
            head = tail = null;
        }
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
            LinkedHashMap.Entry<K,V> p =
                new LinkedHashMap.Entry<>(hash, key, value, e);
            linkNodeLast(p);
            return p;
        }
        Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
            LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
            LinkedHashMap.Entry<K,V> t =
                new LinkedHashMap.Entry<>(q.hash, q.key, q.value, next);
            transferLinks(q, t);
            return t;
        }
        TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
            TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
            linkNodeLast(p);
            return p;
        }
        TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
            LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
            TreeNode<K,V> t = new TreeNode<>(q.hash, q.key, q.value, next);
            transferLinks(q, t);
            return t;
        }
        void afterNodeRemoval(Node<K,V> e) { // unlink
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.before = p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a == null)
                tail = b;
            else
                a.before = b;
        }
        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);
            }
        }
        void afterNodeAccess(Node<K,V> e) { // move node to last
            LinkedHashMap.Entry<K,V> last;
            if (accessOrder && (last = tail) != e) {
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                p.after = null;
                if (b == null)
                    head = a;
                else
                    b.after = a;
                if (a != null)
                    a.before = b;
                else
                    last = b;
                if (last == null)
                    head = p;
                else {
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }
        void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }
        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;
        }
        public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(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;
       }
        public void clear() {
            super.clear();
            head = tail = null;
        }
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
        }
        public Set<K> keySet() {
            Set<K> ks = keySet;
            if (ks == null) {
                ks = new LinkedKeySet();
                keySet = ks;
            }
            return ks;
        }
        final class LinkedKeySet extends AbstractSet<K> {
            // 省略
        }
        public Collection<V> values() {
            Collection<V> vs = values;
            if (vs == null) {
                vs = new LinkedValues();
                values = vs;
            }
            return vs;
        }
        final class LinkedValues extends AbstractCollection<V> {
            // 省略
        }
        public Set<Map.Entry<K,V>> entrySet() {
            Set<Map.Entry<K,V>> es;
            return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
        }
        final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
            // 省略
        }
        // Map overrides
        public void forEach(BiConsumer<? super K, ? super V> action) {
            if (action == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                action.accept(e.key, e.value);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
        public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
            if (function == null)
                throw new NullPointerException();
            int mc = modCount;
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
                e.value = function.apply(e.key, e.value);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
        // Iterators
        abstract class LinkedHashIterator {
            // 省略
        }
        final class LinkedKeyIterator extends LinkedHashIterator
            // 省略
        }
        final class LinkedValueIterator extends LinkedHashIterator
            // 省略
        }
        final class LinkedEntryIterator extends LinkedHashIterator
            // 省略
        }
    }