黑马程序员技术交流社区
标题: 深入解析HashMap二 [打印本页]
作者: 小刀葛小伦 时间: 2019-8-1 17:55
标题: 深入解析HashMap二
2、put(Object key,Object value)操作
当调用put操作时，首先判断key是否为null，如下代码1处：
[Java] 纯文本查看 复制代码
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
如果key是null，则调用如下代码：
[Java] 纯文本查看 复制代码
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
就是说，获取Entry的第一个元素table[0]，并基于第一个元素的next属性开始遍历，直到找到key为null的Entry，将其value设置为新的value值。
如果没有找到key为null的元素，则调用如上述代码的addEntry(0, null, value, 0);增加一个新的entry，代码如下：
[Java] 纯文本查看 复制代码
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
先获取第一个元素table[bucketIndex],传给e对象，新建一个entry，key为null，value为传入的value值，next为获取的e对象。如果容量大于threshold，容量扩大2倍。
如果key不为null，这也是大多数的情况，重新看一下源码：
[Java] 纯文本查看 复制代码
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());//---------------2---------------
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table; e != null; e = e.next) {//--------------3-----------
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}//-------------------4------------------
modCount++;//----------------5----------
addEntry(hash, key, value, i);-------------6-----------
return null;
}
看源码中2处，首先会进行key.hashCode()操作，获取key的哈希值，hashCode()是Object类的一个方法，为本地方法，内部实现比较复杂，这里暂不介绍。hash()的源码如下：
[Java] 纯文本查看 复制代码
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
int i = indexFor(hash, table.length);的意思，相当于int i = hash % Entry[].length;得到i后，就是在Entry数组中的位置，其实不管Entry数组中i位置有无元素，都会去执行5-6处的代码，如果没有，则直接新增，如果有，则将新元素设置为Entry[0]，其next指针指向原有对象，即原有对象为Entry[1]。具体方法可以解释为下面的这段文字：（3-4处的代码只是检查在索引为i的这条链上有没有key重复的，有则替换且返回原值，程序不再去执行5-6处的代码，无则无处理）
上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。如， 第一个键值对A进来，通过计算其key的hash得到的i=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其i也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,i也等于0,那么C.next = B,Entry[0] = C；这样我们发现i=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。
到这里为止，HashMap的大致实现，我们应该已经清楚了。当然HashMap里面也包含一些优化方面的实现，这里也说一下。比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个i的链就会很长，会不会影响性能？HashMap里面设置一个因素（也称为因子），随着map的size越来越大，Entry[]会以一定的规则加长长度。
作者: hmhm123 时间: 2019-8-1 23:58
沙发
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |