Map 源码合集

好文。
http://www.jasongj.com/java/concurrenthashmap/

HashMap

https://www.yuque.com/docs/share/ded15ad2-6d64-4bbe-9a31-b83bb0a40675?# 《HashMap源码分析》

HashTable

Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。
Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

package java.util;  
import java.io.*;  
public class Hashtable<K,V>  
    extends Dictionary<K,V>  
    implements Map<K,V>, Cloneable, java.io.Serializable {  
    // 保存key-value的数组。  
    // Hashtable同样采用单链表解决冲突，每一个Entry本质上是一个单向链表  
    private transient Entry[] table;  
    // Hashtable中键值对的数量  
    private transient int count;  
    // 阈值，用于判断是否需要调整Hashtable的容量（threshold = 容量*加载因子）  
    private int threshold;  
    // 加载因子  
    private float loadFactor;  
    // Hashtable被改变的次数，用于fail-fast机制的实现  
    private transient int modCount = 0;  
    // 序列版本号  
    private static final long serialVersionUID = 1421746759512286392L;  
    // 指定“容量大小”和“加载因子”的构造函数  
    public Hashtable(int initialCapacity, float loadFactor) {  
        if (initialCapacity < 0)  
            throw new IllegalArgumentException("Illegal Capacity: "+  
                                               initialCapacity);  
        if (loadFactor <= 0 || Float.isNaN(loadFactor))  
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);  
        if (initialCapacity==0)  
            initialCapacity = 1;  
        this.loadFactor = loadFactor;  
        table = new Entry[initialCapacity];  
        threshold = (int)(initialCapacity * loadFactor);  
    }  
    // 指定“容量大小”的构造函数  
    public Hashtable(int initialCapacity) {  
        this(initialCapacity, 0.75f);  
    }  
    // 默认构造函数。  
    public Hashtable() {  
        // 默认构造函数，指定的容量大小是11；加载因子是0.75  
        this(11, 0.75f);  
    }  
    // 包含“子Map”的构造函数  
    public Hashtable(Map<? extends K, ? extends V> t) {  
        this(Math.max(2*t.size(), 11), 0.75f);  
        // 将“子Map”的全部元素都添加到Hashtable中  
        putAll(t);  
    }  
    public synchronized int size() {  
        return count;  
    }  
    public synchronized boolean isEmpty() {  
        return count == 0;  
    }  
    // 返回“所有key”的枚举对象  
    public synchronized Enumeration<K> keys() {  
        return this.<K>getEnumeration(KEYS);  
    }  
    // 返回“所有value”的枚举对象  
    public synchronized Enumeration<V> elements() {  
        return this.<V>getEnumeration(VALUES);  
    }  
    // 判断Hashtable是否包含“值(value)”  
    public synchronized boolean contains(Object value) {  
        //注意，Hashtable中的value不能是null，  
        // 若是null的话，抛出异常!  
        if (value == null) {  
            throw new NullPointerException();  
        }  
        // 从后向前遍历table数组中的元素(Entry)  
        // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value  
        Entry tab[] = table;  
        for (int i = tab.length ; i-- > 0 ;) {  
            for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {  
                if (e.value.equals(value)) {  
                    return true;  
                }  
            }  
        }  
        return false;  
    }  
    public boolean containsValue(Object value) {  
        return contains(value);  
    }  
    // 判断Hashtable是否包含key  
    public synchronized boolean containsKey(Object key) {  
        Entry tab[] = table;  
        //计算hash值，直接用key的hashCode代替
        int hash = key.hashCode();    
        // 计算在数组中的索引值 
        int index = (hash & 0x7FFFFFFF) % tab.length;  
        // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素  
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
            if ((e.hash == hash) && e.key.equals(key)) {  
                return true;  
            }  
        }  
        return false;  
    }  
    // 返回key对应的value，没有的话返回null  
    public synchronized V get(Object key) {  
        Entry tab[] = table;  
        int hash = key.hashCode();  
        // 计算索引值，  
        int index = (hash & 0x7FFFFFFF) % tab.length;  
        // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素  
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
            if ((e.hash == hash) && e.key.equals(key)) {  
                return e.value;  
            }  
        }  
        return null;  
    }  
    // 调整Hashtable的长度，将长度变成原来的2倍+1 
    protected void rehash() {  
        int oldCapacity = table.length;  
        Entry[] oldMap = table;  
        //创建新容量大小的Entry数组
        int newCapacity = oldCapacity * 2 + 1;  
        Entry[] newMap = new Entry[newCapacity];  
        modCount++;  
        threshold = (int)(newCapacity * loadFactor);  
        table = newMap;  
        //将“旧的Hashtable”中的元素复制到“新的Hashtable”中
        for (int i = oldCapacity ; i-- > 0 ;) {  
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {  
                Entry<K,V> e = old;  
                old = old.next;  
                //重新计算index
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;  
                e.next = newMap[index];  
                newMap[index] = e;  
            }  
        }  
    }  
    // 将“key-value”添加到Hashtable中  
    public synchronized V put(K key, V value) {  
        // Hashtable中不能插入value为null的元素！！！  
        if (value == null) {  
            throw new NullPointerException();  
        }  
        // 若“Hashtable中已存在键为key的键值对”，  
        // 则用“新的value”替换“旧的value”  
        Entry tab[] = table;  
        int hash = key.hashCode();  
        int index = (hash & 0x7FFFFFFF) % tab.length;  
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {  
            if ((e.hash == hash) && e.key.equals(key)) {  
                V old = e.value;  
                e.value = value;  
                return old;  
                }  
        }  
        // 若“Hashtable中不存在键为key的键值对”，
        // 将“修改统计数”+1  
        modCount++;  
        //  若“Hashtable实际容量” > “阈值”(阈值=总的容量 * 加载因子)  
        //  则调整Hashtable的大小  
        if (count >= threshold) {
            rehash();  
            tab = table;  
            index = (hash & 0x7FFFFFFF) % tab.length;  
        }  
        //将新的key-value对插入到tab[index]处（即链表的头结点）
        Entry<K,V> e = tab[index];         
        tab[index] = new Entry<K,V>(hash, key, value, e);  
        count++;  
        return null;  
    }  
    // 删除Hashtable中键为key的元素  
    public synchronized V remove(Object key) {  
        Entry tab[] = table;  
        int hash = key.hashCode();  
        int index = (hash & 0x7FFFFFFF) % tab.length;  
        //从table[index]链表中找出要删除的节点，并删除该节点。
        //因为是单链表，因此要保留带删节点的前一个节点，才能有效地删除节点
        for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {  
            if ((e.hash == hash) && e.key.equals(key)) {  
                modCount++;  
                if (prev != null) {  
                    prev.next = e.next;  
                } else {  
                    tab[index] = e.next;  
                }  
                count--;  
                V oldValue = e.value;  
                e.value = null;  
                return oldValue;  
            }  
        }  
        return null;  
    }  
    // 将“Map(t)”的中全部元素逐一添加到Hashtable中  
    public synchronized void putAll(Map<? extends K, ? extends V> t) {  
        for (Map.Entry<? extends K, ? extends V> e : t.entrySet())  
            put(e.getKey(), e.getValue());  
    }  
    // 清空Hashtable  
    // 将Hashtable的table数组的值全部设为null  
    public synchronized void clear() {  
        Entry tab[] = table;  
        modCount++;  
        for (int index = tab.length; --index >= 0; )  
            tab[index] = null;  
        count = 0;  
    }  
    // 克隆一个Hashtable，并以Object的形式返回。  
    public synchronized Object clone() {  
        try {  
            Hashtable<K,V> t = (Hashtable<K,V>) super.clone();  
            t.table = new Entry[table.length];  
            for (int i = table.length ; i-- > 0 ; ) {  
                t.table[i] = (table[i] != null)  
                ? (Entry<K,V>) table[i].clone() : null;  
            }  
            t.keySet = null;  
            t.entrySet = null;  
            t.values = null;  
            t.modCount = 0;  
            return t;  
        } catch (CloneNotSupportedException e) {   
            throw new InternalError();  
        }  
    }  
    public synchronized String toString() {  
        int max = size() - 1;  
        if (max == -1)  
            return "{}";  
        StringBuilder sb = new StringBuilder();  
        Iterator<Map.Entry<K,V>> it = entrySet().iterator();  
        sb.append('{');  
        for (int i = 0; ; i++) {  
            Map.Entry<K,V> e = it.next();  
            K key = e.getKey();  
            V value = e.getValue();  
            sb.append(key   == this ? "(this Map)" : key.toString());  
            sb.append('=');  
            sb.append(value == this ? "(this Map)" : value.toString());  
            if (i == max)  
                return sb.append('}').toString();  
            sb.append(", ");  
        }  
    }  
    // 获取Hashtable的枚举类对象  
    // 若Hashtable的实际大小为0,则返回“空枚举类”对象；  
    // 否则，返回正常的Enumerator的对象。 
    private <T> Enumeration<T> getEnumeration(int type) {  
    if (count == 0) {  
        return (Enumeration<T>)emptyEnumerator;  
    } else {  
        return new Enumerator<T>(type, false);  
    }  
    }  
    // 获取Hashtable的迭代器  
    // 若Hashtable的实际大小为0,则返回“空迭代器”对象；  
    // 否则，返回正常的Enumerator的对象。(Enumerator实现了迭代器和枚举两个接口)  
    private <T> Iterator<T> getIterator(int type) {  
        if (count == 0) {  
            return (Iterator<T>) emptyIterator;  
        } else {  
            return new Enumerator<T>(type, true);  
        }  
    }  
    // Hashtable的“key的集合”。它是一个Set，没有重复元素  
    private transient volatile Set<K> keySet = null;  
    // Hashtable的“key-value的集合”。它是一个Set，没有重复元素  
    private transient volatile Set<Map.Entry<K,V>> entrySet = null;  
    // Hashtable的“key-value的集合”。它是一个Collection，可以有重复元素  
    private transient volatile Collection<V> values = null;  
    // 返回一个被synchronizedSet封装后的KeySet对象  
    // synchronizedSet封装的目的是对KeySet的所有方法都添加synchronized，实现多线程同步  
    public Set<K> keySet() {  
        if (keySet == null)  
            keySet = Collections.synchronizedSet(new KeySet(), this);  
        return keySet;  
    }  
    // Hashtable的Key的Set集合。  
    // KeySet继承于AbstractSet，所以，KeySet中的元素没有重复的。  
    private class KeySet extends AbstractSet<K> {  
        public Iterator<K> iterator() {  
            return getIterator(KEYS);  
        }  
        public int size() {  
            return count;  
        }  
        public boolean contains(Object o) {  
            return containsKey(o);  
        }  
        public boolean remove(Object o) {  
            return Hashtable.this.remove(o) != null;  
        }  
        public void clear() {  
            Hashtable.this.clear();  
        }  
    }  
    // 返回一个被synchronizedSet封装后的EntrySet对象  
    // synchronizedSet封装的目的是对EntrySet的所有方法都添加synchronized，实现多线程同步  
    public Set<Map.Entry<K,V>> entrySet() {  
        if (entrySet==null)  
            entrySet = Collections.synchronizedSet(new EntrySet(), this);  
        return entrySet;  
    }  
    // Hashtable的Entry的Set集合。  
    // EntrySet继承于AbstractSet，所以，EntrySet中的元素没有重复的。  
    private class EntrySet extends AbstractSet<Map.Entry<K,V>> {  
        public Iterator<Map.Entry<K,V>> iterator() {  
            return getIterator(ENTRIES);  
        }  
        public boolean add(Map.Entry<K,V> o) {  
            return super.add(o);  
        }  
        // 查找EntrySet中是否包含Object(0)  
        // 首先，在table中找到o对应的Entry链表  
        // 然后，查找Entry链表中是否存在Object  
        public boolean contains(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry entry = (Map.Entry)o;  
            Object key = entry.getKey();  
            Entry[] tab = table;  
            int hash = key.hashCode();  
            int index = (hash & 0x7FFFFFFF) % tab.length;  
            for (Entry e = tab[index]; e != null; e = e.next)  
                if (e.hash==hash && e.equals(entry))  
                    return true;  
            return false;  
        }  
        // 删除元素Object(0)  
        // 首先，在table中找到o对应的Entry链表
        // 然后，删除链表中的元素Object  
        public boolean remove(Object o) {  
            if (!(o instanceof Map.Entry))  
                return false;  
            Map.Entry<K,V> entry = (Map.Entry<K,V>) o;  
            K key = entry.getKey();  
            Entry[] tab = table;  
            int hash = key.hashCode();  
            int index = (hash & 0x7FFFFFFF) % tab.length;  
            for (Entry<K,V> e = tab[index], prev = null; e != null;  
                 prev = e, e = e.next) {  
                if (e.hash==hash && e.equals(entry)) {  
                    modCount++;  
                    if (prev != null)  
                        prev.next = e.next;  
                    else 
                        tab[index] = e.next;  
                    count--;  
                    e.value = null;  
                    return true;  
                }  
            }  
            return false;  
        }  
        public int size() {  
            return count;  
        }  
        public void clear() {  
            Hashtable.this.clear();  
        }  
    }  
    // 返回一个被synchronizedCollection封装后的ValueCollection对象  
    // synchronizedCollection封装的目的是对ValueCollection的所有方法都添加synchronized，实现多线程同步  
    public Collection<V> values() {  
    if (values==null)  
        values = Collections.synchronizedCollection(new ValueCollection(),  
                                                        this);  
        return values;  
    }  
    // Hashtable的value的Collection集合。  
    // ValueCollection继承于AbstractCollection，所以，ValueCollection中的元素可以重复的。  
    private class ValueCollection extends AbstractCollection<V> {  
        public Iterator<V> iterator() {  
        return getIterator(VALUES);  
        }  
        public int size() {  
            return count;  
        }  
        public boolean contains(Object o) {  
            return containsValue(o);  
        }  
        public void clear() {  
            Hashtable.this.clear();  
        }  
    }  
    // 重新equals()函数  
    // 若两个Hashtable的所有key-value键值对都相等，则判断它们两个相等  
    public synchronized boolean equals(Object o) {  
        if (o == this)  
            return true;  
        if (!(o instanceof Map))  
            return false;  
        Map<K,V> t = (Map<K,V>) o;  
        if (t.size() != size())  
            return false;  
        try {  
            // 通过迭代器依次取出当前Hashtable的key-value键值对  
            // 并判断该键值对，存在于Hashtable中。  
            // 若不存在，则立即返回false；否则，遍历完“当前Hashtable”并返回true。  
            Iterator<Map.Entry<K,V>> i = entrySet().iterator();  
            while (i.hasNext()) {  
                Map.Entry<K,V> e = i.next();  
                K key = e.getKey();  
                V value = e.getValue();  
                if (value == null) {  
                    if (!(t.get(key)==null && t.containsKey(key)))  
                        return false;  
                } else {  
                    if (!value.equals(t.get(key)))  
                        return false;  
                }  
            }  
        } catch (ClassCastException unused)   {  
            return false;  
        } catch (NullPointerException unused) {  
            return false;  
        }  
        return true;  
    }  
    // 计算Entry的hashCode  
    // 若 Hashtable的实际大小为0 或者 加载因子<0，则返回0。  
    // 否则，返回“Hashtable中的每个Entry的key和value的异或值 的总和”。  
    public synchronized int hashCode() {  
        int h = 0;  
        if (count == 0 || loadFactor < 0)  
            return h;  // Returns zero  
        loadFactor = -loadFactor;  // Mark hashCode computation in progress  
        Entry[] tab = table;  
        for (int i = 0; i < tab.length; i++)  
            for (Entry e = tab[i]; e != null; e = e.next)  
                h += e.key.hashCode() ^ e.value.hashCode();  
        loadFactor = -loadFactor;  // Mark hashCode computation complete  
        return h;  
    }

