HashMap

JDK1.8 hashmap底层是散列表+红黑树。java表现为数组+链表+红黑树。
JDK1.8的优化是对扩容变为2的幂次方（那么用于数组索引的hashCode也会左移），来加快散列表落槽时候数组的索引(看hashCode增加的bit是0还是1)。还有就是红黑树的引入。

IMG20190216230052.jpg

Hashmap初始化与扩容

是在第一次put的时候初始化，初始化的值按位用算符1<<4，为16，当达到阈值threshold的时候就扩容，threshold等于Capacity默认存储容量*填充因子(0.75)，为了提高散列表性能，扩容的时候，每次2倍。1<<5,1<<6

   newThr = oldThr << 1; // double threshold

总是2的n次方，这样我们就不需要重新按位与重新计算哈希来算出数组下标，只需要看新的hashCode新增的bit是0还是1，如果是0，索引不变，如果是1，变为原索引+oldCap

put

put原理:数组table每个元素存的是链表的头节点，往hashmap里面放键值对的时候先得到key的hashcode，然后重新计算hashcode(使用位哈希算法，高或低16位，使得32位哈希值中的1均匀分布，降低哈希碰撞，提高散列表性能)，然后与length-1按位与，计算出数组下标(即哈希槽的位置)。如果该下标的哈希桶为空，头插法直接将键值对作为头节点(Node,继承了Map.Entry)，如果不为空，遍历哈希桶看是否有key值相同的，如果有则覆盖value值，如果没有，则头插法。

JDK1.8的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;
        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))))//哈希桶不为空，记录下当前桶key和hashcode
                e = p;
            else if (p instanceof TreeNode)//如果是树结构，转为红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//链表结构，如果哈希桶长度大于8并且容量大于64时，转化为红黑树
                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//e不为空，新值覆盖旧值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

和我们一开始说的一样，看注释，如果散列表为空，初始化散列表，如果没有哈希碰撞，直接落槽，如果有哈希碰撞，并且哈希桶为空，头插法，如果有哈希碰撞，并且哈希桶不为空，则记录下当前哈希桶的key和hashcode，对是否是树结构进行判断，如果是树，转用红黑树的插入，如果不是，使用链表头插。

面试问题:

HashMap为什么允许为null?
首先put的时候，就会对key==null做一个判断，对于key==null的Entry，会调用putForNullKey直接去遍历table[0]上的哈希桶，寻找e.key=null的Entry或者没有找到遍历结束。找到则覆盖原值，没找到就调用addEntry方法添加一个key为null的Entry。

为什么说HashMap是无序的?（因为其初始化的时候采用的是位哈希算法）
HashMap在第一次put的时候完成初始化，通过模运算(其实是高或低16位的按位与运算的位哈希算法 使1均匀分布，有利于泊松分布，降低哈希碰撞的概率)来计算哈希槽中的落槽位置即数组下标的(这里是无序的)。

HashMap高并发情况下的问题?改善?
HashMap高并发情况下的扩容数据丢失以及死链问题。因为hashmap线程不安全，所以如果两个线程同时对同一Entry进行操作，会丢失数据。死链问题:Entry的next被并发修改导致的对象丢失，两个对象互链，对象自己互链的中两个对象互链产生的死锁。改善，1.8Hashmap采用对原先链表的引用，保证有序性，除此之外，可以使用ConcurrentHashmap。1.7使用segement分段锁，1.8使用CAS保证有序，voliate关键字保证可见。

HashMap存放自定义类的时候，为什么要重写hashCode和equals。
因为我们要通过hashCode然后模运算(现在是按位与的哈希算法)来计算table中的下标，然后遍历这之后的链表，通过equals比较有没有相同的key，如果有直接覆盖value，因为要通过equals比较有没有相同的key，所以要重写equals，而由于约定并且提高散列表性能，重写equals必须重写hashCode。

HashMap与Hashtable比较。

image.png