HashMap

概述

HashMap 是 Map 接口的实现，HashMap 允许空的 key-value 键值对，HashMap 被认为是 Hashtable 的增强版，HashMap 是一个非线程安全的容器，如果想构造线程安全的 Map 考虑使用ConcurrentHashMap。HashMap 是无序的，因为 HashMap 无法保证内部存储的键值对的有序性。
HashMap 是 Map 接口的实现，HashMap 允许空的 key-value 键值对，HashMap 被认为是 Hashtable 的增强版，HashMap 是一个非线程安全的容器，如果想构造线程安全的 Map 考虑使用 ConcurrentHashMap。HashMap 是无序的，因为 HashMap 无法保证内部存储的键值对的有序性。
HashMap 的底层数据结构是数组 + 链表的集合体，数组在 HashMap 中又被称为桶(bucket)。遍历 HashMap 需要的时间损耗为 HashMap 实例桶的数量 + (key - value 映射) 的数量。因此，如果遍历元素很重要的话，不要把初始容量设置的太高或者负载因子设置的太低。
HashMap 实例有两个很重要的因素，初始容量和负载因子，初始容量指的就是 hash 表桶的数量，负载因子是一种衡量哈希表填充程度的标准，当哈希表中存在足够数量的 entry，以至于超过了负载因子和当前容量，这个哈希表会进行 rehash 操作，内部的数据结构重新 rebuilt。
注意 HashMap 不是线程安全的，如果多个线程同时影响了 HashMap ，并且至少一个线程修改了 HashMap 的结构，那么必须对 HashMap 进行同步操作。可以使用 Collections.synchronizedMap(new HashMap) 来创建一个线程安全的 Map。
HashMap 会导致除了迭代器本身的 remove 外，外部 remove 方法都可能会导致 fail-fast 机制，因此尽量要用迭代器自己的 remove 方法。如果在迭代器创建的过程中修改了 map 的结构，就会抛出 ConcurrentModificationException 异常。

HashMap 和 HashTable 的区别

相同点
HashMap 和 HashTable 都是基于哈希表实现的，其内部每个元素都是 key-value 键值对，HashMap 和 HashTable 都实现了 Map、Cloneable、Serializable 接口。
不同点
父类不同：HashMap 继承了 AbstractMap 类，而 HashTable 继承了 Dictionary 类

public class Hashtable<K,V> extends Dictionary<K,V>
        implements Map<K,V>, Cloneable, java.io.Serializable {
}
public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable {
}