针对Hashtable，我们同样给出几点比较重要的总结，但要结合与HashMap的比较来总结

1. 二者的存储结构和解决冲突的方法都是相同的
2. HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
3. Hashtable中key和value都不允许为null，而HashMap中key和value都允许为null（key只能有一个为null，而value则可以有多个为null）。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。
4. Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
5. Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。

HashTable是线程安全的。

LinkedHashMap

类继承关系图表
LinkedHashMap 直接继承自HashMap ， HashMap 一切重要的概念 LinkedHashMap 都是拥有的，这就包括了，hash 算法定位 hash 桶位置，哈希表由数组和单链表构成，并且当单链表长度超过 8 的时候转化为红黑树，扩容体系，这一切都跟 HashMap 一样。那么除了这么多关键的相同点以外，LinkedHashMap 比 HashMap 更加强大，这体现在：

• **LinkedHashMap 内部维护了一个双向链表，解决了 不能随时保持遍历顺序和插入顺序一致的问题**``**HashMap**
• **LinkedHashMap 元素的访问顺序也提供了相关支持，也就是我们常说的 LRU（最近最少使用）原则。**

  LinkedHashMap 双向链表的构建过程

  
  HashMap 的存储结构为，数组 + 单链表 + 红黑树，从上边的图片我们也可以看出 LinkedHashMap 底层的存储结构并没有发生变化。
  唯一变化的是使用双向链表（图中红黄箭头部分）记录了元素的添加顺序，我们知道 HashMap 中的 Node 节点只有 next 指针，对于双向链表而言只有 next 指针是不够的，所以 LinkedHashMap 对于 Node 节点进行了拓展：

  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);
   }
  }

  LinkedHashMap 基本存储单元 Entry<K,V> 继承自 HashMap.Node<K,V>,并在此基础上添加了 before 和 after 这两个指针变量。这 before 变量在每次添加元素的时候将会链接上一次添加的元素，而上一次添加的元素的 after 变量将指向该次添加的元素，来形成双向链接。值得注意的是 LinkedHashMap 并没有覆写任何关于 HashMap put 方法。所以调用 LinkedHashMap 的 put 方法实际上调用了父类 HashMap 的方法。
  HashMap 中 newNode 方法无法完成上述所讲的双向链表节点的间的关系，所以 LinkedHashMap 复写了该方法： ```java // HashMap newNode 中实现 Node newNode(int hash, K key, V value, Node next) { return new Node<>(hash, key, value, next); }

// LinkedHashMap newNode 的实现 Node newNode(int hash, K key, V value, Node e) { LinkedHashMap.Entry p = new LinkedHashMap.Entry(hash, key, value, e); // 将 Entry 接在双向链表的尾部 linkNodeLast(p); return p; }

```java
/**
* 该引用始终指向双向链表的头部
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 该引用始终指向双向链表的尾部
*/
transient LinkedHashMap.Entry<K,V> tail;
// newNode 中新节点，放到双向链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    // 添加元素之前双向链表尾部节点
   LinkedHashMap.Entry<K,V> last = tail;
   // tail 指向新添加的节点
   tail = p;
   //如果之前 tail 指向 null 那么集合为空新添加的节点 head = tail = p
   if (last == null)
       head = p;
   else {
       // 否则将新节点的 before 引用指向之前当前链表尾部
       p.before = last;
       // 当前链表尾部节点的 after 指向新节点
       last.after = p;
   }
}

LinkedHashMap 通过调用父类的 HashMap 的 remove 方法将 Hash 表的中节点的删除操作完成即：

1. 获取对应 key 的哈希值 hash(key)，定位对应的哈希桶的位置
2. 遍历对应的哈希桶中的单链表或者红黑树找到对应 key 相同的节点，在最后删除，并返回原来的节点。

对于 afterNodeRemoval（node） HashMap 中是空实现，而该方法，正是 LinkedHashMap 删除对应节点在双向链表中的关系的操作：

//  从双向链表中删除对应的节点 e 为已经删除的节点
void afterNodeRemoval(Node<K,V> e) { 
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将 p 节点的前后指针引用置为 null 便于内存释放
    p.before = p.after = null;
    // p.before 为 null，表明 p 是头节点 
    if (b == null)
        head = a;
    else//否则将 p 的前驱节点连接到 p 的后驱节点
        b.after = a;
    // a 为 null，表明 p 是尾节点
    if (a == null)
        tail = b;
    else //否则将 a 的前驱节点连接到 b 
        a.before = b;
}

LinkedHashMap 维护节点访问顺序

1. HashMap 的遍历结果是跟添加顺序并无关系
2. LinkedHashMap 的遍历结果就是添加顺序

这就是双向链表的作用。双向链表能做的不仅仅是这些，在介绍双向链表维护访问顺序前我们看来看一个重要的参数:

