一.简介
hashmap本身是一个使用链地址法(拉链法)的哈希表，主干为一个node数组，每个node包含一对key和value，数组的每个位置上存储的为一个个链表。当发生哈希冲突时，key的哈希值相同的node将会放在对应table[i]的链表上。如下图所示：
node1 node2 node3的key的哈希值相同，以链表的形式存储在table[i]处。
ps：jdk1.8版本针对hashmap做了优化，当每个链表上的元素超过8个后，会转换成红黑树，这部分会在之后的微博更新，本文只针对拉链法实现的哈希表做分析
hashmap的主要属性:
//table的默认大小为16，必须为2的幂，每次二倍扩容。
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;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
//node数组
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
//hashmap中元素个数
transient int size;
//修改次数，用于fail-fast机制。
transient int modCount;
//阈值，=容量*装载因子
int threshold;
//装载因子
final float loadFactor;
loadFactor的大小需要认真考虑，如果太大table装的太满会使hash冲突的可能性增大，导致每个桶上链表的长度太长，由于链表的查询的效率为O(n),put，get时时间开销加大。如果loadFactor过小，导致明明没有put进很多元素，就达到了threshold，需要频繁的扩容，增加了空间开销的同时也增加了时间的开销。经过研究最好的折衷值为0.75.
这里说下为什么table的大小为什么一定要是2的幂，为的是put的时候需要求key对应在table上的具体位置，使用hash()&table.size-1,这样与运算的结果相当于对数组的长度n做模运算，而&的效率高于%。
二.实现细节：
1.node中包含key(用final修饰)，value，下一个node，和key的hash值。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
2.哈希函数:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果key为null 则其hash为0，否则用key的hashcode异或其右移16位的值，目的是将key的hashcode高位与低位混合，使高位也参加hash运算，降低发生哈希冲突的可能性。若n的大小为16。
3.put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//如果table为null或者table长度为0，则先resize
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//p = tab[i = (n - 1) & hash 为求该key对应的table的位置，(n-1)&hash其实就是hash%table.size,如果table[(n - 1) & hash ]上无node，则说明没有发生哈希冲突，直接new一个node存储进去。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果table[(n - 1) & hash ]上非空，说明发生冲突
else {
Node<K,V> e; K k;
//这个p为table[(n - 1) & hash ]上node，从前向后遍历，如果存在某个node，其key与传入的key相同，则直接替换这个node。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果p为TreeNode的实例，说明该hashmap已经转换为红黑树，调用putTreeVal方法。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//从table[(n - 1) & hash ]上链表头开始，每经过一次循环，e就指向下一个节点，如果e.next为空，则新建一个node。
//p.next==null说明链表已经遍历到末尾了
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//当链表中节点熟练大于等于8时，转换为红黑树。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//循环过程中可能会发现某node的key与传入的key相同，则替换value。
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;
//如果size>threshold，则resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上述代码看起来可能有点头晕，其实很简单，与jdk1.6的区别就是当bucket上的元素大于8个时，会将链表转换为红黑树。首先判段table表是否为空，如果为空则resize。然后找到key对应在table表上的位置，方法就是用hash()方法返回的值&数组的长度-1，如果table[(n - 1) & hash ]没有元素，直接new一个node放进去，如果table[(n - 1) & hash ]上的节点为红黑树的实例，说明该bucket上已经是红黑树了，则调用putTreeVal方法。否则向后遍历，如果遍历的过程中发现某node的key与put的key相同，则替换value。否则在链表尾部添加上新node。如果链表的长度大于等于8，则调用treeifyBin方法转换成红黑树。如果新put的值替换了原来的值，则返回oldValue旧值，否则返回null。
上述文字可以用下图表示：
当hashmap中元素的个数大于threshold时，会调用扩容方法，将table的大小double。jdk1.8中对此方法进行了优化，如下为jdk1.6中的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);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
//将旧table中的节点迁移到新table
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
//遍历oldtable，新位置及为重新哈希计算后的位置。
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);
}
}
}
很简单，对每个桶上的链表遍历，每个节点的新位置的计算方法和之前一样，重新计算hash&（newTable.length-1）。但是由于使用的是头插入的方式，所以原链表中头部的节点会在尾部，尾部的节点会在头部，颠倒了过来。但这么做有个缺陷，就是在并发put的过程中，会出现死循环。
hash的过程中有个奇妙的规律：假设一个put进入hashcode的key的hash为1111,1101,1011,1111,1111,0101,0011,1101
原table的大小为16，扩容后即为32，则该key在原table的位置为
1111, 1101,1011,1111, 1111, 0101,0011,0101
0000,0000,0000,0000,0000,0000,0000,1111
0000,0000,0000,0000,0000,0000,0000,0101 =5
新table的大小为原来的二倍，即mark在原来的基础上高比特位上多了个1.
1111, 1101,1011,1111, 1111, 0101,0011,0101
0000,0000,0000,0000,0000,0000,0001,1111
0000,0000,0000,0000,0000,0000,0001 ,0101 =21=5+16
由此可见resize之后node的位置为原位置+oldCap。
因此，我们在扩充HashMap的时候，不需要像JDK1.6那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”.这样省去了重新进行&运算的时间，同时可以根据
新增的1bit是0还是1，均匀的将原先冲突的节点分散在新table。
如下为jdk1.8中resize方法，与1.6的区别为新table中的链表的顺序和原来一样，没有倒置。
final Node<K,V>[] resize() {
//如果table表为空
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//超过最大值，则不需要扩容了。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//将threshold左移一位，即二倍扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//遍历旧的table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果table[j]上的节点只有一个，即其next为null，则resize之后，重新hash计算后新位置上也只会有他一个。所以可以直接newTab[e.hash & (newCap - 1)] = e;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是树类型，则添加到红黑树中
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//在table中的新位置与之前一样
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//在table中的新位置=旧位置+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
首先计算e.hash & oldCap，如果是0则原node在新table中的位置不变，如果是1则原node在新table中的位置为原位置+oldCap.然后定义两组node， loHead = null, loTail = null;hiHead = null, hiTail = null;lo组用来连接位置不变的那些节点，hi组用来连接位置改变的那些节点，head指向第一个节点永远不变，通过移动tail来使整个链表连接起来。如下图：
e1,e3,34将由lo组连接起来，循环中loHead一直指向e1不变，lotail指向新链表结尾，最后if (loTail != null)，只需 loTail.next = null;newTab[j] = loHead;即可。
ps:由于扩容过程中将链表差分为两个，顺序不变并放到不同的位置，所以不会出现resize发生死循环的问题。
4.get方法：
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//红黑树
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
1.首先根据参数key的hash找出对应的table的位置，检查桶上第一个节点first，先用==判段传入的key与该节点的key是否相等，如果不相等再调用equals方法。
2.然后判段first节点的下个节点是否为红黑树的实例，如果是则调用红黑树的遍历方法
3.否则循环沿着链表向后遍历，直到结尾。
