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冲突
- [开放定址法]
- [线性探测再散列]
- [二次探测再散列]
- [伪随机探测再散列]
- [再哈希法]
- [链地址法]
- [建立公共溢出区]
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，速度也很快的。转化为树还有生成树的时间，并不明智。