final boolean accessOrder;// 是否维护双向链表中的元素访问顺序

该方法随 LinkedHashMap 构造参数初始化，accessOrder 默认值为 false.
可以看出当我们使用 access 为 true 后，我们访问元素的顺序将会在下次遍历的时候体现，最后访问的元素将最后获得。其实这一切在 HashMap 源码中 putVal/get/repalce 最后都有一个 void afterNodeAccess(Node<K,V> e) 方法，该方法在 HashMap 中是空实现，但是在 LinkedHasMap 中该后置方法，将作为维护节点访问顺序的重要方法，我们来看下其实现:

//将被访问节点移动到链表最后
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;
       //访问节点的后驱置为 null    
       p.after = null;
       //如访问节点的前驱为 null 则说明 p = head
       if (b == null)
           head = a;
       else
           b.after = a;
       //如果 p 不为尾节点 那么将 a 的前驱设置为 b    
       if (a != null)
           a.before = b;
       else
           last = b;
       if (last == null)
           head = p;
       else {
           p.before = last;
           last.after = p;
       }
       tail = p;// 将 p 接在双向链表的最后
       ++modCount;
   }
}

Java 中最简单的 LRU 构建方式

LRU(Least Recently Used) 算法实现的关键就像它名字一样，当达到预定阈值的时候，这个阈值可能是内存不足，或者容量达到最大，找到最近最少使用的存储元素进行移除，保证新添加的元素能够保存到集合中。
HashMap 的 putVal 方法添加完元素后还有个后置操作void afterNodeInsertion(boolean evict){} 就是这个方法。 LinkedHashMap 重写了此方法：

