HashMap阅读(jdk1.8)
发布日期:2021-06-28 19:59:42
浏览次数:2
分类:技术文章
本文共 7167 字,大约阅读时间需要 23 分钟。
hashMap有并发问题,1.6是死锁,1.8是丢元素。
先看并发会产生什么现象
import com.alibaba.fastjson.JSON;import com.alibaba.fastjson.serializer.SerializerFeature;import java.util.HashMap;import java.util.Map;import java.util.concurrent.BrokenBarrierException;import java.util.concurrent.CyclicBarrier;import java.util.concurrent.ExecutorService;import java.util.concurrent.Executors;public class HashMapTest implements Runnable { private static Mapmap = new HashMap<>(); private Integer index; private CyclicBarrier barrier; public HashMapTest(Integer index, CyclicBarrier barrier) { this.index = index; this.barrier = barrier; } public static void main(String[] args) throws InterruptedException { CyclicBarrier cyclicBarrier = new CyclicBarrier(128, new Runnable() { @Override public void run() { System.out.println("All are ready"); } }); ExecutorService exec = Executors.newCachedThreadPool(); for (int i = 0; i < 128; i++) { exec.execute(new HashMapTest(i, cyclicBarrier)); } Thread.sleep(10000); System.out.println("map长度为:" + map.size()); System.out.println(JSON.toJSONString(map, SerializerFeature.PrettyFormat)); exec.shutdown(); } @Override public void run() { try { barrier.await(); } catch (InterruptedException e) { e.printStackTrace(); } catch (BrokenBarrierException e) { e.printStackTrace(); } map.put(index + "", Thread.currentThread().getName()); System.out.println("put:i=" + index + ";value=" + Thread.currentThread().getName()); }}
打印第一行,map.size=127;(执行了128次put方法)
第二行,map内容打印出来实际上元素少于127。
执行了10次,没有出现死锁。
* 吐槽:1.8的一点都不好读,各种莫名其妙的变量名,各种if套if
首先是putVal方法。
/** * 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[] tab; Node p; int n, i; if ((p = tab[i = (n - 1) & hash]) == null) // 如果hash后的位置上没有node,则直接放进去 tab[i] = newNode(hash, key, value, null); else { Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // key一致hash也一致则认为要插入的node是已有节点 e = p; else if (p instanceof TreeNode) // 如果p是红黑树的一个节点,则将当前节点也添加进这棵树 e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value); else { // hash冲突,遍历链表 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 // 如果链表长度>8则将hash表中这个位置上的链表转化为红黑树 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) // key一致则认为要插入的node是当前节点。 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) // threshold默认12 resize(); // 这个方法更恶心 afterNodeInsertion(evict); // HashMap中没有内容,先不管他了。 return null; }
putVal方法主要是这么一件事:
- 根据key做hash,然后mod数组的size得到一个数字i(可以看做是索引)
- 在数组a(哈希表)中看第i位有没有内容,没有的话直接放
- 第i位有内容且hash值一致,认为是重复节点。
- 第i位有内容,且是红黑树,则将这个kv放入树种
- 第i位有内容,且是链表,则找到链表的最后一个节点,将kv放到链表末端;如果链表长度>阈值a,则将链表转化为红黑树
- 如果数组a中元素>阈值b,则将数组a扩容,将内容重新摆放。
然后,大家都说扩容会有并发问题,看下resize方法(更恶心)。
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */final Node[] resize() { Node [] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap为哈希表容量 int oldThr = threshold; // 默认16? int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { //MAXIMUM_CAPACITY = 2^30, 一般不可能有这么大 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 容量*2后 <2^30 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; // table.length==0时,初始化成默认16 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // threshold = 0.75*16=12 } if (newThr == 0) { float ft = (float)newCap * loadFactor; // 默认loadFactor=0.75f newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node [] newTab = (Node [])new Node[newCap]; table = newTab; // 上面先不管了,反正一般情况就是将容量*2,触发resize的threshold*2。。 if (oldTab != null) { // 从1开始? for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // 该节点后面没有节点了,直接放 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 如果e是一棵的根结点,则split(将这棵树拆成一大一小两棵树,具体先不关注了。) ((TreeNode )e).split(this, newTab, j, oldCap); else { // 如果该节点后面还有节点,保持顺序。按高低位分为两个链表,分别是loTail(low),hiTail(high) /**比如oldCap=8,hash是3,11,19,27时,(e.hash & oldCap)的结果是0,8,0,8,这样3,19组成新的链表,index为3;而11,27组成新的链表,新分配的index为3+8; */ Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { // 遍历 next = e.next; // if ((e.hash & oldCap) == 0) { // loTail是一个链表,以e为头。链表尾插法 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;}
具体逻辑见注释。到底是哪里发生了并发问题研究出来了再补充
转载地址:https://blog.csdn.net/xxxxssss12/article/details/86589265 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月04日 16时57分06秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
delphi中遍历枚举类型的方法
2019-04-29
Delphi 遍历类中的属性
2019-04-29
jsTree发现一个比较好的树形结构
2019-04-29
C#连接MariaDB
2019-04-29
ajax上传大文件
2019-04-29
Android版本和API Level对应关系
2019-04-29
delphi 查找指定目录,指定扩展名的所有文件名
2019-04-29
介绍两款绘图软件免费的
2019-04-29
怎么样使用delphi 中的statusbar控件改变文字颜色
2019-04-29
sql server 2005 自动重新建立索引
2019-04-29
Android Socket开发
2019-04-29
Opencvsharp 读取摄像头,图片叠加
2019-04-29
自己写的前端验证
2019-04-29
遍历目录下的所有文件
2019-04-29
AJAX 传list数据到后端
2019-04-29
JS文字特效
2019-04-29
table 的表头固定
2019-04-29
html 发光字体和 淡入淡出效果
2019-04-29