1700445419
h^=（h＞＞＞20）^（h＞＞＞12）；
1700445420
1700445421
return h^（h＞＞＞7）^（h＞＞＞4）；
1700445422
1700445423
}
1700445424
1700445425
static int indexFor（int h, int length）{
1700445426
1700445427
return h＆（length-1）；
1700445428
1700445429
}
1700445430
1700445431
这两个方法相当有深度，读者有兴趣可以深入研究一下，这已经超出了本书范畴，不再赘述。顺便说明一下，null值也是可以作为key值的，它的位置永远是在Entry数组中的第一位。
1700445432
1700445433
现在有一个很重要的问题摆在面前了：哈希运算存在着哈希冲突问题，即对于一个固定的哈希算法f（k），允许出现f（k1）=f（k2），但k1≠k2的情况，也就是说两个不同的Entry，可能产生相同的哈希码，HashMap是如何处理这种冲突问题的呢？答案是通过链表，每个键值对都是一个Entry，其中每个Entry都有一个next变量，也就是说它会指向下一个键值对—很明显，这应该是一个单向链表，该链表是由addEntry方法完成的，其代码如下：
1700445434
1700445435
void addEntry（int hash, K key, V value, int bucketIndex）{
1700445436
1700445437
//取得当前位置元素
1700445438
1700445439
Entry＜K, V＞e=table[bucketIndex]；
1700445440
1700445441
//生成新的键值对，并进行替换，建立链表
1700445442
1700445443
table[bucketIndex]=new Entry＜K, V＞（hash, key, value, e）；
1700445444
1700445445
//判断是否需要扩容
1700445446
1700445447
if（size++＞=threshold）
1700445448
1700445449
resize（2*table.length）；
1700445450
1700445451
}
1700445452
1700445453
这段程序涵盖了两个业务逻辑：如果新加入的键值对的hashCode是唯一的，那直接插入的数组中，它Entry的next值则为null；如果新加入的键值对的hashCode与其他元素冲突，则替换掉数组中的当前值，并把新加入的Entry的next变量指向被替换掉的元素—于是，一个链表就生成了，可以用图5-1来表示。
1700445454
1700445455
1700445456
1700445457
1700445458
图5-1 HashMap存储结构图
1700445459
1700445460
HashMap的存储主线还是数组，遇到哈希冲突的时候则使用链表解决。了解了HashMap是如何存储的，查找也就一目了然了：使用hashCode定位元素，若有哈希冲突，则遍历对比，换句话说在没有哈希冲突的情况下，HashMap的查找则是依赖hashCode定位的，因为是直接定位，那效率当然就高了！
1700445461
1700445462
知道HashMap的查找原理，我们就应该很清楚：如果哈希码相同，它的查找效率就与ArrayList没什么两样了，遍历对比，性能会大打折扣。特别是在那些进度紧张的项目中，虽重写了hashCode方法但返回值却是固定的，此时如果把这些对象插入到HashMap中，查找就相当耗时了。
1700445463
1700445464
注意 HashMap中的hashCode应避免冲突。
1700445465
1700445466
1700445467
1700445468