// HashMap 中 putVal 方法实现 evict 传递的 true，表示表处于创建模式。
public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) { .... }
//evict 由上述说明大部分情况下都传 true 表示表处于创建模式
void afterNodeInsertion(boolean evict) { // possibly remove eldest
   LinkedHashMap.Entry<K,V> first;
   //由于 evict = true 那么当链表不为空的时候 且 removeEldestEntry(first) 返回 true 的时候进入if 内部
   if (evict && (first = head) != null && removeEldestEntry(first)) {
       K key = first.key;
       removeNode(hash(key), key, null, false, true);//移除双向链表中处于 head 的节点
   }
}
 //LinkedHashMap 默认返回 false 则不删除节点。 返回 true 双向链表中处于 head 的节点
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
   return false;
}

由上述源码可以看出，如果 removeEldestEntry(Map.Entry<K,V> eldest) 方法返回值为 true 的时候，当我们添加一个新的元素之后，afterNodeInsertion这个后置操作，将会删除双向链表最初的节点，也就是 head 节点。

TreeMap

TreeMap继承于AbstractMap，实现了Map, Cloneable, NavigableMap, Serializable接口。
(1)TreeMap 继承于AbstractMap，而AbstractMap实现了Map接口，并实现了Map接口中定义的方法，减少了其子类继承的复杂度；
(2)TreeMap 实现了Map接口，成为Map框架中的一员，可以包含着key—value形式的元素；
(3)TreeMap 实现了NavigableMap接口，意味着拥有了更强的元素搜索能力；
(4)TreeMap 实现了Cloneable接口，实现了clone()方法，可以被克隆；
(5)TreeMap 实现了Java.io.Serializable接口，支持序列化操作，可通过Hessian协议进行传输。