空值不同：HashMap 允许空的 key 和 value 值，HashTable 不允许空的 key 和 value 值。HashMap 会把 Null key 当做普通的 key 对待。不允许 null key 重复。

     * @param      key     the hashtable key
     * @param      value   the value
     * @return     the previous value of the specified key in this hashtable,
     *             or <code>null</code> if it did not have one
     * @exception  NullPointerException  if the key or value is
     *               <code>null</code>
     * @see     Object#equals(Object)
     * @see     #get(Object)
     */
    public synchronized V put(K key, V value) {
        // Make sure the value is not null  
        if (value == null) {
            throw new NullPointerException();
        }

线程安全性：HashMap 不是线程安全的，如果多个外部操作同时修改 HashMap 的数据结构比如 add 或者是 delete，必须进行同步操作，仅仅对 key 或者 value 的修改不是改变数据结构的操作。可以选择构造线程安全的 Map 比如 Collections.synchronizedMap 或者是 ConcurrentHashMap。而 HashTable 本身就是线程安全的容器。性能方面：虽然 HashMap 和 HashTable 都是基于单链表的，但是 HashMap 进行 put 或者 get 操作，可以达到常数时间的性能；而 HashTable 的 put 和 get 操作都是加了 synchronized 锁的，所以效率很差。

                    HashMap
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
                    HashTable
    public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }
        addEntry(hash, key, value, index);
        return null;
    }
    public synchronized V get(Object key) {
        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.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

初始容量不同：HashTable 的初始长度是11，之后每次扩充容量变为之前的 2n+1（n为上一次的长度）而 HashMap 的初始长度为16，之后每次扩充变为原来的两倍。创建时，如果给定了容量初始值，那么HashTable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小。

HashMap 和 HashSet 的区别

HashSet 继承于 AbstractSet 接口，实现了 Set、Cloneable,、java.io.Serializable 接口。HashSet 不允许集合中出现重复的值。HashSet 底层其实就是 HashMap，所有对 HashSet 的操作其实就是对 HashMap 的操作。所以 HashSet 也不保证集合的顺序.

HashMap 底层结构

HashMap 的结构：

最主要的三个类(接口)就是 HashMap,AbstractMap和 Map 了，下面来介绍一下 AbstractMap。
AbstractMap 类
这个抽象类是 Map 接口的骨干实现，以求最大化的减少实现类的工作量。为了实现不可修改的 map，程序员仅需要继承这个类并且提供 entrySet 方法的实现即可。它将会返回一组 map 映射的某一段。通常，返回的集合将在AbstractSet 之上实现。这个set不应该支持 add 或者 remove 方法，并且它的迭代器也不支持 remove 方法。
为了实现可修改的 map，程序员必须额外重写这个类的 put 方法(否则就会抛出UnsupportedOperationException)，并且 entrySet.iterator() 返回的 iterator 必须实现 remove() 方法。
Map 接口
Map 接口定义了 key-value 键值对的标准。一个对象支持 key-value 存储。Map不能包含重复的 key，每个键最多映射一个值。这个接口代替了Dictionary 类，Dictionary是一个抽象类而不是接口。
Map 接口提供了三个集合的构造器，它允许将 map 的内容视为一组键，值集合或一组键值映射。map的顺序定义为map映射集合上的迭代器返回其元素的顺序。一些map实现，像是TreeMap类，保证了map的有序性；其他的实现，像是HashMap，则没有保证。
重要内部类和接口
Node 接口
Node节点是用来存储HashMap的一个个实例，它实现了 Map.Entry接口，我们先来看一下 Map中的内部接口 Entry 接口的定义
Map.Entry
// 一个map 的entry 链，这个Map.entrySet()方法返回一个集合的视图，包含类中的元素，// 这个唯一的方式是从集合的视图进行迭代，获取一个map的entry链。这些Map.Entry链只在// 迭代期间有效。/interfaceEntry {K getKey();V getValue();V setValue(V value);booleanequals(Object o);inthashCode();}
Node 节点会存储四个属性，hash值，key，value，指向下一个Node节点的引用
// hash值finalint hash;// 键final K key;// 值V value;// 指向下一个Node节点的Node类型Node next;
因为Map.Entry 是一条条entry 链连接在一起的，所以Node节点也是一条条entry链。构造一个新的HashMap实例的时候，会把这四个属性值分为传入
Node(int hash, K key, V value, Node next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}
实现了 Map.Entry 接口所以必须实现其中的方法，所以 Node 节点中也包括上面的五个方法
KeySet 内部类
keySet 类继承于 AbstractSet 抽象类，它是由 HashMap 中的 keyset() 方法来创建 KeySet 实例的，旨在对HashMap 中的key键进行操作，看一个代码示例

        Map<Integer, String> map = new HashMap<>();
        map.put(1, "1");
        map.put(2, "2");
        map.put(3, "3");
        // 循环遍历
        Set<Integer> set = map.keySet();
        set.forEach(v -> {
            System.out.println(v.intValue());
        });

图中把「1, 2, 3」这三个key 放在了HashMap中，然后使用 lambda 表达式循环遍历 key 值，可以看到，map.keySet() 其实是返回了一个 Set 接口，KeySet() 是在 Map 接口中进行定义的，不过是被HashMap 进行了实现操作，来看一下源码就明白了
// 返回一个set视图，这个视图中包含了map中的key。public Set keySet(){// // keySet 指向的是 AbstractMap 中的 keyset Set ks = keySet;if (ks == null) {// 如果 ks 为空，就创建一个 KeySet 对象// 并对 ks 赋值。 ks = new KeySet(); keySet = ks;}return ks;}
所以 KeySet 类中都是对 Map中的 Key 进行操作的：

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

Values 内部类
Values 类的创建其实是和 KeySet 类很相似，不过 KeySet 旨在对 Map中的键进行操作，Values 旨在对key-value 键值对中的 value 值进行使用，看一下代码示例：

    Collection<String> collection = map.values();
    collection.forEach(v -> {
        System.out.println(v);
    });

循环遍历 Map中的 values值，看一下 values() 方法最终创建的是什么：
public Collection values(){// values 其实是 AbstractMap 中的 valuesCollection vs = values;if (vs == null) { vs = new Values(); values = vs; }return vs;}
所有的 values 其实都存储在 AbstractMap 中，而 Values 类其实也是实现了 Map 中的 Values 接口，看一下对 values 的操作都有哪些方法

    final class Values extends AbstractCollection<V> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<V> iterator()     { return new ValueIterator(); }
        public final boolean contains(Object o) { return containsValue(o); }
        public final Spliterator<V> spliterator() {
            return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super V> 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.value);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

其实是和 key 的操作差不多
EntrySet 内部类
上面提到了HashMap中分别有对 key、value 进行操作的，其实还有对 key-value 键值对进行操作的内部类，它就是 EntrySet，来看一下EntrySet 的创建过程：

    Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
    entrySet.forEach(v -> {
        System.out.println(v.getKey() + "=" + v.getValue());
    });

点进去 entrySet() 会发现这个方法也是在 Map 接口中定义的，HashMap对它进行了重写
// 返回一个 set 视图，此视图包含了 map 中的key-value 键值对public Set> entrySet() { Set> es;return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;}
如果 es 为空创建一个新的 EntrySet 实例，EntrySet 主要包括了对key-value 键值对映射的方法，如下

HashMap 1.7 的底层结构

JDK1.7 中，HashMap 采用位桶 + 链表的实现，即使用链表来处理冲突，同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即 hash 值相等的元素较多时，通过 key 值依次查找的效率较低。它的数据结构如下

HashMap 大致结构
HashMap 底层数据结构就是一个 Entry 数组，Entry 是 HashMap 的基本组成单元，每个 Entry 中包含一个 key-value 键值对。
transient Entry[] table = (Entry[]) EMPTY_TABLE;
而每个 Entry 中包含 「hash, key ,value」 属性，它是 HashMap 的一个内部类
staticclassEntry implementsMap.Entry {final K key; V value; Entry next;int hash; Entry(int h, K k, V v, Entry n) { value = v; next = n; key = k; hash = h; } …}
所以，HashMap 的整体结构就像下面这样

HashMap 1.8 的底层结构

与 JDK 1.7 相比，1.8 在底层结构方面做了一些改变，当每个桶中元素大于 8 的时候，会转变为红黑树，目的就是优化查询效率，JDK 1.8 重写了 resize() 方法。

HashMap 重要属性

「初始容量」
HashMap 的默认初始容量是由 DEFAULT_INITIAL_CAPACITY 属性管理的。
staticfinalint DEFAULT_INITIAL_CAPACITY = 1 << 4;
HashMap 的默认初始容量是 1 << 4 = 16， << 是一个左移操作，它相当于是

「最大容量」
HashMap 的最大容量是
staticfinalint MAXIMUM_CAPACITY = 1 << 30;
这里是不是有个疑问？int 占用四个字节，按说最大容量应该是左移 31 位，为什么 HashMap 最大容量是左移 30 位呢？因为在数值计算中，最高位也就是最左位的位 是代表着符号为，0 -> 正数，1 -> 负数，容量不可能是负数，所以 HashMap 最高位只能移位到 2 ^ 30 次幂。
「默认负载因子」
HashMap 的默认负载因子是
staticfinalfloat DEFAULT_LOAD_FACTOR = 0.75f;
float 类型所以用 .f 为单位，负载因子是和扩容机制有关，这里大致提一下，后面会细说。扩容机制的原则是当 HashMap 中存储的数量 > HashMap 容量 负载因子时，就会把 HashMap 的容量扩大为原来的二倍。
HashMap 的第一次扩容就在 DEFAULT_INITIAL_CAPACITY DEFAULT_LOAD_FACTOR = 12 时进行。
「树化阈值」
HashMap 的树化阈值是
staticfinalint TREEIFY_THRESHOLD = 8;
在进行添加元素时，当一个桶中存储元素的数量 > 8 时，会自动转换为红黑树（JDK1.8 特性）。
「链表阈值」
HashMap 的链表阈值是
staticfinalint UNTREEIFY_THRESHOLD = 6;
在进行删除元素时，如果一个桶中存储元素数量 < 6 后，会自动转换为链表
「扩容临界值」
staticfinalint MIN_TREEIFY_CAPACITY = 64;
这个值表示的是当桶数组容量小于该值时，优先进行扩容，而不是树化
「节点数组」
HashMap 中的节点数组就是 Entry 数组，它代表的就是 HashMap 中 「数组 + 链表」 数据结构中的数组。
transient Node[] table;
Node 数组在第一次使用的时候进行初始化操作，在必要的时候进行 resize，resize 后数组的长度扩容为原来的二倍。
「键值对数量」
在 HashMap 中，使用 size 来表示 HashMap 中键值对的数量。
「修改次数」
在 HashMap 中，使用 modCount 来表示修改次数，主要用于做并发修改 HashMap 时的快速失败 - fail-fast 机制。
「扩容阈值」
在 HashMap 中，使用 threshold 表示扩容的阈值，也就是 初始容量 负载因子的值。
threshold 涉及到一个扩容的阈值问题，这个问题是由 tableSizeFor 源码解决的。我们先看一下它的源码再来解释
staticfinalinttableSizeFor(int cap){int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}
代码中涉及一个运算符 |= ，它表示的是按位或，啥意思呢？你一定知道 「a+=b 的意思是 a=a+b」，那么同理：a |= b 就是 a = a | b，也就是双方都转换为二进制，来进行与操作。如下图所示

我们上面采用了一个比较大的数字进行扩容，由上图可知 2^29 次方的数组经过一系列的或操作后，会算出来结果是 2^30 次方。
所以扩容后的数组长度是原来的 2 倍。
*「负载因子」
loadFactor 表示负载因子，它表示的是 HashMap 中的密集程度。

HashMap 构造函数

在 HashMap 源码中，有四种构造函数
带有初始容量 initialCapacity 和 负载因子 loadFactor 的构造函数

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;       // 扩容的阈值
        this.threshold = tableSizeFor(initialCapacity);
    }

初始容量不能为负，所以当传递初始容量 < 0 的时候，会直接抛出 IllegalArgumentException 异常。如果传递进来的初始容量 > 最大容量时，初始容量 = 最大容量。负载因子也不能小于 0 。然后进行数组的扩容，这个扩容机制也非常重要，我们后面进行探讨
只带有 initialCapacity 的构造函数

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

最终也会调用到上面的构造函数，不过这个默认的负载因子就是 HashMap 的默认负载因子也就是 0.75f
无参数的构造函数

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

默认的负载因子也就是 0.75f
带有 map 的构造函数

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

带有 Map 的构造函数，会直接把外部元素批量放入 HashMap 中。

HashMap put 方法

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果table 为null 或者没有为 table 分配内存，就resize一次
        // 延迟初始化逻辑 初始化hashmap对象中的最耗费内存的散列表
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 指定hash值节点为空则直接插入，这个(n - 1) & hash才是表中真正的哈希
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 如果不为空
        else {
            Node<K,V> e; K k;
            // 计算表中的这个真正的哈希值与要插入的key.hash相比
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 若不同的话，并且当前节点已经在 TreeNode 上了
            else if (p instanceof TreeNode)
                // 采用红黑树存储方式
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // key.hash 不同并且也不再 TreeNode 上，在链表上找到
                    if ((e = p.next) == null) {
                        // 在表尾插入
                        p.next = newNode(hash, key, value, null);
                        // 新增节点后如果节点个数到达阈值，则进入 treeifyBin() 进行再次判断
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果找到了同 hash、key 的节点，那么直接退出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 更新 p 指向下一节点
                    p = e;
                }
            }
            // map中含有旧值，返回旧值i
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // map调整次数 + 1
        ++modCount;
        // 键值对的数量达到阈值，需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

首先看一下 putVal 方法，这个方法是 final 的，如果你自已定义 HashMap 继承的话，是不允许你自己重写 put 方法的，然后这个方法涉及五个参数
· hash -> put 放在桶中的位置，在 put 之前，会进行 hash 函数的计算。
· key -> 参数的 key 值
· value -> 参数的 value 值
· onlyIfAbsent -> 是否改变已经存在的值，也就是是否进行 value 值的替换标志
· evict -> 是否是刚创建 HashMap 的标志
在调用到 putVal 方法时，首先会进行 hash 函数计算应该插入的位置

public V put(K key, V value){
    return putVal(hash(key), key, value, false, true);
}

哈希函数的源码如下

static final inthash(Object key){
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先先来理解一下 hash 函数的计算规则
Hash 函数
hash 函数会根据你传递的 key 值进行计算，首先计算 key 的 hashCode 值，然后再对 hashcode 进行无符号右移操作，最后再和 hashCode 进行异或 ^ 操作。
>>>: 无符号右移操作，它指的是 「无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0」 ，也就是不管是正数还是负数，右移都会在空缺位补 0 。
在得到 hash 值后，就会进行 put 过程。
首先会判断 HashMap 中的 Node 数组是否为 null，如果第一次创建 HashMap 并进行第一次插入元素，首先会进行数组的 resize，也就是重新分配，这里还涉及到一个 resize() 扩容机制源码分析，我们后面会介绍。扩容完毕后，会计算出 HashMap 的存放位置，通过使用 「( n - 1 ) & hash」 进行计算得出。

然后会把这个位置作为数组的下标作为存放元素的位置。如果不为空，那么计算表中的这个真正的哈希值与要插入的 key.hash 相比。如果哈希值相同，key-value 不一样，再判断是否是树的实例，如果是的话，那么就把它插入到树上。如果不是，就执行尾插法在 entry 链尾进行插入。

会根据桶中元素的数量判断是链表还是红黑树。然后判断键值对数量是否大于阈值，大于的话则进行扩容。

扩容机制

在 Java 中，数组的长度是固定的，这意味着数组只能存储固定量的数据。但在开发的过程中，很多时候我们无法知道该建多大的数组合适。好在 HashMap 是一种自动扩容的数据结构，在这种基于变长的数据结构中，扩容机制是非常重要的。
在 HashMap 中，阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时，进行扩容。HashMap 中的扩容机制是由 resize() 方法来实现的

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        // 存储old table 的大小
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 存储扩容阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 如果old table数据已达最大，那么threshold也被设置成最大
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 左移扩大二倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容成原来二倍
                newThr = oldThr << 1; // double threshold
        }
        // 如果oldThr !> 0
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 如果old table <= 0 并且 存储的阈值 <= 0
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 如果扩充阈值为0
        if (newThr == 0) {
            // 扩容阈值为 初始容量*负载因子
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 重新给负载因子赋值
        threshold = newThr;
        // 获取扩容后的数组
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 如果第一次进行table 初始化不会走下面的代码
        // 扩容之后需要重新把节点放在新扩容的数组中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 重新映射时，需要对红黑树进行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 遍历链表，并将链表节点按原顺序进行分组
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 将分组后的链表映射到新桶中
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

上面代码主要做了这几个事情
判断 HashMap 中的数组的长度，也就是 (Node[])oldTab.length() ，再判断数组的长度是否比最大的的长度也就是 2^30 次幂要大，大的话直接取最大长度，否则利用位运算 <<扩容为原来的两倍

        if (oldCap > 0) {
            // 如果old table数据已达最大，那么threshold也被设置成最大
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 左移扩大二倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容成原来二倍
                newThr = oldThr << 1; // double threshold
        }

如果数组长度不大于0 ，再判断扩容阈值 threshold 是否大于 0 ，也就是看有无外部指定的扩容阈值，若有则使用，这里需要说明一下 threshold 何时是 oldThr > 0，因为 oldThr = threshold ，这里其实比较的就是 threshold，因为 HashMap 中的每个构造方法都会调用 HashMap(initCapacity,loadFactor) 这个构造方法，所以如果没有外部指定 initialCapacity，初始容量使用的就是 16，然后根据 this.threshold = tableSizeFor(initialCapacity); 求得 threshold 的值。

        // 如果oldThr !> 0
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;

否则，直接使用默认的初始容量和扩容阈值，走 else 的逻辑是在 table 刚刚初始化的时候。

         // 如果oldThr !> 0
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 如果old table <= 0 并且 存储的阈值 <= 0
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

然后会判断 newThr 是否为 0 ，笔者在刚开始研究时发现 newThr = (int)(DEFAULT_LOAD_FACTOR DEFAULT_INITIAL_CAPACITY); 一直以为这是常量做乘法，怎么会为 0 ，其实不是这部分的问题，在于上面逻辑判断中的扩容操作，可能会导致位溢出。
导致位溢出的示例：oldCap = 2^28 次幂，threshold > 2 的三次方整数次幂。在进入到 float ft = (float)newCap loadFactor; 这个方法是 2^28 2^(3+n) 会直接 > 2^31 次幂，导致全部归零。
*「在扩容后需要把节点放在新扩容的数组中，这里也涉及到三个步骤」
循环桶中的每个 Node 节点，判断 Node[i] 是否为空，为空直接返回，不为空则遍历桶数组，并将键值对映射到新的桶数组中。如果不为空，再判断是否是树形结构，如果是树形结构则按照树形结构进行拆分，拆分方法在 split 方法中。如果不是树形结构，则遍历链表，并将链表节点按原顺序进行分组。

        // 如果第一次进行table 初始化不会走下面的代码
        // 扩容之后需要重新把节点放在新扩容的数组中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        // 重新映射时，需要对红黑树进行拆分
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // 遍历链表，并将链表节点按原顺序进行分组
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 将分组后的链表映射到新桶中
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }

HashMap get 方法

get 方法的过程

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 找到真实的元素位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 总是会check 一下第一个元素
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果不是第一个元素，并且下一个元素不是空的
            if ((e = first.next) != null) {
                // 判断是否属于 TreeNode，如果是 TreeNode 实例，直接从 TreeNode.getTreeNode 取
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 如果还不是 TreeNode 实例，就直接循环数组元素，直到找到指定元素位置
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

来简单介绍下吧，首先会检查 table 中的元素是否为空，然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为 null，为空直接返回，如果不为空，再判断是否是 TreeNode 实例，如果是 TreeNode 实例，则直接使用 TreeNode.getTreeNode 取出元素，否则执行循环，直到下一个元素为 null 位置。
getNode 方法有一个比较重要的过程就是 「(n - 1) & hash」，这段代码是确定需要查找的桶的位置的，那么，为什么要 (n - 1) & hash 呢？
n 就是 HashMap 中桶的数量，这句话的意思也就是说 (n - 1) & hash 就是 (桶的容量 - 1) & hash
// 为什么 HashMap 的检索位置是 (table.size - 1) & hashpublicstaticvoidmain(String[] args){ Map map = new HashMap<>();// debug 得知 1 的 hash 值算出来是 49 map.put(“1”,”cxuan”);// debug 得知 1 的 hash 值算出来是 50map.put(“2”,”cxuan”);// debug 得知 1 的 hash 值算出来是 51 map.put(“3”,”cxuan”);}
那么每次算完之后的 (n - 1) & hash ，依次为

也就是 「tab[(n - 1) & hash]」 算出的具体位置。

HashMap 的遍历方式

HashMap 的遍历，也是一个使用频次特别高的操作
HashMap 遍历的基类是 HashIterator，它是一个 Hash 迭代器，它是一个 HashMap 内部的抽象类，它的构造比较简单，只有三种方法，「hasNext 、 remove 和 nextNode」 方法，其中 nextNode 方法是由三种迭代器实现的
这三种迭代器就就是
· KeyIterator ，对 key 进行遍历
· ValueIterator，对 value 进行遍历
· EntryIterator， 对 Entry 链进行遍历
虽然说看着迭代器比较多，但其实他们的遍历顺序都是一样的，构造也非常简单，都是使用 HashIterator 中的 nextNode 方法进行遍历

    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }
    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

HashIterator 中的遍历方式

    abstract class HashIterator {
        // 下一个 entry 节点
        Node<K,V> next;        // next entry to return
        // 当前 entry 节点
        Node<K,V> current;     // current entry
        // fail-fast 的判断标识
        int expectedModCount;  // for fast-fail
        // 当前槽
        int index;             // current slot
        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }
        public final boolean hasNext() {
            return next != null;
        }
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

next 和 current 分别表示下一个 Node 节点和当前的 Node 节点，HashIterator 在初始化时会遍历所有的节点。下面我们用图来表示一下他们的遍历顺序

你会发现 nextNode() 方法的遍历方式和 HashIterator 的遍历方式一样，只不过判断条件不一样，构造 HashIterator 的时候判断条件是有没有链表，桶是否为 null，而遍历 nextNode 的判断条件变为下一个 node 节点是不是 null ，并且桶是不是为 null。

HashMap 中的移除方法

HashMap 中的移除方法也比较简单了

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

remove方法有很多，最终都会调用到removeNode方法，只不过传递的参数值不同，我们拿 remove(object) 来演示一下。
首先会通过hash来找到对应的bucket，然后通过遍历链表，找到键值相等的节点，然后把对应的节点进行删除。

总结

HashMap 的底层数据结构

JDK1.7中，HashMap采用位桶 + 链表的实现，即使用链表来处理冲突，同一 hash值的链表都存储在一个数组中。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
与 JDK 1.7相比，JDK 1.8在底层结构方面做了一些改变，由“数组+链表+红黑树”组成。当链表过长，则会严重影响HashMap的性能，红黑树搜索时间复杂度是O(logn)，而链表是O(n)。因此，JDK1.8对数据结构做了进一步的优化，引入了红黑树，当每个桶中元素大于8且总entry达到64的时候，会转变为红黑树，当entry总数没有达到64时，会进行数组的扩容操作，而不是转换为红黑树，目的就是优化查询效率。

HashMap的特点

· hashmap存储是无序的
· 键和值位置都可以为null，但是键位置只能存在一个null
· 键位置是唯一的，底层的数据结构是控制键的
· JDK1.8前数据结构是：数组+链表，JDK1.8之后是：数组+链表+红黑树
· 阈值(边界值)>8并且数组长度大于64，才将链表转换为红黑树，变成红黑树的目的是提高搜索速度，高效查询。

HashMap 的 put 过程

JDK1.8大致过程如下：
1.首先会使用hash方法计算对象(key)的哈希码，根据哈希码来确定在bucket中存放的位置(下标)
2.如果bucket是空的，则调用resize进行初始化
3.如果bucket中没有Node节点则直接进行put，放在对应的下标里
4.如果对应bucket已经有Node节点，且key值重复，就覆盖value
5.冲突后会对链表长度进行分析，判断长度是否大于8，如果链表长度小于8，在JDK1.7前会使用头插法。在JDK1.8之后更改为尾插法,，如果链表长度大于8并且数组容量小于64，对数组进行扩容，如果数组也大于64，会进行树化操作，把链表转换为红黑树，在红黑树上进行存储。

解决hash冲突的办法

解决hash冲突方法有：开放定址法、再哈希法、链地址法（HashMap中常见的拉链法）、建立公共溢出区。HashMap中采取的是链地址法。
· 开放定址法也称为再散列法，基本思想是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p)，如果p1再次出现冲突，则以p1位基础，以此类推，直到找到一个不冲突的哈希地址pi。因此开放定址法所需要的的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能直接删除节点。
· 再哈希法（双重散列，多重散列），提供多个不同的hash函数，R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。这样做虽然不容易产生堆集，但增加了计算的时间。
· 链地址法（拉链法），将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行，链表法使用于经常进行插入和删除的情况。
· 建立公共溢出区，将哈希表分为公共表和益出表，当溢出发生时，将所有溢出数据统一放到溢出区。
注意开放定址法和再哈希法的区别
· 开放定址发只能使用同一种hash函数进行再次hash，再哈希法可以调用多种不同的hash函数进行再次hash。

