HashMap 小结
HashMap 是 Java 里面比较重要的一个类，我们先想想常用的两种数据结构
数组 和 链表
我们先回顾下这两种数据结果的区别
数组的特点是在内存里面是一块连续的存储空间。这样的数据结构使得数组随机读写效率比较高，但是带来的一个问题是在插入或删除数据由于会影响其他元素导致插入或删除效率不高。
链表的特点是每个节点都有一个引用指向下一个节点，这样的好处就是在插入或删除数据的时候对其他节点影响较小，相较数组而言，插入或删除的效率会高很多。但是由于内存地址并不连续，会导致随机访问比较慢，因为需要一个一个遍历。
那我们有没有一种折中的方法，使得随机读写和插入或删除效率都比较理想呢？答案就是 HashMap 。
HashMap 可以认为是一个数组，然后数组的元素是链表。这样就把数组和链表结合到一起了。
下面通过源码(Java 7 版本 )来看下具体是如何将数组和链表结合到一起的。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
... 省略其他代码
// 定义一个数据，里面存放的是 Entry 实例
transient Entry[] table;
... 省略其他代码
// 定义 Entry ， 很明显，是一个链表
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
... 省略其他代码
}
}
刚才聊到了随机读写和插入或删除，那我们从源码角度来看看 HashMap 是如何去做的。
先看 put 方法
public V put(K key, V value) {
// 如果 key 为空，按照 key 为空的逻辑插入 value , 后面再分析 putForNullKey 方法
if (key == null)
return putForNullKey(value);
// 先拿到 key 的 hashCode ,然后用 hash 方法做一次松散处理
int hash = hash(key.hashCode());
// 根据 hash 计算在 table 数组上的索引 ，注意 table[i] 是一个链表
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果有 Entry 的 key 和 hash 和需要查找的 key 一致
// 说明之前放置过，那么久修改 value 为最新的 value , 返回旧的value
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 方法插入
addEntry(hash, key, value, i);
return null;
}
put 方法里面有 2 个比较关键的方法 ** int hash(int h) ** 和 ** int indexFor(int h, int length) **。这 2 个方法的实现如下
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);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
先分析 indexFor() 方法
return h & (length-1);
这里面 length 就是 Entry[] table 的数组长度，而这个 table 的长度永远是 2 的 x 次方。那么 h & (length-1) 就是对 length 取模。
然后还有一个问题，为什么拿到了 key 的 hashCode 后还是需要做一次 hash 操作。那是因为在插入数据的时候，需要判断吧数据插入到数组的哪个元素下面，一般是取 hashCode 然后对数组长度取模，但是如果仅仅用 hashCode 会比较容易出现两个不同的 key 最后计算下来是在同一个数组元素下，这种情况我们称之为碰撞，理想情况下我们当然是不希望发送碰撞的，所有有了 hash 方法来优化碰撞发生的情况。
似乎到这里就结束了，但是有个很关键的方法需要说一下，那就是
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
看最后 2 行
if (size++ >= threshold)
resize(2 * table.length);
size 是当前 HashMap 里面存放的数据个数， threshold 是一个临界值，由容量和重载因子决定。意思是，当 HashMap 里面的数据存放了一定个数的时候，我们需要对 HashMap 做 resize 处理，即扩容。扩容也是一个需要了解的点。我们看看扩容都做了些什么。
void resize(int newCapacity) {
// 记录老的 table
Entry[] oldTable = table;
// 记录老的 table 的长度
int oldCapacity = oldTable.length;
// 如果当前的容量已经是最大了，没法扩容，直接返回
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 申请新的存储空间
Entry[] newTable = new Entry[newCapacity];
// 将旧的数据写入到新的数组中
transfer(newTable);
// 保存新的数组
table = newTable;
// 重新计算临界值
threshold = (int)(newCapacity * loadFactor);
}
大意就是，如果容量已经是最大的容量了，就不扩容，否则就扩容，然后把旧的数据装载到新的数据里面。负责装载的方法就是 transfer ，我们看看这个方法
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
// 记录老的数据
Entry[] src = table;
// 新的大小
int newCapacity = newTable.length;
// 依次取出旧的数组元素
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
// 释放旧的数组
src[j] = null;
// 遍历链表
do {
Entry<K,V> next = e.next;
// 找到键值对新的索引
int i = indexFor(e.hash, newCapacity);
// 插入到数组链表表头
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
整个的 put 过程就是这样啦。我们来总结一下。
首先，如果这个 key 之前有过 put 操作，那么找到对应的 Entry ，修改里面的 value 。如果没有 put 过，那么将这个键值对插入进去，插入后判断是否需要扩容(每次都是容量*2)，如果需要，那么重新申请一个数组，然后把旧的键值对从新插入到新的数组里面去。