对于SortedMap来说，该类是TreeMap体系中的父接口，也是区别于HashMap体系最关键的一个接口。
主要原因就是SortedMap接口中定义的第一个方法—-Comparator<? super K> comparator()；

public interface SortedMap<K,V> extends Map<K,V> {
    //返回元素比较器。如果是自然顺序，则返回null；
    Comparator<? super K> comparator();
    //返回从fromKey到toKey的集合：含头不含尾
    java.util.SortedMap<K,V> subMap(K fromKey, K toKey);
    //返回从头到toKey的集合：不包含toKey
    java.util.SortedMap<K,V> headMap(K toKey);
    //返回从fromKey到结尾的集合：包含fromKey
    java.util.SortedMap<K,V> tailMap(K fromKey);
    //返回集合中的第一个元素：
    K firstKey();
    //返回集合中的最后一个元素：
    K lastKey();
    //返回集合中所有key的集合：
    Set<K> keySet();
    //返回集合中所有value的集合：
    Collection<V> values();
    //返回集合中的元素映射：
    Set<Map.Entry<K, V>> entrySet();
}

NavigableMap接口又是对SortedMap进一步的扩展：主要增加了对集合内元素的搜索获取操作，例如：返回集合中某一区间内的元素、返回小于大于某一值的元素等类似操作。

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    //返回小于key的第一个元素：
    Map.Entry<K,V> lowerEntry(K key);
    //返回小于key的第一个键：
    K lowerKey(K key);
    //返回小于等于key的第一个元素：
    Map.Entry<K,V> floorEntry(K key);
    //返回小于等于key的第一个键：
    K floorKey(K key);
    //返回大于或者等于key的第一个元素：
    Map.Entry<K,V> ceilingEntry(K key);
    //返回大于或者等于key的第一个键：
    K ceilingKey(K key);
    //返回大于key的第一个元素：
    Map.Entry<K,V> higherEntry(K key);
    //返回大于key的第一个键：
    K higherKey(K key);
    //返回集合中第一个元素：
    Map.Entry<K,V> firstEntry();
    //返回集合中最后一个元素：
    Map.Entry<K,V> lastEntry();
    //返回集合中第一个元素，并从集合中删除：
    Map.Entry<K,V> pollFirstEntry();
    //返回集合中最后一个元素，并从集合中删除：
    Map.Entry<K,V> pollLastEntry();
    //返回倒序的Map集合：
    java.util.NavigableMap<K,V> descendingMap();
    NavigableSet<K> navigableKeySet();
    //返回Map集合中倒序的Key组成的Set集合：
    NavigableSet<K> descendingKeySet();
    java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                       K toKey, boolean toInclusive);
    java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);
    java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
}

TreeMap具有如下特点：

• 不允许出现重复的key
• 可以插入null键，null值
• 可以对元素进行排序