链表转红黑树的条件为数组大于64和单链大于8

在数组比较小时如果出现红黑树结构，反而会降低效率，而红黑树需要进行左旋右旋，变色，这些操作来保持平衡，同时数组长度小于64时，搜索时间相对要快些，总之是为了加快搜索速度，提高性能
JDK1.8以前HashMap的实现是数组+链表。即使哈希函数取得再好，也很难达到元素百分百均匀分布。当HashMap中有大量的元素都存放在同一个桶中时，这个桶下有一条长长的链表，此时HashMap就相当于单链表，假如单链表有n个元素，遍历的时间复杂度就从O(1)退化成O(n)，完全失去了它的优势，为了解决此种情况，JDK1.8中引入了红黑树(查找的时间复杂度为O(logn))来优化这种问题。

加载因子0.75，初始化临界值12

HashMap中的threshold是HashMap所能容纳Node的最大值。计算公式为
lengthLoadFactory。
也就是说，在数组定义好长度之后，负载因子越大，所能容纳的Node个数也越大
loadFactory越趋近于1，那么数组中存放的数据(entry也就越多)，数据也就越密集，更多的链表长度处于更长的值，查询的效率就会降低，添加数据产生哈希冲突的概率就越高
默认的loadFactory是0.75，loadFactory越小，越趋近于0，数组中存放的数据(entry)就越少，表现的越稀疏。

