原理底层计划--HashMap

HashMap

之前写了“Java集合TreeMap红黑树一生只爱一次”，说到底还是太年轻了，Map其实在排序中应用比较少，一般追求的是速度，通过HashMap来获取速度。hashmap 调用object hashcode方法用于返回对象的哈希码，主要使用在哈希表中。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap继承AbstractMap 本质是key-value键值对，具有Map素有常用的方法put() get() remove()。
Cloneable意味着可以被克隆。
实现serializable接口的作用是就是可以把对象存到字节流,然后可以恢复。
当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。

get

hashmap常用的get方法，可以看到先hash话，然后获取

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

put

在Java 8中put这个方法的思路分为以下几步：

1. 调用key的hashCode方法计算哈希值，并据此计算出数组下标index
2. 如果发现当前的桶数组为null，则调用resize()方法进行初始化
3. 如果没有发生哈希碰撞，则直接放到对应的桶中
4. 如果发生哈希碰撞，且节点已经存在，就替换掉相应的value
5. 如果发生哈希碰撞，且桶中存放的是树状结构，则挂载到树上
6. 如果碰撞后为链表，添加到链表尾，如果链表长度超过TREEIFY_THRESHOLD默认是8，则将链表转换为树结构
7. 数据put完成后，如果HashMap的总数超过threshold就要resize

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) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ;   binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
      modCount;
    if (  size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

为什么非要使用红黑树呢？

这个选择是综合考虑的，既要put效率很高，同时也要get效率很高，红黑树就是其中一种。
二叉树也ok，红黑树是一种自平衡的二叉查找树
平衡二叉树可以有效的减少二叉树的深度，从而提高了查询的效率
除了之外，红黑树还具备
节点是红色或黑色；
根节点是黑色；
所有叶子都是黑色的空节点；
每个红色节点必须有两个黑色的子节点，也就是说从每个叶子到根的所有路径上，不能有两个连续的红色节点；
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点
红黑树的优势在于它是一个平衡二叉查找树，对于普通的二叉查找树（非平衡二叉查找树）在极端情况下可能会退化为链表的结构，再进行元素的添加、删除以及查询时，它的时间复杂度就会退化为 O(n)
红黑树的高度近似 log2n，它的添加、删除以及查询数据的时间复杂度为 O(logn)
红黑树时间复杂度比链表、二叉树小，这就是采用红黑树做hashMap底层原理，然后在treeMap里面就更经典了。

jdk1.7之前底层数据结构采用哈希 链表。但后来业务越来越追求速度，hash的目的是为了得到进行索引，有些hash冲突可能造成死循环，所以jdk1.8加上红黑树来解决明显可以提高效率。
但是要分情况在数组长度大于64，同时链表长度大于8的情况下，链表将转化为红黑树。当数据的长度退化成6时，红黑树转化为链表。数据长度没有那么长，就没必要采用红黑树，红黑树虽然提高了速度，但也提交了空间复杂度。数据长度大于8和数组长度大于64，采用红黑树。那为什么是6和8作为临近值呢，其实这个值不要死记，是官网进行压力测试的出来的结论。

为什么HashMap要扩容呢？

数组是固定的，但集合是动态的，可以扩容。
当hashmap越来越来多的元素塞进来之后，hashmap不得不扩容了，hashmap中元素个数超过160.75=12的时候，就把数组的大小扩展为216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作。
所以我们提前预测知道hashmap容量，再稍微设置大些，这样可以减少性能的消耗的。
但是initialCapacity初始容量设置小了，会不会报错呢？
不会的，但是hashmap会自动扩容，同样也会走到上面过程，重新计算，消耗性能的操作。
提前预判，但是后来业务改变，需要那么大的容量，程序员应该即使更改，要不然就和不设置没有区别啦。

哈希 链表、红黑树 （来处理极端情况下的哈希碰撞）

数组 （链表或红黑树）Node类来存储Key、Value

hashMap什么时候扩容？

注意，是在put的时候才会扩容，在容量超过四分之三的时候就会扩容

hashMap的key可以为空吗

可以，Null值会作为key来存储

key重复了，会被覆盖吗？

会的

HashMap扩容为什么总是2的次幂？

HashMap扩容主要是给数组扩容的，因为数组长度不可变，而链表是可变长度的。从HashMap的源码中可以看到HashMap在扩容时选择了位运算，向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置。只有当对应位置的数据都为1时，运算结果也为1，当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞

当HashMap的容量是16时，它的二进制是10000，(n-1)的二进制是01111

JDk1.7HashMap扩容死循环问题

HashMap是一个线程不安全的容器，在最坏的情况下，所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)。
JDK1.7中HashMap采用头插法拉链表，所谓头插法，即在每次都在链表头部（即桶中）插入最后添加的数据。
死循环问题只会出现在多线程的情况下。

假设在原来的链表中，A节点指向了B节点。
在线程1进行扩容时，由于使用了头插法，链表中B节点指向了A节点。
在线程2进行扩容时，由于使用了头插法，链表中A节点又指向了B节点。
在线程n进行扩容时，
这就容易出现问题了。在并发扩容结束后，可能导致A节点指向了B节点，B节点指向了A节点，链表中便有了环

死循环解决方案：

1)、使用线程安全的ConcurrentHashMap替代HashMap，个人推荐使用此方案。

2)、使用线程安全的容器Hashtable替代，但它性能较低，不建议使用。

3)、使用synchronized或Lock加锁之后，再进行操作，相当于多线程排队执行，也会影响性能，不建议使用。

为了解决JDK1.7死循环问题，JDK1.8引入了红黑树
即在数组长度大于64，同时链表长度大于8的情况下，链表将转化为红黑树。同时使用尾插法。当数据的长度退化成6时，红黑树转化为链表。

从JDK1.8开始，在HashMap里面定义了一个常量TREEIFY_THRESHOLD，默认为8。当链表中的节点数量大于TREEIFY_THRESHOLD时，链表将会考虑改为红黑树
使用线程安全如Concurrenthashmap、HashTable

为什么线程不安全？

1、put的时候导致的多线程数据不一致。
这个问题比较好想象，比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它对此一无所知，以至于它认为它应该这样做，如此一来就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致的行为。

2、另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环（cpu100%）
HashMap的扩容机制就是重新申请一个容量是当前的2倍的桶数组，然后将原先的记录逐个重新映射到新的桶里面，然后将原先的桶逐个置为null使得引用失效。HashMap之所以线程不安全，就是resize这里出的问题。

这篇好文章是转载于：学新通技术网