java有序的Map-LinkedHashMap

java有序的Map-LinkedHashMap

• HashMap中的keySet
• LinkedHashMap中的keySet
• • 两种有序的方式
  • 实现
  • • 实现载体
    • 实现过程
    • • 修改节点的位置
      • 获取keySet
• JAVA集合目录

HashMap中的keySet

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

final class KeySet extends AbstractSet<K> {
    public final int size()                 { return size; }
    public final void clear()               { HashMap.this.clear(); }
    public final Iterator<K> iterator()     { return new KeyIterator(); }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null, false, true) != null;
    }
    public final Spliterator<K> spliterator() {
        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    public final void forEach(Consumer<? super K> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0 && (tab = table) != null) {
            int mc = modCount;
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next)
                    action.accept(e.key);
            }
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }
}

HashMap在获取keySet的时候就是创建了一个Set集合，但是该实体并没有保存实际的信息，而是所有的实现都是HashMap的实现，这样做的好处是不用在添加或者删除的时候去操作这个集合。

HashMap的这个keySet是懒加载的，只有在调用的时候才去建立，减少内存的浪费。

LinkedHashMap中的keySet

两种有序的方式

• 根据插入进行排序
• 根据读取进行排序

public class Main {
    public static void main(String[] args) {
    	// 插入排序
        LinkedHashMap<Integer, Integer> linkedHashMap = new LinkedHashMap<>(8, 0.75F, false);
        linkedHashMap.put(1,2);
        linkedHashMap.put(2,2);
        linkedHashMap.get(1);
        System.out.println(linkedHashMap.keySet());

		// 根据读取及进行排序
        LinkedHashMap<Integer, Integer> linkedHashMapAccess = new LinkedHashMap<>(8, 0.75F, true);
        linkedHashMapAccess.put(1,2);
        linkedHashMapAccess.put(2,2);
        linkedHashMapAccess.get(1);
        System.out.println(linkedHashMapAccess.keySet());
    }
}

实现

实现载体

其中的实现就是依赖于链表的有序结构，再插入删除或者获取数组的时候，添加或者才做节点的位置即可。

    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;

实现过程

修改节点的位置

LinkedHashMap继承自HashMap,所有在实体插入元素的时候，实际是去调用HashMap的方法，在HashMap中有三个方法值得注意。

    // 添加链表使用
    void afterNodeAccess(Node<K,V> p) { }
    // 是否删除最早的节点
    void afterNodeInsertion(boolean evict) { }
    // 删除节点使用
    void afterNodeRemoval(Node<K,V> p) { }

此处是HashMap为我们提供的方法，在所有进行插入，删除，获取的时候都进行了调用，但是HashMap中没有具体实现，如果我们想要自定义一个Map，有一个排序规则，只需要重写这里的方法即可，不用做大面积的修改。一个好的设计是可用于扩展的。

三个方法的具体实在在这里不进行展开，大家可以到LinkedHash源码中查看，就是维护一个链表。

获取keySet

forEach中从头节点开始比比遍历列表。

 final class LinkedKeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { LinkedHashMap.this.clear(); }
        public final Iterator<K> iterator() {
            return new LinkedKeyIterator();
        }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator()  {
            return Spliterators.spliterator(this, Spliterator.SIZED |
                                            Spliterator.ORDERED |
                                            Spliterator.DISTINCT);
        }
        public final void forEach(Consumer<? super K> 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);
            if (modCount != mc)
                throw new ConcurrentModificationException();
        }
    }

JAVA集合目录

java集合目录