Java之HashMap

HashMap 构造函数允许用户传入的容量可以不是 2 的 n 次方吗?

可以。因为它可以自动地将传入的容量转换为 2 的 n 次方。

static final int tableSizeFor(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;
}

哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

hash算法

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {
//jdk1.7的源码，jdk1.8没有这个方法，原理是一样的只不过放到其他方法中去，例如put()
     return h & (length-1);  //第三步 取模运算
}

这里的Hash算法分为三步：取key的hashCode值、高位运算、取模运算。对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

为什么计算 key 的 hash 值，要把 key 的 hashcode 右移 16 位，然后与它的 hashcode 相或呀？

首先，假设有一种情况，对象 A 的 hashCode 为 1000010001110001000001111000000，对象 B 的 hashCode 为 0111011100111000101000010100000。如果数组长度是 16，也就是 15 与运算这两个数， 你会发现结果都是 0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。但是如果我们将 hashCode 值右移 16 位，也就是取 int 类型的一半，刚好将该二进制数对半切开。并且使用位异或运算（如果两个数对应的位置相反，则结果为 1，反之为 0），这样的话，就能避免我们上面的情况的发生。总的来说，使用位移 16 位和 异或 就是防止这种极端情况。但是，该方法在一些极端情况下还是有问题，比如：10000000000000000000000000 和 1000000000100000000000000 这两个数，如果数组长度是 16，那么即使右移 16 位，在异或，hash 值还是会重复。但是为了性能，对这种极端情况，JDK 的作者选择了性能。毕竟这是少数情况，为了这种情况去增加 hash 时间，性价比不高。

HashMap为什么用头插法？

在jdk1.8之前是插入头部的，在jdk1.8中是插入尾部的。

modCount字段

modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

HashMap可以有key为null的情况，为什么最多只能有一个？

HashMap 允许插入key为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。

put过程

get过程

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

java1.7 resize过程

void resize(int newCapacity) {   //传入新的容量
     Entry[] oldTable = table;    //引用扩容前的Entry数组
     int oldCapacity = oldTable.length;         
     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
         return;
     }
  
     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
    transfer(newTable);                         //将数据转移到新的Entry数组里
    table = newTable;                           //HashMap的table属性引用新的Entry数组
    threshold = (int)(newCapacity * loadFactor);//修改阈值
}

void transfer(Entry[] newTable) {
    Entry[] src = table;                   //src引用了旧的Entry数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
        Entry e = src[j];       //取得旧Entry数组的每个元素
        if (e != null) {
//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
            src[j] = null;
            do {
                Entry next = e.next;
                //！！重新计算每个元素在数组中的位置
               int i = indexFor(e.hash, newCapacity);
               e.next = newTable[i]; //标记[1]
               newTable[i] = e;      //将元素放在数组上
               e = next;             //访问下一个Entry链上的元素
           } while (e != null);
       }
   }
}

java1.8resize过程

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //table已经完成初始化
    if (oldCap > 0) {
        //达到最大，不能继续扩容
        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
    }
    //table未完成初始化但阈值已经设置完成，即使用HashMap(int)或HashMap(int,float)构造时会发生这种情况
    else if (oldThr > 0) // initial capacity was placed in threshold
        //设置阈值为新容量
        newCap = oldThr;
    //table未初始化，阈值未初始化，即使用HashMap()构造时发生这种情况
    else {
        //设置初始值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //计算出新阈值
    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;
    //如果原来的哈希表有元素，要把原来的元素放到新哈希表中
    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;
                        //(e.hash & oldCap) == 0为true判断的是扩容后在原下标，false为要放进新的下标。
                        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);
                    //将链表放进新table中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

为什么链化为6，树化为8？

• 首先，红黑树的查询O(logn)比链表O(n)快；但红黑树添加删除节点时会维持红黑树的特性而进行相应旋转，变色操作，链表在添加删除时只需要改变当前节点的next指针即可。
• 当链表和红黑树的节点个数小于等于6时，查询速度的差异小于删除添加的差异，所以选择添加删除更方便的链表
• 当链表和红黑树的节点个数大于8时，删除添加的速度差异小于查询速度的差异，所以选择查询更快的红黑树

为什么table不能被序列化？

我们知道确定hashmap使用的哈希函数会用到key的hashCode，而key的哈希code方法可能没有被重写，这样这个方法就会调用Object的hashCode方法，而Object的hashCode方法是本地native方法，那么会造成的问题就是同一个hashmap可能在不同虚拟机下反序列话时造成每个键的hash值不一样，就会造成键值对对应的位置出错。

table可以换成LinkedList吗？那ArrayList呢？

答案很明显，必须是可以的。既然是可以的,为什么HashMap不用LinkedList,而选用数组? 因为用数组效率最高！

在HashMap中，定位桶的位置是利用元素的key的哈希值对数组长度取模得到。此时，我们已得到桶的位置。显然数组的查找效率比LinkedList大。

