HashMap的源码解析
今天我们要解析的HashMap源码是基于jdk1.8。
在正式具体的看HashMap的源码之前，我们先简单的看下，Map(映射)在java 集合框架的位置。
Java 集合框架
由上图，我们其实可以看到，Map其实一种比较特殊的集合，它单独继承AbstractMap，与之对应的是AbstractCollection。可以说，这里就代表了java集合框架的两大类型。Collection和Map。抽象类里一般是放置的公共方法。继承Collection接口的集合，如ArrayList，它的新增方法是
public boolean add(E e) {
add(size(), e);
return true;
}
即新增一个元素。而继承了Map接口的集合或者说映射，如HashMap，它新增元素的方法就是
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
由此就可以明显的区分两大类集合了。
另外，这里的类图其实忽略一个HashTable类。它是继承的Dictionary。且是同步的。和Vector,Stack等类一样，因为都有新的可代替类，所以现在都不提倡使用了。
需要提醒的是，之所以单独搞出这么一个Map类型集合，首先是看重的它的常数时间存取，而这一性能相当依赖HashCode的结果有效性。即通过Hash算法计算出的Hash值的有效性。在jdk中，如果你是使用HashCode，必须了解它对应的equals方法。并且满足HashCode和equals的一些基本约定。
- equals相等，hashcode一定要相等。
- 重写了hashcode也要重写equals。
- hashcode需要保持一致性，状态改变返回的哈希值仍要一致。
- equals的对称，反射，传递等特性。
最后再补充一个类LinkedHashMap。从上图类图可以看出，它是HashMap的子类。之所以要提供这个类，是为满足遍历顺序符合插入顺序的。要知道HashMap是无序的。而LinkedHashMap通过维护一个双向链表支持创建反映访问顺序的实例，所谓的put,get,compute等操作都算是“访问”。
下面我们看下HashMap的源码。
根据HashMap的构造方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
我们可以知道，HashMap最重要的两个属性 initialCapacity和loadFactor。即初始容量和负载因子。一般负载因子默认是0.75。初始容量如果在你已经知道将来这个HashMap里要存多少键值对的情况下，可以通过下面的公式自行设置。
负载因子*容量 > 元素数量
此时，我们就需要提下HashMap的数据结构设计。它可以被看做数组加链表的复合结构，通过key的Hash值在HashMap内置的Hash方法做的位运算结果，决定这个键值对在数组中的寻址。数组被分成了一个个bucket。当Hash值相同，则会在一个桶下以链表的形式存储。就像下图一样。
其实，从这个数据结构看，不难看出其性能的瓶颈。一个瓶颈就是桶数。桶数太多，会占用额外资源，桶数太少，不免要不断的重建数组。另一个瓶颈，则是链表。链表是不善随机查询的。一个极端的情况，如果有攻击不断撞击一个桶，就会形成一个单链表，这样会给虚拟机造成很大的压力。所以，jdk8后，就做了个限制，链表超过一定长度，就会进行树化。这个长度，在jdk源码里默认是
static final int TREEIFY_THRESHOLD = 8;
它是在什么时候判断的呢，请看下面的putVal方法。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由上面源码，我们可以看出，如果hashtable是空的，它会用resize方法进行初始化。resize方法也是HashMap里极其重要的一个方法。因为，它还承担着重建数组的重担。这个时候大家应该会有个疑问，我平时往HashMap里新增元素，是用的put方法呀。这里怎么是putvalue。其实，不难想到，putVal其实就是put的具体实现。只是，在putVal之前，需要使用HashMap自己的hash方法帮助你的key生成个Hash值。而不是直接使用key自己的hashcode方法。源码如下。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
然后我们再回过头看下putVal方法。
如果table不为空，它就会计算下当前键值对应该放到哪个桶里，如果没有，就新建一个桶。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
如果已经存在桶，那么就需要往链表或者红黑树里新增键值对元素了。即
Node<K,V> e
首先它会判断，如果已存在同样的key，它会把原有的value覆盖掉。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
然后是新元素，就会看下它是否是TreeNode类型。TreeNode是HashMap里的一个内部类。代表的就是红黑树节点。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
如果也不是，才会正式开始往链表里新增键值元素。
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
这个时候终于开始做之前的长度判断，来决定是否进行树化。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
进行树化的方法就是treefyBin。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
总的来说，HashMap本质上就是存储键值对的容器。至于它是以什么形式的存储的，其实，我们大多数情况下是不用关心的。集合就是这样的一个东西。它提供了一个方便的方式供我们去存储我们的对象。这也是为什么在日常开发中集合的使用频率这么高的原因。
