[数据结构与算法]HashMap的理解

底层数据结构

HashMap底层是哈希表（hash table，也叫作散列表），为了解决哈希碰撞，又在原来的基础上把每个数组的元素扩展成一个个链表。简单理解的话，结构=数组（也叫作哈希桶）+链表，注意的是在jdk8以后，为了更高效的查询，在满足一定条件下，将链表转化成红黑树。

hash（）方法

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

key.hashCode()是底层的一个函数，说实话我也不了解其实现原理。我只知道他会返回一个32位的2进制数。当得到32位的数据后，下一步的操作是把此数据和自身的高16位进行异或操作。

为什么要和自身的高16位异或？

我们再得到key之后，是想把这个key的值转成数组中的下标，以驻足长度为16进行距离。如果我们得到一个hashcode的返回值1111 0000 1111 0000 1111 0000 1111 0000，直接人为他是hash值，接下来他会和（n-1）15（1111）进行&操作，得到低四位0000。如果另一个数据是1111 1100 1111 0110 1111 0110 1111 0000，经过上述的操作，低四位也是0000。意味着这两个数据会放在同一个下标处。没有达到我们的预期：让数据分散开。

而与高16位异或的步骤如下：

接下来第一个hash值和1111相与，得到0000（下标0）。第二个hash值和1111与操作，得到0110（下标6）。所以此时两个数据分离开了。

和高16位异或可以数据分布不均匀，这样可以保证高位的数据也参与到与运算中来，以增大索引的散列程度[1]。

&操作是二者都为1时，结果等于1，所有大多数情况下结果为0，即此操作会让结果更趋近于0。|操作是二者有一个1时，结果就为1，所以结果会更趋近1。异或可以保证两个数值的特性，不至于趋近0或1。

putVal（）方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //第一次使用put时，此时table为空，所以tab中也没有数据。第一步就是进行扩容，后续不会再                                                            
        //执行此处, 最初的扩容，也是初始化，会把数组长度确定为16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        //用（n-1）&hash得到下标，此过程详细步骤在上一小节讲过
        //得到小标后，得到数组在此下标的数据，如果此处没有数据就直接添加
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            //执行到此，代表着下标处有数据，所以会进行接下来的操作，注意p现在代表着数组中的元 
            //素,e则是一个备份，k也是对key的备份，具体的后面会讲
            Node<K,V> e; K k;


            //如果下标数据和我们要添加的数据的key相同，则让e指向p，注意此时k一定有值。接下来会 
            //直接执行if (e != null) { }，把数据更新
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

            //如果上面不成立，到这，注意k=p.key，e = null
            else if (p instanceof TreeNode)
                   //如果p下面是红黑树，则进行此操作（我不是很懂，后续再学习）
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {
                //如果上面不成立，到这，链表的第一个元素不是我们想找的，注意k=p.key，e =                 
                //null，且数组下面是链表

                //从链表的头部开始，依次遍历
                for (int binCount = 0; ; ++binCount) {

                    //注意此时e被赋值为p指向的下一个节点，如果下一个节点为null，则把put的数据 
                    //放在链表最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //如果遍历的数据长度大于等于8，则直接转成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    //到这，此时k=p.key，e指向p的下一个（举例p指向链表第一个元素，e指向链表第        
                    //二个元素），如果e的key和要添加的key相同，则退出更新。
                    //如果不相同，p = e，此时p是链表第二个元素。后续e再到这，就会指向第三个元    
                    //素。这样不断的迭代，最后把数据添加。
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

            //这个地方就是处理key值相同时，更新value值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//记录修改次数
        //数据长度+1，然后判断数据是够需要扩容，大于0.75的容量，需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

以上在参考相关博客后，我写出来自己的理解[2,3]。对于红黑树，可能需要在学习。

总结：先调用hashcode（）方法得到hash值，然后通过哈希算法得到数组的下标值。如果这个位置上什么都没有，返回null。如果这个位置上有链表，拿着k与链表上Node的k进行equals比较，如果返回true，则这个节点就是我们要得到的，更新数据，如果结果全是false，把数据添加到链表最后。

为什么每次扩容2倍？

我们在得到下标时，是进行（n-1）&hash的操作。最开始是1111和hash值进行&操作。首先这个结果必然在0-15，不会超过数组下标。扩容后，我们是不是想让5个1和hash&操作，此时11111-->31，所以n=32，再次扩容后6个1和hash&操作，此时111111->63，所以n=64。其实每加一个1，数据就扩大2倍。所以扩容2倍。

为什么数组长度最大值是2^30?

所以当1不断左移时，数组长度不断变大，对应的n-1中的全1位也在变多。由上面的规律可知，1最多到第32位，所以此时是2^31。但是int数据类型的最高位是符号位，所以1不能左移过去，所以最终长度为2^30.

键值对都可以为null

key为null时，hash = 0。

if ((p = tab[i = (n - 1) & hash]) == null)? tab[i] = newNode(hash, key, value, null);

此时tab[0] == null,所以可以插入值。

理解为什么map中的k是无序且不可重复？
?? ?无序：有些数据是直接存储在某个下标对应的链表里面，有的是存储在别的下标对应的地方。
?? ?输出数据时，可能是先按照下标，一次将下标上的链表进行输出，所以是无序的。
?? ?不可重复：因为k重复后，先调用hashcode（）得到hash值，然后得到数组下标。但是要对
?? ?k进行equals判断，重复时指挥覆盖value，所以不能存储k相同的数据。

参考：

[1]:为什么HashMap使用高16位异或低16位计算Hash值？ - 知乎 (zhihu.com)

[2]:HashMap(一)——HashMap put方法原理_自恃无情的博客-CSDN博客_hashmap的put方法实现原理

[3]:HashMap原理详解，看不懂算我输（附面试题） - 知乎 (zhihu.com)