• 无序集合（插入和遍历顺序不一致）

  TreeMap基本操作

  public class TreeMapTest {
    public static void main(String[] agrs){
        //创建TreeMap对象：
        TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>();
        System.out.println("初始化后,TreeMap元素个数为：" + treeMap.size());
        //新增元素:
        treeMap.put("hello",1);
        treeMap.put("world",2);
        treeMap.put("my",3);
        treeMap.put("name",4);
        treeMap.put("is",5);
        treeMap.put("jiaboyan",6);
        treeMap.put("i",6);
        treeMap.put("am",6);
        treeMap.put("a",6);
        treeMap.put("developer",6);
        System.out.println("添加元素后,TreeMap元素个数为：" + treeMap.size());
        //遍历元素：
        Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
        for(Map.Entry<String,Integer> entry : entrySet){
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("TreeMap元素的key:"+key+",value:"+value);
        }
        //获取所有的key：
        Set<String> keySet = treeMap.keySet();
        for(String strKey:keySet){
            System.out.println("TreeMap集合中的key:"+strKey);
        }
        //获取所有的value:
        Collection<Integer> valueList = treeMap.values();
        for(Integer intValue:valueList){
            System.out.println("TreeMap集合中的value:" + intValue);
        }
        //获取元素：
        Integer getValue = treeMap.get("jiaboyan");//获取集合内元素key为"jiaboyan"的值
        String firstKey = treeMap.firstKey();//获取集合内第一个元素
        String lastKey =treeMap.lastKey();//获取集合内最后一个元素
        String lowerKey =treeMap.lowerKey("jiaboyan");//获取集合内的key小于"jiaboyan"的key
        String ceilingKey =treeMap.ceilingKey("jiaboyan");//获取集合内的key大于等于"jiaboyan"的key
        SortedMap<String,Integer> sortedMap =treeMap.subMap("a","my");//获取集合的key从"a"到"my"的元素
        //删除元素：
        Integer removeValue = treeMap.remove("jiaboyan");//删除集合中key为"jiaboyan"的元素
        treeMap.clear(); //清空集合元素：
        //判断方法：
        boolean isEmpty = treeMap.isEmpty();//判断集合是否为空
        boolean isContain = treeMap.containsKey("jiaboyan");//判断集合的key中是否包含"jiaboyan"
    }
  }

  TreeMap排序

• 使用元素自然排序

在使用自然顺序排序时候，需要区分两种情况：一种是Jdk定义的对象，一种是我们应用自己定义的对象；

public class SortedTest implements Comparable<SortedTest> {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    //自定义对象，实现compareTo(T o)方法：
    public int compareTo(SortedTest sortedTest) {
        int num = this.age - sortedTest.getAge();
        //为0时候，两者相同：
        if(num==0){
            return 0;
        //大于0时，传入的参数小：
        }else if(num>0){
            return 1;
        //小于0时，传入的参数大：
        }else{
            return -1;
        }
    }
}
public class TreeMapTest {
    public static void main(String[] agrs){
        //自然顺序比较
        naturalSort();
    }
     //自然排序顺序：
    public static void naturalSort(){
        //第一种情况：Integer对象
        TreeMap<Integer,String> treeMapFirst = new TreeMap<Integer, String>();
        treeMapFirst.put(1,"jiaboyan");
        treeMapFirst.put(6,"jiaboyan");
        treeMapFirst.put(3,"jiaboyan");
        treeMapFirst.put(10,"jiaboyan");
        treeMapFirst.put(7,"jiaboyan");
        treeMapFirst.put(13,"jiaboyan");
        System.out.println(treeMapFirst.toString());
        //第二种情况:SortedTest对象
        TreeMap<SortedTest,String> treeMapSecond = new TreeMap<SortedTest, String>();
        treeMapSecond.put(new SortedTest(10),"jiaboyan");
        treeMapSecond.put(new SortedTest(1),"jiaboyan");
        treeMapSecond.put(new SortedTest(13),"jiaboyan");
        treeMapSecond.put(new SortedTest(4),"jiaboyan");
        treeMapSecond.put(new SortedTest(0),"jiaboyan");
        treeMapSecond.put(new SortedTest(9),"jiaboyan");
        System.out.println(treeMapSecond.toString());
    }
}

在自然顺序比较中，需要让被比较的元素实现Comparable接口，否则在向集合里添加元素时报：”java.lang.ClassCastException: com.jiaboyan.collection.map.SortedTest cannot be cast to java.lang.Comparable”异常；这是因为在调用put()方法时，会将传入的元素转化成Comparable类型对象，所以当你传入的元素没有实现Comparable接口时，就无法转换，报错。

• 使用自定义比较器排序

使用自定义比较器排序，需要在创建TreeMap对象时，将自定义比较器对象传入到TreeMap构造方法中；
自定义比较器对象，需要实现Comparator接口，并实现比较方法compare(T o1,T o2)；
值得一提的是，使用自定义比较器排序的话，被比较的对象无需再实现Comparable接口了。