那ArrayList，底层也是数组，查找也快啊，为啥不用ArrayList?

因为采用基本数组结构，扩容机制可以自己定义，HashMap中数组扩容刚好是2的次幂，在做取模运算的效率高。而ArrayList的扩容机制是1.5倍扩容

如何解决hashmap序列化问题？

可能我需要将hashmap传送到其他计算机上，那么hashmap自己实现了writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectInputStream s)方法。他们作用是该类在序列化时会自动调用这两个方法，没有这两个方法就调用defaultWriteObject()和defaultReadObject()。而hashmap实现了，所以看一下他们是如何进行序列化的，下面只分析写，读就对是相应数据的读就行了。

private void writeObject(java.io.ObjectOutputStream s)
    throws IOException {
    int buckets = capacity();
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    s.writeInt(buckets);
    s.writeInt(size);
    internalWriteEntries(s);
}

void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
    Node<K,V>[] tab;
    if (size > 0 && (tab = table) != null) {
        for (Node<K, V> e : tab) {
            for (; e != null; e = e.next) {
                s.writeObject(e.key);
                s.writeObject(e.value);
            }
        }
    }
}

可以看到，hashmap实现序列化的方式就是将hashmap拆解为属性和节点，直接把属性和节点序列化即可

HashMap中的key为什么不能为可变对象？

如果我们的key是一个可变对象，那我们改变它的元素就注定会改变它的hashcode值。如果一定要使用可变对象作为key，就需要保证该对象的属性发生改变时，不会改变对象的hashcode值。
所以要重写它的hashcode方法和equals方法

请说明一下HashMap扩容的过程

扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。这个rehash的过程是很耗时的，特别是HashMap很大的时候，会导致程序卡顿，而2倍内存的关系还会导致内存瞬间溢出，实际上是3倍内存，因为老结构的内存在rehash结束之前还不能立即回收。那为什么不能在HashMap比较大的时候扩容扩少一点呢，关于这个问题我也没有非常满意的答案，我只知道hash的取模操作使用的是按位操作，按位操作需要限制数组的长度必须是2的指数。另外就是Java堆内存底层用的是tcmalloc这类library，它们在内存管理的分配单位就是以2的指数的单位，2倍内存的递增有助于减少内存碎片，减少内存管理的负担。

说说String中hashcode的实现?

public int hashCode() {
 int h = hash;
 if (h == 0 && value.length > 0) {
 char val[] = value;
 for (int i = 0; i < value.length; i++) {
 h = 31 * h + val[i];
 }
 hash = h;
 }
 return h;
}

String类中的hashCode计算方法还是比较简单的，就是以31为权，每一位为字符的ASCII值进行运算，用自然溢出来等效取模。

哈希计算公式可以计为s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

那为什么以31为质数呢?

主要是因为31是一个奇质数，所以31i=32i-i=(i<<5)-i，这种位移与减法结合的计算相比一般的运算快很多。

HashMap在并发编程环境下有什么问题啊?

(1)多线程扩容，引起的死循环问题
(2)多线程put的时候可能导致元素丢失
(3)put非null元素后get出来的却是null

扩容死循环问题(1.8解决)

https://coolshell.cn/articles/9606.html

既然链表如此短，为啥Java8要对HashMap的链表进行改造，使用红黑树来代替链表呢？

这道题的关键在于如果Key的hashcode不是随机的，而是人为特殊构造的话，那么第二维链表可能会无比的长，而且分布极为不均匀，这个时候就会出现性能问题。比如我们把对象的hashcode都统一返回一个常量，最终的结果就是hashmap会退化为一维链表，Get方法的性能巨降为O(n)，使用红黑树可以将性能提升到O(log(n))。

Redis里面的字典是如何扩容？(单线程渐进式Rehash)

https://luoming1224.github.io/2018/11/12/[redis%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0]redis%E6%B8%90%E8%BF%9B%E5%BC%8Frehash%E6%9C%BA%E5%88%B6/
当hash内部的元素比较拥挤时(hash碰撞比较频繁)，就需要进行扩容。扩容需要申请新的两倍大小的数组，然后将所有的键值对重新分配到新的数组下标对应的链表中(rehash)。如果hash结构很大，比如有上百万个键值对，那么一次完整rehash的过程就会耗时很长。这对于单线程的Redis里来说有点压力山大。所以Redis采用了渐进式rehash的方案。它会同时保留两个新旧hash结构，在后续的定时任务以及hash结构的读写指令中将旧结构的元素逐渐迁移到新的结构中。这样就可以避免因扩容导致的线程卡顿现象。
它的好处：采用分而治之的思想，将庞大的迁移工作划分到每一次CURD中，避免了服务繁忙。

参考

https://juejin.im/post/5d0058fce51d45773e418a5d
https://tech.meituan.com/2016/06/24/java-hashmap.html
https://juejin.im/post/5d0258f4e51d4550723b13e3