1.HashMap和ConcurrentHashMap介绍
核心是一个Node数组,数据结构与hashMap相似
使用CAS操作来实现无锁的更新,提高了并发性。当更新节点时,它会使用CAS来替换节点的值或链接,如果CAS失败,表明有其他线程也在进行修改,当前线程可以重试或锁定节点
对于复杂的结构修改操作 ConcurrentHashMap 使用synchronized关键字来锁定特定的节点。
.CAS是什么
CAS是一种用于实现多线程同步的机制。它是一种无锁的非阻塞算法的一部分,广泛应用于多线程编程中,用于实现高效的同步控制。
CAS的基本思想:
CAS操作包含三个参数:内存位置(V),预期原值(A)和新值(B)。CAS具体操作如下:
比较: 它首先检查内存位置V的当前值是否与预期原值A相等。
交换: 如果相等,那么处理器会自动将该位置值更新为新值B。
否则: 如果不相等,说明其他线程已经修改了该位置的数据,CAS操作失败
hashMap插入的过程
1)计算key的哈希码,使用哈希函数将哈希码转换为数组索引
2)上一步得到的索引,定位到内部数组的特定位置
3)由于不同的键可能产生相同的索引
如果是链表,则遍历链表,使用 equals() 方法比较键对象,直到找到匹配的键。
如果是红黑树,则在树中进行搜索,直到找到匹配的键。
自定义类作为hashmap的key,那么这个key要满足什么要求
1)正确实现 hashCode()、equals()方法
2)如果两个对象通过 equals() 方法比较是相等的,那么这两个对象调用 hashCode() 方法必须产生相同的整数结果。如果两个对象通过 equals() 方法比较是不相等的,理想情况下它们的 hashCode() 方法产生的整数也应该不同
HashMap改用红黑树讲讲为什么**
链表可能会变得很长,这意味着查找效率会降低到O(n)。将链表转换成红黑树,这样即使在最坏的情况下,查找效率也能保持在O(log n)
红黑树
任何一条从根到叶子的路径上各个节点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出两倍,由此达到近似平衡的效果文章来源:https://www.toymoban.com/news/detail-796267.html
2. ArrayList和LinkedList的底层原理和区别**
ArrayList
ArrayList 线程不安全,没有synchronized
LinkedList
ArrayList和LinkedList的区别
ArrayList需要连续内存空间
LinkedList不需要连续内存空间文章来源地址https://www.toymoban.com/news/detail-796267.html
到了这里,关于Java面试基础|数据结构 -实时更新的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!