内部接口Entry中存放键/值对(key value pair)

1
2
3
4
5
6
7
8
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
//剩余代码未列出
}

put()方法的内部实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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[i]; 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;
}
put()方法的解释:
  • 检查key是否为null,如果key为null,value被存放在table[0],因为null的散列值始终为0。
  • 以key的散列值作为参数,调用hashCode()方法,计算得到一个散列值。这个散列值将被用来计算Entry对象在数组中的下标。JDK的设计者假定这里可能会有糟糕的hashCode()方法,为了解决这个问题,他们介绍了另外一个hash()方法,将对象的散列值传递给这个方法,得到更加合适的散列值。
  • 调用indexFor(hash, table.length)方法,计算Entry对象在数组中的确切下标。
  • 两个不相等的对象可以有相同的散列值,两个不相等的对象是怎样被存放在数组的相同位置(该位置称为bucket)?答案是链表。Entry类有一个“next”属性,用来指向链中的下一个对象。所以,如果对象发生冲突,Entry对象就被存放在链表中。
  • 当Entry对象需要被存入一个特定的下标时,HashMap会检查该下标处是否已经有一个Entry对象:
    • 如果还没有,Entry对象会被存入这个位置;
    • 如果已经有,则检查它的“next”属性:
      • 如果为null,当前Entry对象将作为其下一节点;
      • 如果不为null,程序会保持跟随,直到其为null。
  • 如果已经添加了另一个具有相同key的value作为Entry对象,逻辑上,它应该替换旧的value。是怎样做的?在决定Entry对象在数组中的下标后,HashMap会调用每个Entry对象的equals()方法。在链表中的所有Entry对象会具有相似的散列值,但equals()方法会做出判断。如果equals(k)的结果为true,两个key将会被看做相等的key对象。这将导致仅Entry中的value对象被替换。这样,HashMap就确保了key的唯一性。

get()方法的内部实现代码:

1
2
3
4
5
6
7
8
9
10
11
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

注意条件:e.hash == hash && ((k = e.key) == key || key.equals(k))

参考资料:

How HashMap works in Java