我们都知道Java最基本的数据结构有数组和链表。
数组的特点：空间连续、寻址快、插入和删除时需要移动元素会很慢。
链表的特点：动态增加或减少空间以适应新增和删除元素，但查找时只能顺着一个个节点查找。
而哈希表却能将两者的优点相综合。
JDK1.6 中 HashMap 采用的是位桶+链表的方式，即我们常说的散列链表的方式；JDK1.8中 采用的是位桶+链表/红黑树的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。
如果对红黑树不是很了解的同学，请先移步熟悉 红黑树。
1. 数据结构
HashMap的底层是哈希数组，通过key的hashCode来计算hash值，当hashCode冲突时，通过“拉链法”解决冲突：
如果当冲突很多时，链表长度变长，会造成搜索时间变长，因此JDK1.8之后，当链表长度大于阈值8之后，会将链表变成红黑树。
链表结构：
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;
}
}
红黑树结构：
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;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
2. 各常量、成员变量作用
//创建 HashMap 时未指定初始容量情况下的默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap 的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//装载因子，当 HashMap 中元素数量超过 容量*装载因子 时，进行 resize() 操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//用来确定何时将解决 hash 冲突的链表转变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 用来确定何时将解决 hash 冲突的红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
/* 当需要将解决 hash 冲突的链表转变为红黑树时，需要判断下此时数组容量，若是由于数组容量太小（小于 MIN_TREEIFY_CAPACITY ）导致的 hash 冲突太多，则不进行链表转变为红黑树操作，转为利用 resize() 函数对 hashMap 扩容 */
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素(位桶)的数组
transient Node<K,V>[] table;
// 记录 hashMap 当前存储的元素的数量
transient int size;
// 结构改变次数，fast-fail机制
transient int modCount;
// 新的扩容resize临界值,当实际大小(容量*装载因子)大于临界值时，会进行扩容
int threshold;
// hashMap 装载因子
final float loadFactor;
这里着重说一下装载因子，默认值为0.75，如果实际元素所占容量占分配容量的75%时就要扩容了。如果装载因子很大，说明利用的空间很多，但是查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），HashMap本来是以空间换时间，所以装载因子没必要太大。但是装载因子太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。
3. 构造方法
HashMap一共有4个构造方法，主要区别在于设置初始容量与装载因子上。
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
我们看一下tableSizeFor方法，是用来计算下次需要调整大小的扩容resize临界值 thresold。
此方法将返回(>=cap)的最小2的自然数幂，非常精妙的通过无符号右移的策略来完成，可以值得借鉴。
但是，为什么必须是2的幂呢？我们留下悬念。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
4. 主要方法
4.1 V get(Object key)
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;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
用
key通过hash方法算出来对应的hash值。元素所在位桶的位置为
tab[(n - 1) & hash]，即求余运算。首先判断位桶位置的
Node第一个元素，如果hash值相等并且key相等(或都等于null)，则直接返回。hash值相等，但
key不相等，说明出现冲突。需要判断Node是链表还是红黑树，并从中取值。
hash方法为何如此计算，我们继续留下悬念！
4.2 V put(K key, V value)
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) {
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;
}
如果位桶为空，则通过
resize()方法生成。根据hash获取位桶对应位置的
Node元素，如果为空，则创建并设置到位桶中。如果hash与Node的相等，且key值也与Node的相等，即找到元素。
否则说明有冲突，需要往链表或者红黑树中寻找插值。
如果向链表中插值时，链表长度
>= TREEIFY_THRESHOLD，则需要通过treeifyBin方法将链表转红黑树。最后检查容量是否达到临界值，否则进行扩容。
切记，返回
oldValue。
4.3 Node<K,V>[] resize()
resize() 方法中比较重要的是链表和红黑树的 rehash 操作，先来说下 rehash 的实现原理：
我们在扩容的时候，一般是把长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。如图：
n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的计算示例，图（b）表示扩容后key1和key2两种key确定索引位置的计算示例，其中hash1是key1对应的哈希与高位运算结果。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
因此，我们在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
代码中非常巧妙的用了(e.hash & oldCap) == 0来判断。oldCap仅仅高位为1，其余位为0。因此相&为0说明e.hash最高位为0，否则为1。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold; //设置旧容量、旧阈值，有可能都是0
int newCap, newThr = 0; //新容量、新阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {//如果已到最大容量，直接返回，不再扩容。
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {扩容两倍没有超过最大容量 且 旧容量 >= 16
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;//如果旧容量、旧阈值都为0，则使用默认值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {// 如果新阀值为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) { //重新将旧桶中的数据设置到新桶中。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//红黑树重新rehash
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order //链表重新rehash
// 一个桶中有多个元素，遍历将它们移到新的bucket或原bucket
Node<K,V> loHead = null, loTail = null; //lo原bucket的链表指针
Node<K,V> hiHead = null, hiTail = null; //hi新bucket的链表指针
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
总结：
无需重新计算Hash，节省了时间；
由于所计算的hash(key)位是1是0可以认为是随机的，所以将一个冲突长链表又“均分”成了两个链表，减少碰撞与检索时间。
5. 悬念
5.1 为什么容量必须是2的幂次方？
我们在resize()方法中知道获取 bucketIndex 是通过 tab[(length - 1) & hash]来获取，由于hash我们可以认为是随机的，而 (length - 1) 可以保证最后一位为1(二进制表示),从而保证了 bucketIndex的最后一位同时有为0和为1的可能性，保证了散列的均匀性。反过来讲，若 length 为奇数，length-1 最后一位为0，这样与h按位与(同1为1)的最后一位肯定为0，即索引位置肯定是偶数，这样数组的奇数位置全部没有放置元素，浪费了大量空间。
总而言之：
length为2的幂保证了按位与最后一位的有效性，使哈希表散列更均匀。
5.2 hash方法为何如此计算？
我们知道，使用散列的容器，其高性能的主要影响因素之一就是hash值。
在HashMap中，为了更好的性能，我们希望作为Key的对象提供一个合理的hash函数以便能将其合理的分配到桶中。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
按位异或就是把两个数按二进制，相同就取0，不同就取1。
比如：0101 ^ 1110 的结果为 1011。
无符号右移16位，高16位补0，丢弃掉低16位，那么也就是说小于2^16的数字右移16位后结果为0。
所以，任何一个数，与0按位异或的结果都是这个数本身。
所以这个 hash() 函数对于非null的hash值，仅在其大于等于2^16的时候才会重新调整其值。
有什么好处吗？
我们知道获取 bucketIndex 是通过 tab[(length - 1) & hash]来获取。我们以默认容量16为例。
此时 size-1 =15的二进制为 1111 ，也就是任意二进制最后四位为0000的hash值，都会被存储到位置为0的桶位上，一个桶中的元素太多，就一定会降低其性能，即使使用了红黑树。
而正是由于将大于等于2^16的hash值，将他们的高16位与低16位异或，才能变成另外的值，避免了装到同一桶内。
