本文主要内容
- Hash原理
- 存储过程
- 读取过程
- 总结
各种容器类、线程池等常见Java知识，经常在面试的过程中被问起，工作中也经常被提及，比如为啥说Map的查找效率近似为1。为此，本人接下来会专门总结这类知识。
Hash原理
Object类有本身就有hash方法，但HashMap类中对key的hash值做了专门处理：
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);
}
h是key的原来hash值，map的查找比较有意思，效率非常高，通过计算key的hash值，来确定value的位置，知道位置就能直接读取数组返回对应的value值了。
static int indexFor(int h, int length) {
return h & (length-1);
}
key的hash值取值范围非常宽，基本就是int的最大值与最小值这么分布的，非常的松散，那为什么HashMap还要专门处理下key的hash值呢？
从indexFor方法中能看到，key的hash值与(length-1)相与之后，基本只能保留很小的一部分，如果当前HashMap长度为16，那么相与后，key原本的hash值只能保留最后4位，这样会导致哈希碰撞特别多，影响整体效率。例如下图：
在JDK7中，key的hash值会做4次异或操作，在JDK8中，目前只用做一次异或操作了，异或操作的目的在于：
混合原始哈希码的高位和低位，以此来加大低位的随机性，而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
有数据表明，这么做之后哈希碰撞的概率能减少10%
存储过程
HashMap其实是使用数组进行存储的，但它的数组长度是特定的，只能是2的指数。看看HashMap的初始化方法：
public HashMap(int initialCapacity, float loadFactor) {
// 略过初始长度异常的处理
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
initialCapacity即是用户传入的初始Map长度，capacity 是真实的长度，capacity 初始值为1，当capacity 小于initialCapacity时，则 capacity 向右移1位，即是乘以2，整个过程循环，最终capacity 的值只会是2的指数次幂。
再来查看存储方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
//获取hash值
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;
}
HashMap使用数组来存储数据，数组中元素类型是Entry类型。
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry中有4个成员变量，其中一个是next，我们很容易想到，这可以形成一个链表，所以HashMap其实是使用数组存储数据，如果发生哈希碰撞，那么索引处会形成一个链表。
如果在插入位置已经有一个值了，如果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);
}
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
在addEntry方法中，先取得这个位置上原来的值，然后将数组的这个位置赋值为新的key和value，比较巧妙的是Entry的构造方法，数组新元素的next值即是老的元素e，这样链表也更新的。链表是一直在更新head元素，代码看起来更加简洁。
如果在存储的过程中发现长度不够，则需要扩展数组的长度为先前长度的2倍，这也从侧面印证了HashMap的长度是2的指数幂。
void resize(int newCapacity) {
Entry[] oldTable = table;
Entry[] newTable = new Entry[newCapacity];
//transfer方法将之前数组中的值转移过来
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
因为元素在HashMap中的索引，是由hash和数组长度与计算得到的，所以在元素的转移过程当中，原有元素的位置很可能发生了变化
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);
}
}
}
在数据转移过程中，有趣的是链表值的转移，能够推测出新链表中head值为原来链表中的tail值了，因为newTable[i]的值一直在被重置为链表后边的值。
读取过程
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;
}
读取过程则比较简单了，根据hash查到索引值，如果索引处存在链表，则遍历链表，如果不存在则直接返回了。
总结
HashMap的原理还是比较简单，最复杂的是对hash值的处理，还是文中对链表的操作，理解了这两部分就能很清晰地理解HashMap了。