public class SortedTest {
    private int age;
    public SortedTest(int age){
        this.age = age;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
}
public class SortedTestComparator implements Comparator<SortedTest> {
    //自定义比较器：实现compare(T o1,T o2)方法：
    public int compare(SortedTest sortedTest1, SortedTest sortedTest2) {
        int num = sortedTest1.getAge() - sortedTest2.getAge();
        if(num==0){//为0时候，两者相同：
            return 0;
        }else if(num>0){//大于0时，后面的参数小：
            return 1;
        }else{//小于0时，前面的参数小：
            return -1;
        }
    }
}
public class TreeMapTest {
    public static void main(String[] agrs){
        //自定义顺序比较
        customSort();
    }
    //自定义排序顺序:
    public static void customSort(){
        TreeMap<SortedTest,String> treeMap = new TreeMap<SortedTest, String>(new SortedTestComparator());
        treeMap.put(new SortedTest(10),"hello");
        treeMap.put(new SortedTest(21),"my");
        treeMap.put(new SortedTest(15),"name");
        treeMap.put(new SortedTest(2),"is");
        treeMap.put(new SortedTest(1),"jiaboyan");
        treeMap.put(new SortedTest(7),"world");
        System.out.println(treeMap.toString());
    }
}

background introduction (tree)

• 二叉查找树

二叉查找树规定：

如果二叉查找树的左子树不为空，那么它的左子树上的任意节点的值都小于根节点的值；
如果二叉查找树的右子树不为空，那么它的右子树上的任意节点的值都大于根节点的值；

• 平衡二叉树（AVL树）

它要求左右子树的高度差的绝对值不能大于1，也就是说左右子树的高度差只能为-1、0、1。

• 红黑树

NIL节点是就是一个假想的或是无实在意义的节点，所有应该指向NULL的指针，都看成指向了NIL节点。包括叶节点的子节点指针或是根节点的父指针（均是指向null的）。

红黑树，即红颜色和黑颜色并存的自平衡二叉查找树，插入的元素节点会被赋为红色或者黑色，待所有元素插入完成后就形成了一颗完整的红黑树。
一颗红黑树必须满足以下几点要求：

1. 树中每个节点必须是有颜色的，要么红色，要么黑色；
2. 树中的根节点必须是黑色的；
3. 树中的叶节点必须是黑色的，也就是树尾的NIL节点或者为null的节点；
4. 树中任意一个节点如果是红色的，那么它的两个子节点一定是黑色的；
5. 任意节点到叶节点（树最下面一个节点）的每一条路径所包含的黑色节点数目一定相同；

首先，我们先来看下在红黑树中，每一个节点的数据结构。

public class TreeNode {
    //节点的值：
    private int data;
    //节点的颜色：
    private String color;
    //指向左孩子的指针：
    private TreeNode leftTreeNode;
    //指向右孩子的指针：
    private TreeNode rightTreeNode;
    //指向父节点的指针
    private TreeNode parentNode;
    public TreeNode(int data, String color, TreeNode leftTreeNode,
                    TreeNode rightTreeNode, TreeNode parentNode) {
        this.data = data;
        this.color = color;
        this.leftTreeNode = leftTreeNode;
        this.rightTreeNode = rightTreeNode;
        this.parentNode = parentNode;
    }
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public String getColor() {return color;}
    public void setColor(String color) {this.color = color;}
    public TreeNode getLeftTreeNode() {
        return leftTreeNode;
    }
    public void setLeftTreeNode(TreeNode leftTreeNode) {
        this.leftTreeNode = leftTreeNode;
    }
    public TreeNode getRightTreeNode() {
        return rightTreeNode;
    }
    public void setRightTreeNode(TreeNode rightTreeNode) {
        this.rightTreeNode = rightTreeNode;
    }
    public TreeNode getParentNode() {return parentNode;}
    public void setParentNode(TreeNode parentNode) {this.parentNode = parentNode;}
}

与HashMap不同，TreeMap底层不是数组结构，成员变量中并没有数组，而是用根节点root来替代，所有的操作都是通过根节点来进行的。

public class TreeMap<K,V>
        extends AbstractMap<K,V>
        implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
    //自定义的比较器：
    private final Comparator<? super K> comparator;
    //红黑树的根节点：
    private transient java.util.TreeMap.Entry<K,V> root = null;
    //集合元素数量：
    private transient int size = 0;
    //对TreeMap操作的数量：
    private transient int modCount = 0;
    //无参构造方法：comparator属性置为null
    //代表使用key的自然顺序来维持TreeMap的顺序，这里要求key必须实现Comparable接口
    public TreeMap() {
        comparator = null;
    }
    //带有比较器的构造方法：初始化comparator属性；
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    //带有map的构造方法：
    //同样比较器comparator为空，使用key的自然顺序排序
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
    //带有SortedMap的构造方法:
    //根据SortedMap的比较器来来维持TreeMap的顺序
    public TreeMap(SortedMap<K, ? extends V> m) {
        comparator = m.comparator();
        try {
            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }
}