JAVA 常用 Map

• HashMap
• ConcurrentHashMap
• TreeMap
• LinkedHashMap
• WeakHashMap
• IdentityHashMap

HashMap

https://www.jianshu.com/p/fde06b74c1d4

ConcurrentHashMap

https://www.jianshu.com/p/fde06b74c1d4

TreeMap

非哈希表，为红黑树结构，即平衡二叉排序树。时间复杂度为 O(logN)
key 需要实现 Comparable 接口

• TreeSet 使用了 TreeMap

    // 二叉排序树遍历
    Comparable<? super K> k = (Comparable<? super K>) key;
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);   // 值相同则覆盖并结束
    } while (t != null);
    
    // 新增节点
     Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    
    // 平衡树
    fixAfterInsertion(e);

LinkedHashMap

继承自 HashMap 并重写 HashMap 中的方法，实现对链表的维护

• LinkedHashSet 使用了 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);
        }
    }

    /**
     * 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;

WeakHashMap

Entry 继承自 WeakReference，通过查询 ReferenceQueue 移除被回收的 Entry
get、put、size 等方法均会触发对 ReferenceQueue 的查询与移除 Entry

    
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        
        // 新建 Entry 时指定 ReferenceQueue，JVM 回收时会将该对象放入 queue
        Entry(Object key, V value,
              ReferenceQueue<Object> queue,
              int hash, Entry<K,V> next) {
            super(key, queue);
            this.value = value;
            this.hash  = hash;
            this.next  = next;
        }       
    }

IdentityHashMap

判断key值的相同，通过 == (即引用相同) 而非 equals
因此对于值相同但不同引用的 key，均会保存

val map = new IdentityHashMap<Object, String>();

        val a = new Object();
        val b = new Object();

        map.put(a, "a");
        map.put(b, "b");

        assert map.get(a) == "a";
        assert map.get(b) == "b";

        val c = a;
        map.put(c, "c");

        assert map.get(c) == map.get(a);
        assert map.get(c) == "c";