摘要:最近准备面试,一谈到基础,大部分面试官上来就数据结构素质三连与区别,底层数据结构,为什么能保证线程安全。数组顺序存储,内存连续,查询快,插入删除效率稍微低,不过现在略有改善。而在开始,是由和的方式去实现高并发下的线程安全。
最近准备面试,一谈到java基础,大部分面试官上来就java数据结构素质三连:ArrayList与LinkedList区别,HashMap底层数据结构,ConcurrentHashMap为什么能保证线程安全。
刚毕业的应届生,或者基础不好程序员(比如:本尊,对没错就是我~),只了解皮毛,一稍微深入就gg思密达。面试官:嗯...回头等通知吧~ 基本一首《凉凉》送我到门外了。
不好意思,扯远了! 前两个问题很简单,一个数组一个链表。
数组顺序存储,内存连续,查询快,插入删除效率稍微低(System.copyArray),不过现在略有改善。
链表插入删除快速高效,查询效率差了点意思,存储不连续。
总之,各有利弊吧,根据业务场景选择适合自己的存储结构,不过现在也出现很多类似的改进版本,暂时不谈了(其实我也没了解过,啊哈哈哈~有点尴尬)
HashMap JDK1.8以前基本都是数组+链表实现,JDK1.8开始改为数组+列表,当列表长度大于某个值(具体忘了),链表转化为一个X爆了的数据结构————红黑树(我都吓尿了反正,看了几百遍没记住这玩意各种算法)
其实今天主要是想聊一下这个叫做ConcurrentHashMap的数据结构,看过网上几篇文章实在是看的蛋疼,一来写的一般,对于源码的复制粘贴,最为我看起来吃力;二来红黑树太难,看着难受的一比。是在无法理解这个数据结构的精髓所在,故而想自己写篇文章来记录自己学习的过程,就好比孙悟空去了一趟五指山下,做个标记!
废话少说直接先上jb:
如图所示,相比传统HashMap,jdk1.8之前 ConcurrentHashMap 在传统HashEntry之前增加了一个segment数组。Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,Segment数组中每一个元素就是一把锁,每一个Segment元素存储的是HashEntry数组+链表。而在jdk1.8开始,ConcurrentHashMap是由CAS和Synchronized的方式去实现高并发下的线程安全。
我们主要从的get,put等方法来学习ConcurrentHashMap,是如何插入和获取元素,以及如何保证线程安全。
先看下get方法源码:
public V get(Object key) { Node[] tab; Node e, p; int n, eh; K ek; int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
我看上面的代码好多中间变量,很影响我这种菜鸟分析逻辑,于是我按照自己的编码风格,重写了一下:
public V get(Object key) { int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1 Node[] tab = table; // 一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法) // Hashtable中也是这样实现的,这种方法基本能保证元素在哈希表中散列的比较均匀, // 但取模会用到除法运算,效率很低,HashMap中则通过h&(length-1)的方法来代替取模, // 同样实现了均匀的散列,但效率要高很多,这也是HashMap对Hashtable的一个改进。 Node e = tabAt(tab, (tab.length - 1) & h); if (tab == null || tab.length <= 0 ||e == null) { return null; } if (e.hash == h) { if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey()))){ return e.getValue(); } } else if (e.hash < 0) { Node p = e.find(h, key); return p!= null ? p.getValue() : null; } e = e.next; while (e != null) { if (e.hash != h) { return null; } if (e.getKey() == key || (e.getKey() != null && key.equals(e.getKey()))) return e.getValue(); } return null; }
int h = (key.hashCode() ^ (key.hashCode() >>> 16)) & 0x7fffffff;// 2 ^31 -1
代码的意思————通过哈希值二进制异或该哈希值二进制右移动16位 是为了计算哈希值 再和 上面那玩意进行与运算并不知道是什么鬼。如下图:
计算出Hash值之后要通过hash值找到对应数组的下标进而找到数组元素:
Nodee = tabAt(tab, (tab.length - 1) & h);
(tab.length - 1) & h 根据计算出来的hash值从HashMap的“骨干”——bucket数组找到对应的bucket
java.util.HashMap (ConcurrentHashMap同样)保证bucket数组的长度是2的幂方,所以本来应该写成:
index = n % length的,变为可以写成:index = n & (length - 1) ,“&”效率会高一点。
说了这么多我们来看下tabAt方法:
public static int numberOfLeadingZeros(int i) { // HD, Figure 5-6 if (i == 0) return 32; int n = 1; if (i >>> 16 == 0) { n += 16; i <<= 16; } if (i >>> 24 == 0) { n += 8; i <<= 8; } if (i >>> 28 == 0) { n += 4; i <<= 4; } if (i >>> 30 == 0) { n += 2; i <<= 2; } n -= i >>> 31; return n; } U = sun.misc.Unsafe.getUnsafe(); // 获取unsafe类的实例 单例模式 @CallerSensitive public static Unsafe getUnsafe() { Class arg = Reflection.getCallerClass();//获取调用者方法的类 if (!VM.isSystemDomainLoader(arg.getClassLoader())) { throw new SecurityException("Unsafe"); } else { return theUnsafe; } } Class> ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); @SuppressWarnings("unchecked") static finalNode tabAt(Node [] tab, int i) { return (Node )U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/76858.html
摘要:一算法问题将一群猴子排成一圈,按照猴子数按照依次编号。在计算机编程的算法中,类似问题又称为约瑟夫环。问题是,给定了和,一开始要站在什么地方才能避免被处决四算法设计与实现算法问题存猴子名称给猴子定义名称定义猴子排序个数 一、算法问题 将一群猴子排成一圈,按照猴子数按照1,2,...,n依次编号。然后从第1只开始数,定义数m个猴子,之后将数到的猴子将它踢出圈,从它后面再开始数, 再数到第m...
摘要:行结束符之后的符号有二义性,使得该符号与上条语句能够无缝对接,不导致语法错误。然而在中,有几种特殊语句是不允许行结束符存在的。如果语句中有行结束符,会优先认为行结束符表示的是语句的结束,这在标准中称为限制产生式。 showImg(https://segmentfault.com/img/bVmyZB); 什么是 ASI ? 自动分号插入 (automatic semicolon i...
摘要:是线程安全,性能出色的的线程安全实现,相比较他是线程安全的,相比较他的性能优势非常明显。的源码其实很简单,和的结构一致,但是每一个方法都是用来修饰,以保证操作是线程安全的。这样在多线程的情况下,只有一个线程获取锁操作中的数据。 ConcurrentHashMap ConcurrentHashMap是线程安全,性能出色的Map的线程安全实现,相比较HashMap他是线程安全的,相比较Ha...
摘要:如下代码省略相关代码省略相关代码可以看到在里面,是直接采用数组链表红黑树来实现,时间复杂度在和之间,如果链表转化为红黑树了,那么就是到。 在JDK1.8里面,ConcurrentHashMap在put方法里面已经将分段锁移除了,转而是CAS锁和synchronized ConcurrentHashMap是Java里面同时兼顾性能和线程安全的一个键值对集合,同属于键值对的集合还有Hash...
摘要:与中的类似,也是一个数组加链表,不过这个线程安全。线程安全,但是它的线程安全是依赖将所有修改的代码块都用修饰。这是中实现线程安全的思路,由个组成,每个就相当于一个数组链表。线程安全,但性能差,不推荐使用。 问题描述 翻翻别人的面试经历 这里在知乎上看到的,分享出了自己面试阿里Java岗的面试题。 showImg(https://segmentfault.com/img/bVbfSZ5?...
阅读 2257·2021-11-23 09:51
阅读 3717·2021-11-11 10:57
阅读 1360·2021-10-09 09:43
阅读 2410·2021-09-29 09:35
阅读 1984·2019-08-30 15:54
阅读 1758·2019-08-30 15:44
阅读 3120·2019-08-30 13:20
阅读 1655·2019-08-30 11:19