全站资源开放下载,感谢广大网友的支持
链接失效请移步职业司平台
非盈利平台

非盈利平台

只为分享一些优质内容

Java帮帮-微信公众号

Java帮帮-微信公众号

将分享做到极致

微信小程序

微信小程序

更方便的阅读

职业司微信公众号

职业司微信公众号

实时动态通知

安卓APP

安卓APP

我们从此不分开

程序员生活志-公众号

程序员生活志-公众号

程序员生活学习圈,互联网八卦黑料

支付宝赞助-Java帮帮社区
微信赞助-Java帮帮社区

JAVA集合框架-集合实现(三)[云图智联]

5
发表时间:2020-07-07 10:00

免费学习视频欢迎关注云图智联:https://e.yuntuzhilian.com/

1、ArrayList实现原理:

ArrayList是List接口的可变数组非同步实现,并允许包括null在内的所有元素;

底层使用数组实现;

该集合是可变长度数组,数组扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量增长大约是其容量的1.5倍,这种操作的代价很高。

采用了Fail-Fast机制,面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

remove方法会让下标到数组末尾的元素向前移动一个单位,并把最后一位的值置空,方便GC。

2、LinkedList实现原理:

LinkedList是List接口的双向链表非同步实现,并允许包括null在内的所有元素。

底层的数据结构是基于双向链表的,该数据结构我们称为节点。

双向链表节点对应的类Node的实例,Node中包含成员变量:prev,next,item。其中,prev是该节点的上一个节点,next是该节点的下一个节点,item是该节点所包含的值。

它的查找是分两半查找,先判断index是在链表的哪一半,然后再去对应区域查找,这样最多只要遍历链表的一半节点即可找到。

3、HashMap实现原理:

HashMap是基于哈希表的Map接口的非同步实现,允许使用null值和null键,但不保证映射的顺序。

底层使用数组实现,数组中每一项是个单向链表,即数组和链表的结合体;当链表长度大于一定阈值时,链表转换为红黑树,这样减少链表查询时间。

HashMap在底层将key-value当成一个整体进行处理,这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对,当需要存储一个Node对象时,会根据key的hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;

当需要取出一个Node时,也会根据key的hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Node。

HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置,很耗性能。

采用了Fail-Fast机制,通过一个modCount值记录修改次数,对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount,在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map,马上抛出异常。

4、Hashtable实现原理:

Hashtable是基于哈希表的Map接口的同步实现,不允许使用null值和null键。

底层使用数组实现,数组中每一项是个单链表,即数组和链表的结合体。

Hashtable在底层将key-value当成一个整体进行处理,这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对,当需要存储一个Entry对象时,会根据key的hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;

当需要取出一个Entry时,也会根据key的hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

synchronized是针对整张Hash表的,即每次锁住整张表让线程独占。

5、ConcurrentHashMap实现原理:

ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。

它使用了多个锁来控制对hash表的不同段进行的修改,每个段其实就是一个小的hashtable,它们有自己的锁。只要多个并发发生在不同的段上,它们就可以并发进行。

ConcurrentHashMap在底层将key-value当成一个整体进行处理,这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对,当需要存储一个Entry对象时,会根据key的hash算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;

当需要取出一个Entry时,也会根据key的hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。

与HashMap不同的是,ConcurrentHashMap使用多个子Hash表,也就是段(Segment)。

ConcurrentHashMap完全允许多个读操作并发进行,读操作并不需要加锁。

如果使用传统的技术,如HashMap中的实现,如果允许可以在hash链的中间添加或删除元素,读操作不加锁将得到不一致的数据。

ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。

6、LinkedHashMap实现原理:

LinkedHashMap继承于HashMap,底层使用哈希表和双向链表来保存所有元素,并且它是非同步,允许使用null值和null键。

基本操作与父类HashMap相似,通过重写HashMap相关方法,重新定义了数组中保存的元素Entry,来实现自己的链接列表特性。该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而构成了双向链接列表。

7、HashSet实现原理:

HashSet由哈希表(实际上是一个HashMap实例)支持,不保证set的迭代顺序,并允许使用null元素。

基于HashMap实现,API也是对HashMap的行为进行了封装,可参考HashMap。

8、LinkedHashSet实现原理:

对于LinkedHashSet而言,它继承与HashSet、又基于LinkedHashMap来实现的。LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承与HashSet,其所有的方法操作上又与HashSet相同。

(想要了解更多的职场,职业规划方面的经验,文章第一时间发布于云图智联官网)

免费学习视频欢迎关注云图智联:https://e.yuntuzhilian.com/


Java帮帮学习群生态

Java帮帮学习群生态

总有一款能帮到你

Java学习群

Java学习群

与大牛一起交流

大数据学习群

大数据学习群

在数据中成长

九点编程学习群

九点编程学习群

深夜九点学编程

python学习群

python学习群

人工智能,爬虫

测试学习群

测试学习群

感受测试的魅力

Java帮帮生态承诺

Java帮帮生态承诺

一直坚守,不负重望

初心
勤俭
诚信
正义
分享
友链交换:加帮主QQ2524138991 留言即可 24小时内答复  
业司
满吉教育资讯
会员登录
获取验证码
登录
登录
我的资料
留言
回到顶部