- hash算法必须是高效的
- hash值到内存地址（数组索引）的算法是快速的
- 根据内存地址（数组索引）可以直接取得对应的值
图3.11 Hash冲突示意图
要处理好这个问题，需要进一步深入HashMap，虽然HashMap的底层实现使用的是数组，但是数组内的元素并不是简单的值，而是一个Entry类的对象。因此，对HashMap结构的贴切描述如图3.12所示。
图3.12 HashMap表项结构
可以看到，HashMap的内部维护着一个Entry数组，每一个Entry表项包括key、value、next和hash几项。这里特别注意其中的next部分，他指向了另外一个Entry(所以实际上HashMap的数据结构是一个列表数组，数组中每个元素是一个Entry列表，Entry列表中每个元素是一个Entry对象)。进一步阅读HashMap的put()方法源码，可以看到当put()操作有冲突时，新的Entry依然会被安放在对应的索引下标内，并替换原有的值。同时，为了保证旧值不丢失，会将新的Entry的next指向旧值。这便实现了在一个数组索引空间内，存放多个值项。因此，如图3.12所示，HashMap实际上是一个链表为元素的数组。
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;
//如果当前的key已经存在于HashMap中
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); //添加当前的表项到i位置
return null;
}
addEntry()方法的实现如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//将新增元素放到i的位置，并让它的next指向旧的元素
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
基于HashMap的这种实现机制，只要hashCode()和hash()方法实现的足够好，能够尽可能的减少冲突的产生，那么对HashMap的操作几乎等价于对数组的随机访问操作，具有很好的性能。但是，如果hashCode()或者hash()方法实现较差，在大量冲突产生的情况下，HashMap事实上就退化为几个链表，对HashMap的操作等价于遍历链表，此时性能很差。
考虑一个在极端情况下的例子，假设类BadHash有着一个很槽糕的hashCode()实现：
public class BadHash{
double d;
public BadHash(double d){
this.d=d;
}
@Override
public int hashCode(){
return 1; //一个槽糕的hashCode()实现
}
}
类GoodHash拥有默认hashCode()方法：
public class GoodHash{
double d;
public GoodHash(double d){
this.d=d;
}
}
分别使用BadHash类和GoodHash类作为HashMap的key，产生1万一个对象并将其存入HashMap中，执行get()方法1万次。结果BadHash类相对耗时1297ms，而GoodHash类仅耗时15ms。这正是随机数据访问和链表遍历的性能差距。
再补充一下HashMap的get(key)方法的实现原理解析：
public V get(Object key) { if (key == null) // 键为null的Entry是tables[0] return getForNullKey(); // 首先根据key获取hash值，跟put方法一致 int hash = hash(key.hashCode()); // 同样通过位与运算获取Entry[] tables下标 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))) // 当匹配到hash值相同，key相同的Entry元素时，返回Entry对象的vlaue return e.value; } return null; }