HashMap实现原理
Hash算法
Hash，一般翻译做“散列”，也直接音译为“哈希”。就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（Hash值）。
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
Hash表
数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，插入和删除容易。
那么综合两者的优势，得到一种寻址容易，插入删除也容易的数据结构，这就是哈希表。哈希表有多种不同的实现方法，这里说的是最常用的一种方法：拉链法，我们可以理解为“链表的数组”，如图（来自于网络）：
index = hash % 16;
图中的Hash算法即是：index = hash % 16;。说明：本图的结构与HashMap十分相似，HashMap中存储的是键值对，而本图的数值相当于HashMap的键。
前方涉及很多源码，注意保护眼睛！
HashMap结构
HashMap的存储容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap做了一些处理。
首先，HashMap里面实现一个静态内部类Entry：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
... ...
}
重要的属性有key，value，next，从属性key，value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础，而next则是用于链表链接的。我们说HashMap就是由一个线性数组实现，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。由于每一个Entry内部都有指向下一个Entry的引用（next），所以这个数组中的每个元素，实际上是一个链表的头部。
/**
* An empty table instance to share when the table is not inflated.
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
HashMap构造
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap(int initialCapacity, float loadFactor) {
... ...
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
... ...
}
通过源码的注释可以看出：
- HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。
- HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和负载因子loadFactor。
- initialCapacity：HashMap的最大容量，即为底层数组的长度。
- loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。
HashMap存储数据的过程
大概的过程是这样的：
计算hash值
final int hash(Object k) {
... ...
}
将hash值转换为数组索引
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
对数组进行存储
存储时若该位置有值，则判断是否equals：是，则替换；否，则将其插入链表表头
看一下源码：
public V put(K key, V value) {
... ...（这里忽略了对null键的处理）
int hash = hash(key);
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后：
- 先处理null键的情况（阅读源码的处理方式为：存在替换，不存在插入table[0]）
- 计算hash值
- 通过hash值计算数组中索引位置
- 遍历该位置的链表
若存在该值（equals返回true），则替换并返回旧值
若不存在则调用addEntry方法，我们看一下这个方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
... ...（省略处理resize）
createEntry(hash, key, value, bucketIndex);
}
该方法调用了createEntry，再来看一下：
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
在本方法中，将原来的值e变为了新值的next（将新值插入了链表头部）
可以看一下Entry的构造方法：
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
HashMap读取数据过程
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
有了上面的基础，这段代码很容易理解。
HashMap的resize过程
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
在数据存储过程中，调用addEntry时，需要先处理resize（调整大小）的过程：
if ((size >= threshold) && (null != table[bucketIndex])) {
// threshold = (int)(capacity * loadFactor);
resize(2 * table.length);
... ...
}
在这里需要指出：
负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。如果负载因子越大，对空间的利用越充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。
这里是resize的过程，就不赘述了：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer函数中进行了对hash值的重新计算。
在addEntry函数中可以看出，resize时是
*2的（大小变为原来的2倍）。那么，我们会有个疑问：为什么是扩大为原来的2倍呢？
看一看上面定义Entry[] table时，有这样一个注释：
The table, resized as necessary. Length MUST Always be a power of two.
长度必须为2的倍数。那么我们又会有疑问，为什么长度一定要是2的幂呢？这就涉及到HashMap的映射算法了。
HashMap的Hash值映射
在使用HashMap时，我们希望这个HashMap里面的元素位置尽量的分布均匀些，最好使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。
最普遍的想法是把hash值对数组长度进行取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用
indexFor(int h, int length)方法来计算该对象应该保存在table数组的哪个索引处。
方法的代码如下：
static int indexFor(int h, int length) {
return h & (length-1);
}
这个方法很巧妙，它通过h & (table.length -1)来得到该对象的保存位置，而HashMap底层数组的length总是 2 的n次方（length-1为2^n-1，全一），这是HashMap在速度上的优化。
而这个又会带了一个问题就是hash值往往很长（很可能比length长得多），这样会导致即使hash值不同，但hash值的低位相同，与length-1进行&操作后的值仍然相同，虽然不影响使用，但会降低效率。
这里HashMap使用了一种技巧来计算hash值：
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这里使用了hash算法重新计算了hash值，而不是直接使用的hashCode方法。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。
参考
http://www.cnblogs.com/xwdreamer/archive/2012/06/03/2532832.html
JDK API：HashMap
