只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树! 为什么用数组+链表? 数组是用来确定桶的位置,利用元素的key的hash值对数组长度取模得到....HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,hash%length。...java.lang.Object@74a14482 null 如果让你实现一个自定义的class作为HashMap的key该如何实现?...(4)通过构造器初始化所有成员,进行深拷贝(deep copy) 如果构造器传入的对象直接赋值给成员变量,还是可以通过对传入对象的修改进而导致改变内部变量的值。...为了保证内部的值不被修改,可以采用深度copy来创建一个新内存保存传入的值。
只是在JDK1.8中,链表长度大于8的时候,链表会转成红黑树! 2.为什么用数组+链表? 数组是用来确定桶的位置,利用元素的key的hash值对数组长度取模得到....HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模,hash%length。...java.lang.Object@74a14482 null 4.如果让你实现一个自定义的class作为HashMap的key该如何实现?...(4)通过构造器初始化所有成员,进行深拷贝(deep copy) 如果构造器传入的对象直接赋值给成员变量,还是可以通过对传入对象的修改进而导致改变内部变量的值。...为了保证内部的值不被修改,可以采用深度copy来创建一个新内存保存传入的值。
幸好 Java 语言提供了并发包(java.util.concurrent),为高度并发需求提供了更加全面的工具支持 今天我要问你的问题是,如何保证容器是线程安全的?...具体选择要看开发的场景需求,总体来说,并发包内提供的容器通用场景,远优于早期的简单同步实现 考点分析 谈到线程安全和并发,可以说是 Java 面试中必考的考点,我上面给出的回答是一个相对宽泛的总结,而且...如果要深入思考并回答这个问题及其扩展方面,至少需要: 理解基本的线程安全工具。 理解传统集合框架并发编程中 Map 存在的问题,清楚简单同步方式的不足。...2.ConcurrentHashMap 分析 我们再来看看 ConcurrentHashMap 是如何设计实现的,为什么它能大大提高并发效率。...,以最优化性能,毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的 可以参考下面这个早期 ConcurrentHashMap 内部结构的示意图,其核心是利用分段设计,在进行并发操作的时候
今天我要问你的问题是,如何保证容器是线程安全的?ConcurrentHashMap如何实现高效地线程安全?典型回答Java提供了不同层面的线程安全支持。...考点分析谈到线程安全和并发,可以说是Java面试中必考的考点,我上面给出的回答是一个相对宽泛的总结,而且ConcurrentHashMap等并发容器实现也在不断演进,不能一概而论。...如果要深入思考并回答这个问题及其扩展方面,至少需要:理解基本的线程安全工具。理解传统集合框架并发编程中Map存在的问题,清楚简单同步方式的不足。...2.ConcurrentHashMap分析我们再来看看ConcurrentHashMap是如何设计实现的,为什么它能大大提高并发效率。...今天我从线程安全问题开始,概念性的总结了基本容器工具,分析了早期同步容器的问题,进而分析了Java 7和Java 8中ConcurrentHashMap是如何设计实现的,希望ConcurrentHashMap
为什么呢?我觉得还是和底层数据结构有关!ArrayList 底层是数组,而 LinkedList 底层是链表。数组天然支持随机访问,时间复杂度为 O(1),所以称为快速随机访问。...但问题是一个 40 亿长度的数组,内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来要存放的位置也就是对应的数组下标。...这个数组下标的计算方法是“ (n - 1) & hash”。(n 代表数组长度)。这也就解释了 HashMap 的长度为什么是 2 的幂次方。 这个算法应该如何设计呢?...另外,在单线程下,如果在遍历过程中对集合对象的内容进行了修改的话也会触发 fail-fast 机制。 “注:增强 for 循环也是借助迭代器进行遍历。...所以,在遍历过程中对原集合所作的修改并不能被迭代器检测到,故不会抛 ConcurrentModificationException 异常。
2、ConcurrentHashMap 分析 我们再来看看 ConcurrentHashMap 是如何设计实现的,为什么它能大大提高并发效率。...首先,我这里强调,ConcurrentHashMap 的设计实现其实一直在演化,比如在 Java 8 中就发生了非常大的变化(Java 7 其实也有不少更新),所以,我这里将比较分析结构、实现机制等方面...现代 JDK 中,synchronized 已经被不断优化,可以不再过分担心性能差异,另外,相比于 ReentrantLock,它可以减少内存消耗,这是个非常大的优势。...这个东西非常小众,大多数情况下,建议还是使用 AtomicLong,足以满足绝大部分应用的性能需求。 后记 以上就是 【JAVA】ConcurrentHashMap 如何实现高效地线程安全? ...的所有内容了; 从线程安全问题开始,概念性的总结了基本容器工具,分析了早期同步容器的问题,进而分析了 Java 7 和 Java 8 中 ConcurrentHashMap 是如何设计实现的,希望 ConcurrentHashMap
存储这个哈希值是为了避免每次 HashMap 需要它时计算哈希。 这是 JAVA 7 中的 Entry 实现的一部分: HashMap 将数据存储到多个条目的单链表(也称为桶或箱)中。...例如,假设您有一个仅将新数据放入 Map 的 Writer 线程和一个从 Map 读取数据的 Reader 线程,为什么它不能工作?...“2” 修改了key的hash值但是HashMap不知道(因为存储了旧的hash值) 您尝试使用修改后的密钥获取对象 该映射计算您的键的新哈希(因此从“2”开始)以查找条目在哪个链表(桶)中 案例 1...由于您修改后的密钥与旧哈希值(存储在条目中)的哈希值不同,因此映射不会在链表中找到该条目。 这是Java中的一个具体示例。...我在我的 Map 中放置了 2 个键值对,我修改了第一个键,然后尝试获取这 2 个值。
注意:普通集合类,太过于基础,这里仅仅是简单回顾,还需要大家有相应基础哈另外:配合我并发编程专栏中的线程池学习并发队列效果更佳。...),每个segment之间互不影响,提高了并发效率默认有16个segment,也就是说,最多支持16个线程并发写的能力,这个16的默认值,可以在初始化concurrnetHash的时候修改这是1.7的,...这么厉害,先看看代码的例子,演示一下注意:arrayList不能迭代的时候修改,报并发修改异常 ,属于fail-fast机制,这个基础的八股就不多讲了哈,这里主要看copyOnwriteList可以并发的修改这是...你管你的修改,我管我的迭代!...另外,copyOnwriteArrayList读写分离,读的时候不会因为Synchronized阻塞读线程的读操作这只是我偶然的发现,正确性有待考证。
//为什么设置 0.75 这个值呢,简单来说就是时间和空间的权衡。...key,value传入进来 //这里onlyIfAbsent如果为true,表明不能修改已经存在的值,因此我们传入false //evict只有在方法 afterNodeInsertion(boolean...//为什么这样说呢,之前我在 tableSizeFor 卖了个关子,需要注意的是,它返回的值是赋给了 threshold 而不是 capacity。...JDK1.8做了改进,用的是尾插法,不会产生死循环。 那么,链表是怎么形成环状的呢? 关于这一点的解释,我发现网上文章抄来抄去的,而且都来自左耳朵耗子,更惊奇的是,连配图都是一模一样的。...(别问我为什么知道,因为我也看过耗子叔的文章,哈哈。然而,菜鸡的我,那篇文章,并没有看懂。。。) 我实在看不下去了,于是一怒之下,就有了这篇文章。
,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。...一、为什么HashCode对于对象是如此的重要: 一个对象的HashCode就是一个简单的Hash算法的实现,虽然它和那些真正的复杂的Hash算法相比还不能叫真正的算法,它如何实现它,不仅仅是程序员的编程水平问题...从上面我看可以看到,对于HashMap和Hashtable的 存取性能有重大影响的首先是应该使该数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode产生不同的 index...既然可以根据HashCode直接定位对象在Hashtable中的位置,那么为什么Hashtable要用key来做映射呢(为了一些思维有障碍的人能看到懂我加了一句话:而不是直接放value呢)?...从上面我看可以看到,对于HashMap和Hashtable的存取性能有重大影响的首先是应该使该数据结构中的元素尽量大可能具有不同的HashCode,虽然这并不能保证不同的HashCode产生不同的index
Java 平台不提供这个接口任何直接的实现。 Set ,是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模,被用来代表集合,就如一副牌。 List ,是一个有序集合,可以包含重复元素。...另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑。...因为不同的 key 值,可能有相同的 hashcode ,所以 value 值需要是链表结构。 他们的共同点都是 hash 算法实现的唯一性,他们都不能持有基本类型,只能持有对象。...因为 HashMap 使用链表存储对象,这个 Entry(包含有键值对的 Map.Entry 对象)会存储在链表中。 ? hashCode 和 equals 方法有何重要性?...为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢?
(下图作为参考) HashSet和HashMap 另外:Synchronized的实现原理 5.Hash1.7是基于数组和链表实现的,为什么不用双链表?HashMap1.8中引入红黑树的原因是?...补充知识点: HashMap如果我想要让自己的Object作为K应该怎么办?...5.Hash1.7是基于数组和链表实现的,为什么不用双链表?HashMap1.8中引入红黑树的原因是?为什么要用红黑树而不是平衡二叉树?...比如,线程A修改了自己的共享变量副本,这时如果该共享变量没有被volatile修饰,那么本次修改不一定会马上将修改结果刷新到主存中,如果此时B去主存中读取共享变量的值,那么这个值就是没有被A修改之前的值...如果该共享变量被volatile修饰了,那么本次修改结果会强制立刻刷新到主存中,如果此时B去主存中读取共享变量的值,那么这个值就是被A修改之后的值了。
可是问题又来了,对象数组又不能适应变化的需求,因为数组的长度是固定的,而且他不能根据我们的操作(增删改查)选择最好的策略,这个时候,为了适应变化的需求,Java就提供了集合类供我们使用。...另外,LinkedHashMap 在上面结构的基础上,增加了一条双向链表,使得键值对的插入顺序以及访问顺序等逻辑可以得以实现。...(除非使用方法瘦身) 2.2 ArrayLsit 扩容机制和并发修改异常(请跳转) 在 001-ArrayList源码分析(含扩容机制等重点问题分析) 文章中,我做过详细的分析,篇幅过长,可跳转阅读。...具体分析可参考我在知乎的回答:Java遍历HashSet为什么输出是有序的?@BWH_Steven 的答案 这个问题非常值得深入分析,对于 Set 和 Map 源码的理解很有帮助!!!...我们在hashCoe方法中返回到了一个等同于本身值的散列值,但是考虑到int类型数据的范围:-2147483648~2147483647 ,着很显然,这些散列值不能直接使用,因为内存是没有办法放得下,一个
当一个值中要存储到Map的时候会根据Key的值来计算出他的 hash,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储 在Object源码分析中解释过,但是这样如果链表过长来的话,HashMap...这个问题我也没有想过,其实很多在看的时候只会在乎红黑树的实现而忽略到了为什么要使用的这个问题,我也是在写本文的时候突发疑惑。...当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。至于为什么阈值是8,我想,去源码中找寻答案应该是最可靠的途径。...显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。...当Map里面的数量超过这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD ?
当一个值中要存储到Map的时候会根据Key的值来计算出他的 hash,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储 在Object源码分析中解释过,但是这样如果链表过长来的话,HashMap...这个问题我也没有想过,其实很多在看的时候只会在乎红黑树的实现而忽略到了为什么要使用的这个问题,我也是在写本文的时候突发疑惑。...当链表长度很小的时候,即使遍历,速度也非常快,但是当链表长度不断变长,肯定会对查询性能有一定的影响,所以才需要转成树。至于为什么阈值是8,我想,去源码中找寻答案应该是最可靠的途径。...显然的,JDK的维护者,后来不认为这个小小的失误值得去修改,所以就这样存在下来了。 ?...当Map里面的数量超过这个值时,表中的桶才能进行树形化 ,否则桶内元素太多时会扩容,而不是树形化 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD ?
前言 本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的知识。 你好,我是彤哥。 上一节,我们一起学习了如何将递归改写为非递归,其中,用到的数据结构主要是栈。...栈和队列,可以说是除了数组和链表之外最基础的数据结构了,在很多场景中都有用到,后面我们也会陆陆续续的看到。 今天,我想介绍一下,在Java中,如何构建一个高性能的队列,以及我们需要掌握的底层知识。...使用数组和链表实现简单的队列,我们前面都介绍过了,这里就不再赘述了,有兴趣的同学可以点击以下链接查看: 重温四大基础数据结构:数组、链表、队列和栈 今天我们主要来学习如何实现高性能的队列。...本例其实还有优化的空间,比如,size的使用,能不能不使用size?不使用size又该如何实现?...另外,最近收到一些同学的反馈,说哈希、哈希表、哈希函数他们之间有关系吗?有怎样的关系?为什么Object中要放一个hash()方法?跟equals()方法怎么又扯上关系了呢?
我的做法肯定是想办法先知道某个Key肯定没有在用了,然后清理到HashMap中对应的K-V。...注意这里和HashMap不太一样的地方,HashMap会在链表太长的时候对链表做树化,把单链表转换为红黑树,防止极端情况下hashcode冲突导致的性能问题,但在WeakHashMap中没有树化。 ...WeakHashMap中resize有另外一个额外的操作,就是expungeStaleEntries(),就是对tab中的死对象做清理,稍后会详细介绍。...key的值,所以只要用indexFor定位到tab中的位置,然后遍历一下单链表就知道了。...这里也是整个WeakHashMap里唯一加了同步的地方。 除了上文说的到resize中调用了expungeStaleEntries(),size()中也调用了这个清理方法。
迭代器中断处理机制 迭代器是操作集合的工具,当我们已经创建了一个迭代器之后,我们就不能再对原集合进行修改,否则可能报错出现问题 实际上迭代器对于中途修改集合的操作给出了两个处理方式: fail-fast...: 集合出现修改情况,迭代器遍历直接报错 我们直接从底层方法讲起: /*Itr迭代器通常使用fail-fast中断处理机制*/ /*判断如何发生其他进程修改集合*/ private class...,并将snapshot的元素复制进去,再将修改内容修改到新集合中 同时COWIterator遍历旧集合,两者之间互不影响 */ } ArrayList 这里我们来介绍一下ArrayList...因为当hash值较为随机时,hash表按破损分布,当负载因子为0.75时,长度超过8的概率仅有亿分之六,这里是为了让树化几率足够小 /*hashCode问题*/ // 索引如何计算...1.在空间占用与查询时间之间取得较好的平衡 2.大于这个数,空间节省了,但链表长度就会比较长从而影响性能 3.小于这个数,效率加快了,但扩容更加频繁,空间占用较多 /*
如何保证容器是线程安全的?ConcurrentHashMap 如何高效的线程安全? Java提供了不同层面的线程安全支持。...ConcurrentHashMap 是如何设计实现的? ConcurrentHashMap 为什么能够大大提高并发效率?...重复扫描、检测冲突是 ConcurrentHash Map的常见技巧我在专栏上一讲介绍 HashMap时,提到了可能发生的扩容问题,在 ConcurrentHashMap 中同样存在。...不过有一个明显区别,就是它进行的不是整体的扩容,而是单独对 Segmen进行扩容,细节就不介绍了。 另外一个Map的size方法同样需要关注,它的实现涉及分离锁的一个副作用。...实现相对简单,先找到哪个节点,然后,在链表中遍历查找。
领取专属 10元无门槛券
手把手带您无忧上云