HashMap相关

---

HashMap容量为2次幂的原因

---

hash方法可以计算一个对象的hashcode，我们不用过于关注

但是他计算hashcode在bucket数组中的位置是怎么计算的呢？

i = (n - 1) & hash

后面就是大家熟悉的碰撞冲突拉链法解决

这里i = (n - 1) & hash就可以实现一个均匀分布

我们比如容量是n=32，那么32-1=31,31的二进制是11111

用我们取得的对象的hashcode和31去进行与操作

我们假设hashcode从1,2,3开始，分别得出的结果是

00001 1

00010 2

....

11111 31

发现是呈一个均匀分布的

如果n=50呢，49的二进制是110001，再作同等假设，得出的值是

000000 ： 0
000001 ： 1
010000 ： 16
010001 ： 17
100000 ： 32
100001 ： 33
110000 ： 48

110001 ： 49

这就是本质原因，你不用2的幂，保证不了均匀的分布

我们正常的思维是进行一个%运算，但是%运算效率太过低下，所以采用2进制运算，同时为了保证2进制的情况下进行一个均匀分布，所以把容量设置成2的幂，这就是最正确的回答
计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
有人怀疑两种运算效率差别到底有多少，我做个测试：

public static void main(String[] args) {
    
    long currentTimeMillis = System.currentTimeMillis();
    int a=0;
    int times = 10000*10000;
    for (long i = 0; i < times; i++) {
         a=9999%1024;
    }
    long currentTimeMillis2 = System.currentTimeMillis();
    
    int b=0;
    for (long i = 0; i < times; i++) {
         b=9999&(1024-1);
    }
    
    long currentTimeMillis3 = System.currentTimeMillis();
    System.out.println(a+","+b);
    System.out.println("%: "+(currentTimeMillis2-currentTimeMillis));
    System.out.println("&: "+(currentTimeMillis3-currentTimeMillis2));
}

结果：
783,783
%: 359
&: 93

---

如何解决hash冲突

---

• [开放定址法]
  1. [线性探测再散列]
  2. [二次探测再散列]
  3. [伪随机探测再散列]
• [再哈希法]
• [链地址法]
• [建立公共溢出区]

HashMap采用链地址法，即拉链法
链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

---

resize死循环

---

我们都知道HashMap初始容量大小为16,一般来说，当有数据要插入时，都会检查容量有没有超过设定的thredhold，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。因为rehash，所以之前在一个位置的值，可能出现在不同的位置。

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
}

大概看下transfer：

对索引数组中的元素遍历
对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。
循环2，直到链表节点全部转移
循环1，直到所有索引数组全部转移

经过这几步，我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。这时候就有点头绪了，死锁问题不就是因为1->2的同时2->1造成的吗？所以，HashMap 的死锁问题就出在这个transfer()函数上。

假如有两个线程P1、P2，以及链表 a=》b=》null

1、P1先运行，运行完"Entry<K,V> next = e.next;"代码后发生堵塞，或者其它情况不再运行下去，此时e=a。next=b

2、而P2已经运行完整段代码，于是当前的新链表newTable[i]为b=》a=》null

3、P1又继续运行"Entry<K,V> next = e.next;"之后的代码，则运行完"e=next;"后，newTable[i]为a《=》b。则造成回路，while(e!=null)一直死循环

---

为什么长度为8的时候转换为红黑树

---

因为红黑树的平均查找长度是log（n），长度为8的时候，平均查找长度为3。。如果继续使用链表，平均查找长度为8/2=4。这才有转换为树的必要。。链表长度如果是6以内，6/2=3，速度也很快的。转化为树还有生成树的时间，并不明智。