1700445405
modCount++；
1700445406
1700445407
//插入新元素，或者替换同哈希的旧元素并建立链表
1700445408
1700445409
addEntry（hash, key, value, i）；
1700445410
1700445411
return null；
1700445412
1700445413
}
1700445414
1700445415
注意看，HashMap每次增加元素时都会先计算其哈希码，然后使用hash方法再次对hashCode进行抽取和统计，同时兼顾哈希码的高位和低位信息产生一个唯一值，也就是说hashCode不同，hash方法返回的值也不同。之后再通过indexFor方法与数组长度做一次与运算，即可计算出其在数组中的位置，简单地说，hash方法和indexFor方法就是把哈希码转变成数组的下标，源代码如下：
1700445416
1700445417
static int hash（int h）{
1700445418
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
[
上一页 ]
[ :1.700445405e+09 ]
[
下一页 ]