0.75是对空间和时间效率的一个平衡选择
如果负载因子小一些比如0.4，那么初始长度160.4=6，数组占满6个空间就进行扩容，很多空间可能元素很少甚至没有元素，会造成大量的空间被浪费
如果负载因子大一些比如0.9，这样会导致扩容之前查找元素的效率降低，添加时哈希碰撞会增加
loadFactory设置为0.75是经过多重计算检验得到的可靠值，可以最大程度的减少rehash的次数，避免过多的性能消耗

hash值的计算

hashCode方法是Object中的方法，所有的类都可以对其进行使用，首先底层通过调用hashCode方法生成初始hash值h1，然后将h1无符号右移16位得到h2，之后将h1与h2进行按位异或(^)运算得到最终hash值h3，之后将h3与(length-1)进行按位与(&)运算得到hash表索引
其他可以计算出hash值的算法有
· 平方取中法
· 取余法
· 伪随机数法

两个对象的hashCode相同

hashCode相同产生哈希碰撞，hashCode相等会调用equals方法比较内容是否相等，内容相等直接覆盖原值，不相等则会连接到链表后方，链表长度超过8数组长度超过64，会转为红黑树节点

线程不安全

HashMap 不是一个线程安全的容器，不安全性体现在多线程并发对 HashMap 进行 put 操作上。如果有两个线程A和B，首先A希望插入一个键值对到HashMap中，在决定好桶的位置进行put时，此时A的时间片正好用完了，轮到B运行，B运行后执行和A一样的操作，只不过B成功把键值对插入进去了。如果A和B插入的位置（桶）是一样的，那么线程A继续执行后就会覆盖B的记录，造成了数据不一致问题。
还有一点在于HashMap在扩容时，因resize方法会形成环，造成死循环，导致CPU飙高。

