【Java成神之路】HashMap 的实现原理/底层数据结构？JDK1.7到JDK1.8的区别
2022-03-15 11:01:57 晓掌柜 版权声明：本文为站长原创文章，转载请写明出处
一、说一下数据结构
在开发过程中，我们常见的数据结构一共有三种：① 数组结构 ② 链表结构 ③ 哈希表结构
1、数组结构：存储空间连续，内存占用严重，空间复杂度高
优点：随机读取和修改率高（数组是连续的，随机访问性强，查找速度快）
缺点：插入和删除的效率低，因为插入数据时后面的数据都要在内存中往后移动，且大小固定不容易进行动态扩展
2、链表结构：存储空间离散，占用内存宽松，空间复杂度小
优点：插入速度快，内存利用率高，没有固定大小，扩展比较灵活
缺点：不能随机查找，每次都是从第一个遍历所以查询效率低
3、哈希表结构：结合数组和链表的优点，实现了查询和修改的高效率，插入和删除效率也比较高
因为不管是写入合适查找，都是拿到制定的Key的hash值，进行查找的。所以操作的只是一个节点的链表数据。效率高！
二、HashMap中的put()和get()的实现原理
1、map.put(k,v)的实现过程
① 首先将k,v封装到Node（节点）对象之中
② 底层调用K的hashCode方法，得出hash值
③ 通过hash算法，将hash值住哪换成数组的下标，如果这个下标上没有任何元素就把Node添加到这个位置。如果说下标对应的位置上有链表，就会用需要操作的K和链表上的每一个节点上的K进行equals比较。如果所有的equals方法返回的都是false，则这个新的节点就会被添加到链表的末尾。但是有任意一个equals方法返回了true则这个节点的value值就会被覆盖。
源码示例如下：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @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;
/* 判断table中是否有元素，如果为空，说明此操作为第一次put操作，接下来++modCount元素个数加一；*/
if ((tab = table) == null || (n = tab.length) == 0)
/* 数组初始化：长度为16；*/
n = (tab = resize()).length;
/* -1的原码为 1000 0001 和hash值作按位与运算计算出数组下标 判断如果对应hash槽上没有元素直接插入；*/
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/* 如果对应的槽上有元素；判断key是否相同，若相同 则直接覆盖value值；*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/* 判断p节点是否为TreeNode的实例 如果为红黑树结构则插入到红黑树对应位置上 */
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
/* 如果key也不相同，也不是红黑树，则此处为链表结构，则需要对链表进行循环遍历 */
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
/* 直到遍历到最后一个节点，将元素放到最后一位（尾插法 1.7版本使用的是头插法）*/
p.next = newNode(hash, key, value, null);
/* 判断如果链表长度大于等于8时 链表转红黑树（TREEITY_THRESHOLD = 8） binCount 从0开始 */
if (binCount >= TREEIFY_THRESHOLD - 1) /* -1 for 1st */
treeifyBin(tab, hash);
break;
}
/* 如果hash值 和 key都相同 跳出循环 */
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
/* 链表中有重复key 将新的value替换 返回旧的value */
if (e != null) { /* existing mapping for key */
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
/* 跳转到此处说明 对应的hash槽没有元素 修改次数+1 */
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2、map.get(K)的实现原理
① 先调用K的hashCode方法，将Hash值缓缓成数组的下标
② 通过上一步Hash算法的出的数组下标，在通过数组下标快速定位到其位置上，如果这个位置上什么都没有就返回null。如果这个位置上有单向链表，那么就拿着K和单向链表上的每一个节点的K进行equals进行比较，如果所有的equals方法都返回了false则get方法返回null。如果其中一个节点K和参数K的equals返回了true，则认为制定K的value存在且为当前value，并最终返回。
三、总结
1、put方法
①在1.7中hashMap是一个数组，数组里面是一个个链表元素。
②其容量保持在2的n次方，也就是说每次扩容会是原来的2倍
③默认的负载因子为0.75
④在进行插入第一个元素时会初始化数组大小
⑤拿到key的hash值并去寻找对应的数组下标
⑥遍历对应下标的链表，查看是否存在这个对应的key
⑦如果有则直接覆盖，没有则写入到该链表中（hash()和equals()结合来检测是否存在相同key）
2、get方法
①根据key拿到对应的数组下标
②遍历下标对应的链表
③直到找到对应的key （equals()判断）
3、JDK1.8中hashMap变化
hashMap是根据key的hash()值来找到对应下标然后遍历其所属链表的。那么如果这个查到的链表长度是很大的就会增加整个操作的复杂度，这个复杂度是O(n)于是乎，在1.8中就引入了红黑树，也就是说在1.8中hashMap是由数组+链表+红黑树组成的在应对上述复杂度问题时，jdk1.8会在链表长度超出8时自动使用红黑树代替链表进行存储以降低其复杂度。
4、jdk1.7中的ConcurrentHashMap
在一次多线程操作中我使用hashMap进行数据读取和存储发现给出下面异常 java.util.ConcurrentModificationException查资料就开始了ConcurrentHashMap的使用之旅下面介绍下ConcurrentHashMap是如何支持并发操作的。
5、ConcurrentHashMap如何支持并发操作
在1.7中ConcurrentHashMap使用分段锁的机制来实现并发操作的，ConcurrentHashMap是由一个个的segment组成的，也就是说数据是放在一个个的segment中的，如果每一个segment支持了线程安全的话，那么整个ConcurrentHashMap也就是线程安全的了
总结：jdk1.7中是用segment来进行颗粒拆分，在put是锁住segment，在get时不进行加锁。但是由于其复杂度受链表长度影响所以在其链表长度过高时效率还是很低。
6、jdk1.8中的ConcurrentHashMap
jdk8中摒弃了复杂的分段锁机制，主要有：
1、不采用segment而采用node，锁住node来实现减小锁粒度。
2、设计了MOVED状态 当resize的中过程中 线程2还在put数据，线程2会帮助resize。
3、使用3个CAS操作来确保node的一些操作的原子性，这种方式代替了锁。
4、sizeCtl的不同值来代表不同含义，起到了控制的作用