一文吃透hashmap的前世与今生
前言
hello,everyone。五一是不是都过得很开心，开始上班是不是有一种恍恍惚惚的感觉，还沉浸在放假当中。今天将给大家介绍的是hashmap，这是日常工作中使用频率最高，面试官最喜欢问的java数据结构之一。不知道大家是不是之前对hashmap【文中无特殊指出，均基于JDK1.8】有过了解，或者阅读过源码，都可以看看这篇文章，希望能给大家带来帮助。如果文中有错误解读之处，也请大家指出~
一.hashmap介绍
学习一个知识之前我们首先要先知道，这个知识对我们的工作与生活有什么用。本文将系统的介绍hashmap的原理。
那么hashmap是什么呢？
Hashmap是一种java中键值对的数据结构，通过key-value形式存储数据。通过key值可以找到对应的value值，类似于字典，通过拼音找到对应的汉字。
二.关键概念介绍
hashmap中有比较多的一些概念，为了照顾一些初学java或者对数据结构不太了解的朋友，这里贴一下一篇博客中的概念介绍
1.数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
2.线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
3.二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
4.哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。 这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作： 插入过程如下图所示
查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。 5.哈希冲突 然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。 来源：https://blog.csdn.net/woshimaxiao1/article/details/83661464
得知hashmap的关键基础概念之后，我们来深入解析以下haspmap到底是个什么东西。
三.关键成员变量
3.1.成员变量说明
//构造hashmap时，默认初始化容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//hashamp的最大容量，2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认扩容的扩展因子，当hashmap中的元素个数达到当前容量的75%时，触发扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//hashmap数组节点上链表转换为红黑的的阈值，链表节点达到8个时转换为红黑树【注意：这里不是绝对，切往后看】
static final int TREEIFY_THRESHOLD = 8;
//链表节点数小于6个时，从红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
//链表转化为红黑的第二个要求，与TREEIFY_THRESHOLD对应，最小的链转树的数组大小。
static final int MIN_TREEIFY_CAPACITY = 64;
//当前已经存在于hashmap中key-value的个数，与容量不同。
transient int size;
//记录hashmap节点修改次数，这个字段用于保障在for循环遍历hashmap时，不可以对hashmap里面的数据发生结构性改变，如删除其中一个key-value，会导致fast-fail【抛出ConcurrentModificationException】，正确的方式是使用迭代器遍历删除。
transient int modCount;
//下个容器的容量，初始化时将会使得容器为2的背书，比如输入容量为11，则容器的初始化大小为16，详见HashMap#tableSizeFor(int cap)方法
int threshold;
//当前hashmap的扩容因子，默认值为DEFAULT_LOAD_FACTOR
final float loadFactor;3.1.1.modCount变量说明
modCount使用来记录遍历hashmap的过程中，hashmap被修改的次数，来看一下modCount的遍历hashmap时的作用
错误示范
public static void main(String[] args) {
HashMap<Object, Object> map = new HashMap<>(15);
for (int i = 0; i < 100; i++) {
map.put(i,i);
}
for (Map.Entry child:map.entrySet()){
if(Objects.equals(child.getKey(),5)){
map.remove(child.getKey());
}
}
System.out.println(map.size());
}
控制台输出
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.HashMap$HashIterator.nextNode(HashMap.java:1445)
at java.util.HashMap$EntryIterator.next(HashMap.java:1479)
at java.util.HashMap$EntryIterator.next(HashMap.java:1477)
at com.examp.util.HashmapDemo.main(HashmapDemo.java:19)正确方式
public static void main(String[] args) {
HashMap<Object, Object> map = new HashMap<>(15);
for (int i = 0; i < 3; i++) {
map.put(i,i);
}
Iterator<Map.Entry<Object, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<Object, Object> entry = iterator.next();
//判断条件，value，可以用entry.getKey进行判断Key值
if(entry.getValue().equals(1)){
//删除
iterator.remove();
}
//删除后输出发现并没有立即删除掉，在第二次循环进入后会发现元素已删，
//因为立即删掉的是it迭代器中的，第二次循环进入后重新获取长度，这也是
//为什么要使用迭代器删除的原因
System.out.println(map.toString());
}
System.out.println(map.size());
}
控制台输出
{0=0, 1=1, 2=2}
{0=0, 2=2}
{0=0, 2=2}
2解析
根据第一个错误示范的控制台输出点击remove方法进去
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
//修改了modCount
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}我们发现在remove方法执行之后，修改了modCount的值，然后在for循环遍历时，遍历到下一个元素时
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
//进行比对
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}发现在元素遍历过程中，hashmap的结构性发生了改变产生了报错。
而使用迭代器方法进行remove时
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}迭代器对hashmap进行操作时，则会对expectedModCount重新赋值，不会报错
那么开发hashmap的人为什么要使用这种机制呢？
回到迭代器的代码，迭代器对expectedModCount重新赋值，因为hashmap是线程不安全，循环的时候无法保证其他线程来修改map的数据结构。迭代器重新赋值了expectedModCount值后，其他线程则会立即检测到数据已经被修改，快速失败。
ps:这种机制我觉得也并没什么ruan用，就是多线程并发我直接给你报错，但是我想要的是数据可以按照先后顺序进行赋值，而且我更改的可能都不是一个key，你这就给我直接失败了，太不人性化了。所以说多线程并发的情况下为了数据能够正确的更新，推荐使用currentHashMap，这个后续有时间了再给大家介绍
四.关键方法解析
hashmap中关键方法为put与get方法，是我们日常工作，学习中95%以上的使用场景。下文将从这两个方法入手探讨hashmap的原理。
4.1.put方法
老规矩先上源码
//put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}//key的hash值计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}/**
* 真正的put方法
*
* @param hash key的hash值
* @param key key值
* @param value value值
* @param onlyIfAbsent 如果为true，则当map中已经存在对应的key，则不进行修改value
* @param evict 如果为false，则表示当前hashmap处于初始构建模式（用于构建LinkedHashMap，此文不做讨论）
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果hashmap为空则进行新建，初始化容量
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果hash定位到的数组位为空则新建一个节点直接放置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果数组节点上的hash值相等则进行数组值替换
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) {
//寻找到尾部key值如果不存在，则进行节点新建，尾插
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;
//容量超过最大容量进行扩容，避免设置扩展因子为1时，容量超出范围
if (++size > threshold)
resize();
//用于构建LinkedHashMap，此文不做解析
afterNodeInsertion(evict);
return null;
}4.1.1.树化：treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//重点！！！！！ 如果数组长度小于最小树化容量（默认数组大小为64时），则优先使用数组扩容，而不是采用转换红黑树节点
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);
}
}树化方法有一个很关键的点
如果数组长度小于最小树化容量（默认数组大小为64时），则优先使用数组扩容，而不是采用转换红黑树节点。
这里是面试官很喜欢的问的点，本菜鸡在早期的面试中也踩过坑，当时光背面经了==。
4.1.2.扩容：resize
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//旧已经存在的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的容器总容量
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果当前元素已经超过最大容量，则不进行扩容操作，将当前容器最大容量赋值为Integer的最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的2倍
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);
}
// 计算新的resize上限
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) {
// 把每个bucket都移动到新的buckets中
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)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 链表优化重hash的代码块
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) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 原索引放到bucket里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到bucket里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}扩容的过程中，将会让数组的长度扩大至当前容量的2倍，数组与链表上的节点进行重新hash计算，使用尾插法的形式，避免了在resize的过程中在JDK1.7Hashmap中会出现的环形链表情况。感兴趣的同学可以自行百度。
4.2.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;
//保证数组不为空，并且hash定位到的数组上的节点数据不为空
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;
}4.3.小问题
这里抛出一个我在面试中很喜欢问别人的一个问题，如果重写hashmap的key的hashcode方法，没有重写equals方法，会出现什么问题，反过来呢？
4.3.1.重写hashCode不重写equals方法
重写hashcode方法后，可能导致不同的对象，hashcode的值变为一样了，需要再根据equals去进行比较，在hashmap上的哈希冲突变多了，比较查询到次数也变多了。
4.3.2.重写equals不重写hashcode方法
user这个对象有10个字段，通过判断身份证号我就判定这两个对象是一个人，但是这个对象年龄可能是不同的。这样会出现重写了equals方法，两个对象是相等的。hashcode方法可能不相等。对应到hashmap中，同样是张三对象这个key，我希望他们是做等价替换的，他们却分布在两个不同的数组节点（数组下挂在的链表或者红黑树）上。
五.总结
本文对hashmap中日常工作中高频出现的一些知识点做了介绍，现在做一个简单的总结。
1.扩容因子：扩容因子默认值设置为0.75，这个值的设置是开发hashmap的大佬通过泊松分布计算的到，如果扩容因子太小，则扩容频繁，浪费空间。扩容因子过大，将会导致hash冲突高频发生，导致链表，树化转换频繁，选中节点元素的时间变长。
2.map遍历：遍历的过程中hashmap通过维护modCount来记录hashmap被修改的次数，避免在多线程并发的情况下，hashmap的数据出现混乱，采用了fast-fail机制。多线程并发下使用hashmap推荐使用concurrentHashmap
3.链表转换红黑树：链表转换红黑树时会做校验，当数组长度大于64并且链表节点数目大于8时才会做转换，红黑树节点小于6个时，转换为链表。
4.扩容：扩容机制从JDK1.7的头插法改为尾插法，避免了在扩容过程中可能产生的环形链表问题，每次扩容大小为当前容量的2倍。
腾讯云开发者