处理哈希碰撞

只要两个元素的key计算的hash码值相同就会发生hash碰撞。
· JDK1.8之前(链表解决哈希碰撞)，HashMap 底层是使用位桶 + 链表实现的，位桶决定元素的插入位置，位桶是由 hash 方法决定的，当多个元素的 hash 计算得到相同的哈希值后，HashMap会把多个 Node元素都放在对应的位桶中，形成链表，这种处理哈希碰撞的方式被称为链地址法。
· JDK1.8之后(链表+红黑树解决哈希碰撞)，HashMap底层是使用数组+链表+红黑树实现的，如果达到阈值且数组大于64，Node元素挂在树上。
其他处理hash碰撞的方式还有 「开放地址法、rehash 方法、建立公共溢出区」这几种方法。

HashMap get方法

首先会检查table中的元素是否为空，然后根据hash算出指定key的位置。然后检查链表的第一个元素是否为空，如果不为空，是否匹配，如果匹配，直接返回这条记录；如果匹配，再判断下一个元素的值是否为null，为空直接返回，如果不为空，再判断是否是TreeNode实例，如果是TreeNode实例，则直接使用TreeNode.getTreeNode取出元素，否则执行循环，直到下一个元素为null位置。

HashMap扩容

HashMap中有两个非常重要的变量，一个是了loadFactor ，一个是threshold ，loadFactor表示的就是负载因子，threshold表示的是下一次要扩容的阈值，当threshold=loadFactor*length时，数组长度扩大位原来的两倍，来重新调整map的大小，并将原来的对象放入新的bucket数组中。
扩容之后原位置的节点只有两种调整
· 保持原位置不动（新bit位为0时）
· 散列原索引+扩容大小的位置去（新bit位为1时）
扩容之后元素的散列设置的非常巧妙，节省了计算hash值的时间

