Java基础之HashMap的原理

讲到HashMap不得不讲到HashCode，百度HashCode，它的释义如下
哈希码并不是完全唯一的，它是一种算法，让同一个类的对象按照自己不同的特征尽量的有不同的哈希码，但不表示不同的对象哈希码完全不同。也有相同的情况，看程序员如何写哈希码的算法。
HashCode是用来在散列存储结构中确定对象的存储地址，HashMap正是利用HashCode来快速定位存储对象的。
上面说过HashCode并不是唯一的，他取决于设计的哈希算法，所以在HashMap会出现Hash冲突的情况，那HashMap是怎么处理这种问题的呢？答案是在产生冲突的地方使用链表和红黑树。
在JDK1.8之前解决hash冲突使用的是链表，实际上初始化后的HashMap就是由长度为1的单向链表组成的数组，在发生hash冲突时，该节点的单向链表保存具有相同hashcode的对象。在JDK1.8之后，当节点的单向链表长度大于8时，改为使用红黑树，提高查找效率。
HashMap是日常开发中非常常用的容器，HashMap实现了Map接口，底层的实现原理是哈希表，HashMap不是一个线程安全的容器，jdk8对HashMap做了一些改进，作为开发人员需要对HashMap的原理有所了解，现在就通过源码来了解HashMap的实现原理。
首先看HashMap中的属性
//Node数组
transient Node<K,V>[] table;
//当前哈希表中k-v对个数，实际就是node的个数
transient int size;
//修改次数
transient int modCount;
//元素阈值
int threshold;
//负载因子
final float loadFactor;
这里的threshold = loadFactor * table.length，hash表如果想要保持比较好的性能，数组的长度通常要大于元素个数，默认的负载因子是0.75，用户可以自行修改，不过最好使用默认的负载因子。
Node是用来存储KV的节点，每次put(k,v)的时候就会包装成一个新的Node, Node定义
static class Node<K,V> implements Map.Entry<K,V> {
//hash值
final int hash;
final K key;
V value;
//hash & (capacity - 1) 相同的Node会形成一个链表
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;
}
}
put操作
写入操作是map中最常用的方法，这里看看hashmap的put方法代码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里先计算key的hash值，然后调用putVal()方法，其中hash方法是内部自带的一个算法，会对key的hashcode再做一次hash操作

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
pubVal方法
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) //如果对应的数组为空的话，那么就直接new一个node然后塞进去
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; //如果头结点的key和要插入的key相同，那么就说明找到了之前插入的节点
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) { //如果之前没有put过这个节点，那么就new一个新的节点
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//另外要检查一下当前链表的长度，如果超过8那么就将链表转化成红黑树
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//如果找到了之前的节点，那么就跳出
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //在当前类中NOOP
return oldValue;
}
}
++modCount;
//如果当前元素数量大于门限值，就要resize整个hash表，实际上就是把数组扩大一倍，然后将所有元素重新塞到新的hash表中
if (++size > threshold)
resize();
afterNodeInsertion(evict); //在该类中NOOP
return null;
}
在hashtable中默认的出现冲突的时候就会将冲突的元素形成一个链表，当链表长度大于8的时候就会将链表变成一个二叉树，这是java8中做出的改进，因为在使用hash表的时候在key特殊的情况下最坏的时候hash表会退化成一个链表，那么原有的O(1)的时间复杂度就变成了O(n)，性能就会大打折扣，但是引用了红黑树之后那么在最好的情况下时间复杂度就变成了O(log(n))。
resize方法
final Node<K, V> [] resize() {
......
//去掉了一些代码，只关注最核心的node迁移
//resize会新建一个数组，数组的长度是原来数组长度的两倍
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; //如果没有形成链表的话，就直接塞到新的hash表中
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;
if ((e.hash & oldCap) == 0) { //如果hash值小于oldCap的时候，那么就还在原来那个数组的位置，就把这个节点放到low链表中
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //否则的话就是因为扩展数组长度，就把原来的节点放到high链表中
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; //low链表还放在原来的位置
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead; //high链表放到j+oldCap位置上
}
}
}
}
}
resize操作就是创建一个先的数组，然后把老的数组中的元素塞到新的数组中，注意java8中的hashMap中数组长度都是2的n次幂,2、4、、8、16….. 这样的好处就是可以通过与操作来替代求余操作。当数组扩大之后，那么每个元素所在的位置是可以预期的，就是要不就待在原来的位置，要不就是到j+oldCap位置上，举个栗子，如果原来数组长度为4，那么hash为3和7 的元素都会放在index为3的位置上，当数组长度变成8的时候，hash为3的元素还待在index为3的位置，hash为7的元素此时就要放到index为7的位置上。
resize操作是一个很重要的操作，resize会很消耗性能，因此在创建hashMap的时候最好先预估容量，防止重复创建拷贝。
另外hashmap也是非线程安全的，在多线程操作的时候可能会产生cpu100%的情况，主要的原因也是因为在多个线程resize的时候导致链表产生了环，这样下次get操作的时候就会容易进入死循环。
get方法（）
get的实现比较简单
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 && ((k = first.key) == key || (key != null && key.equals(k)))) //如果节点不为空而且头结点与查找的key相同就返回
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); //遍历链表查找key相同的node
}
}
return null;
}
HashMap的常量和构造函数
//默认初始容量，这个值必须是2的次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
//最大容量，也必须设置成2的次幂
static final int MAXIMUM_CAPACITY = 1 << 30; // 1 073 741 824
//负载因子默认大小
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;
//HashMap中实际就是用这样一个元素类型为Node<K,V>的数组来存储数据，该数组长度必须为2的次幂
//每个Node本质上就是一个单向链表
transient Node<K,V>[] table;
//HashMap大小,它代表HashMap保存的键值对的多少
transient int size;
//HashMap被改变的次数
transient int modCount;
//HashMap扩容的阈值，保存键值对个数大于它就要扩容
int threshold;
//存储负载因子的常量
final float loadFactor;
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;
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
//根据loadFactor以及MAXIMUM_CAPACITY再次计算出新的threshold
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
//数量超过阈值扩容
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
HashMap中的元素单向链表Node是Map.Entry<K,V>的实现，可以看到每一个Node只有next属性，没有pre属性，是一个单向链表
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;
}
}
HashMap中的红黑树也是自己实现的，这里就不详细列出其实现
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//省略...
}
HashMap主要常用API get和put方法
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;
//使用key参与hash运算后得出的hash，找出该位置的链表节点的第一个元素first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//总是先检查链表第一个元素first是否匹配，匹配上就返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//匹配不上，就使用first的next属性找到下一个节点e
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);
}
}
//以上都无法匹配就返回null
return null;
}
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;
//如果使用该hash计算出XM返佣www.fx61.com/brokerlist/xm.html的位置没有元素，就把元素保存在这个位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果该位置有数据，且该节点Node的hash和key都与传入值相同或调用传入键对象的equals方法与节点Node的key比较相同，则覆盖该数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果上面的if判断不满足，且该位置节点Node是红黑树类型，使用红黑树保存
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果if满足也不是红黑树类型节点，则找出该位置单向链表最后一个位置的元素，把它的next指向新传入数据保存位置
else {
for (int binCount = 0; ; ++binCount) {
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;
}
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;
}
为什么HashMap的容量必须设置为2的次幂呢？
其实主要是为了在哈希算法中减少碰撞，使数据均匀分布。这里就不深究了。