当前数组长度从16到32，其实只是多了一个bit位的运算，我们只需要关注多出来的bit是0还是1，0索引不变，1索引变为当前索引值+扩容长度，5+16=21

这样的扩容方式不仅节省了重新计算hash的时间，而且保证了当前桶中的元素总数一定小于等于原来桶中的元素数量，避免了严重的hash冲突，均匀的把之前冲突的节点分散到新的通中去

HashMap中key值

一般用String、Integer这种不可变类当HashMap的key
· 因为String是不可变的，当创建字符串时，它的hashCode被缓存下来，不需要再次计算，相对于其他对象来说效率更快。
· 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象重写这两个方法是非常好重要的，这些类很规范的重写了equals()和hashCode()方法

HashMap的长度是2的幂次方

为什么length%hash==(n-1)&hash，相等的前提是length的长度2的幂次方，因为HashMap的长度是2的幂次方，所以使用余数来判断在桶中的下标。
如果length的长度不是2的幂次方，举个例子来试试。
例如长度为9时候，3&(9-1)=0，2&(9-1)=0 ，都在0上，碰撞了
这样会增大 HashMap 碰撞的几率。

链表大于8转红黑树

 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.  In
 * usages with well-distributed user hashCodes, tree bins are
 * rarely used.  Ideally, under random hashCodes, the frequency of
 * nodes in bins follows a Poisson distribution
 * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 * parameter of about 0.5 on average for the default resizing
 * threshold of 0.75, although with a large variance because of
 * resizing granularity. Ignoring variance, the expected
 * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 * factorial(k)).
 因为树节点的大小大约是普通节点的两倍，所以我们只在箱子包含足够的节点时才使用树节点（参见TREEIFY_THRESHOLD）。
当他们边的太小（由于删除或调整大小）时，就会被转换回普通的桶，在使用分布良好的hashcode时，很少使用树箱。
理想情况下，在随机哈希码下，箱子中节点的频率服从泊松分布
第一个值是：
 * 0:    0.60653066
 * 1:    0.30326533
 * 2:    0.07581633
 * 3:    0.01263606
 * 4:    0.00157952
 * 5:    0.00015795
 * 6:    0.00001316
 * 7:    0.00000094
 * 8:    0.00000006
 * more: less than 1 in ten million

树节点占用空间是普通节点的两倍，如果链表节点不够多却转为红黑树，会耗费大量的空间资源，并且在随机hash算法下的所有bin节点分布频率遵从泊松分布，链表长度达到8的概率只有0.00000006，几乎是不可能事件。
· 从平均查找长度来看，红黑树的平均查找长度是logn，如果长度为8，则logn=3，而链表的平均查找长度为n/4，长度为8时，n/2=4，所以阈值8能大大提高搜索速度
· 当长度为6时红黑树退化为链表是因为logn=log6约等于2.6，而n/2=6/2=3.两者相差不大，而红黑树节点占用空间更大。

HashMap 线程安全实现

· 多线程下扩容死循环。JDK1.7中的HashMap使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题
· 多线程的put可能导致元素的丢失。多线程同时执行put操作，如果计算出来的索引位置是相同的，那会造成前一个key被后一个key覆盖，从而导致元素的丢失。此问题在JDK1.7和JDK1.8中都存在
· put和get并发时，可能导致get为null。线程1执行put时，因为元素个数超出threshold而导致rehash，线程2此时执行get，有可能导致这个问题，此问题在JDK1.7和JDK1.8中都存在
· 因为HashMap不是一个线程安全的容器，所以并发场景下推荐使用ConcurrentHashMap，或者使用线程安全的HashMap，使用Collections包下的线程安全的容器，比如说
Collections.synchronizedMap(new HashMap());
还可以使用HashTable，它也是线程安全的容器，基于key-value存储，经常用HashMap和HashTable 做比较就是因为HashTable的数据结构和HashMap相同。
上面效率最高的就是ConcurrentHashMap。

计算hash低16bit和高16bit进行与或处理

计算索引需要将hashCode值与length-1进行按位与运算，如果数组长度很小，比如16，这样的值和hashCode做异或实际上只有hashCode值的后4位在进行运算，hash值是一个随机值，而如果产生的hashCode值高位变化很大，而低位变化很小，那么有很大概率造成哈希冲突，所以我们为了使元素更好的散列，将hash值的高位也利用起来。