Java基础篇——集合浅谈
程序员文章站
2022-03-30 21:51:48
原创不易,如需转载,请注明出处 "https://www.cnblogs.com/baixianlong/p/10703558.html" ,否则将追究法律责任!!! Set(基于Map来实现的,不细说) HashSet(不重复、无序、非线程安全的集合) 底层实现,源码如下: public clas ......
原创不易,如需转载,请注明出处,否则将追究法律责任!!!
set(基于map来实现的,不细说)
hashset(不重复、无序、非线程安全的集合)
-
底层实现,源码如下:
public class hashset<e> extends abstractset<e> implements set<e>, cloneable, java.io.serializable { static final long serialversionuid = -5024744406713321676l; //卖个关子,这里为啥要用transient关键字? 评论区见哦! private transient hashmap<e,object> map; private static final object present = new object(); public hashset() { map = new hashmap<>(); } public boolean add(e e) { return map.put(e, present)==null; } ... }
不用多说,是不没想到,原来hashset是基于hashmap实现的,元素都存到hashmap键值对的key上面,而value时有一个统一的值private static final object present = new object();
- 注意:
- 对于hashset中保存的对象,主要要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
- hashset没有提供get()方法,愿意是同hashmap一样,set内部是无序的,只能通过迭代的方式获得
treeset(不重复、有序、非线程安全的集合)
-
底层实现,源码如下:
public class treeset<e> extends abstractset<e> implements navigableset<e>, cloneable, java.io.serializable { private transient navigablemap<e,object> m; private static final object present = new object(); treeset(navigablemap<e,object> m) { this.m = m; } public treeset() { this(new treemap<e,object>()); } public boolean add(e e) { return m.put(e, present)==null; } }
我去,又是这个尿性,基于treemap来实现的 - 注意:
- 首先要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
- 需要实现comparable接口,从而实现有序存储
linkedhashset(不重复、位置有序、非线程安全的集合)
-
底层实现,源码如下:
public class linkedhashset<e> extends hashset<e> implements set<e>, cloneable, java.io.serializable { private static final long serialversionuid = -2851667679971038690l; public linkedhashset(int initialcapacity, float loadfactor) { super(initialcapacity, loadfactor, true); } public linkedhashset(int initialcapacity) { super(initialcapacity, .75f, true); } public linkedhashset() { super(16, .75f, true); } public linkedhashset(collection<? extends e> c) { super(math.max(2*c.size(), 11), .75f, true); addall(c); } }
都是super,实现了把hashset中预留的构造方法启用了,因而可以实现有序插入(linkedhashmap再谈究竟) - 注意:
- 首先要正确重写equals方法和hashcode方法,以保证放入set对象的唯一性
- 内部实现了有序插入,所以使用时不需要考虑
map
hashmap(无序、线程不安全)
-
jdk1.7数据存储结构(采用数组+链表)
-
jdk1.8数据存储结构(采用数组+链表+红黑树)
注意:在链表长度大于8后,查询复杂度由o(n)变为o(logn),将链表存储转换成红黑树存储(也就是treemap)
-
红黑树r-b tree简介(本质其实是2-3-4树):
二叉树特性: (1)左字数上所有的节点的值都小于或等于他的根节点上的值 (2)右子树上所有节点的值均大于或等于他的根节点的值 (3)左、右子树也分别为二叉树 红黑树特点(一种平衡二叉树): (1)每个结点要么是红的要么是黑的。 (2)根结点是黑的。 (3)每个叶结点(叶结点即指树尾端nil指针或null结点)都是黑的。 (4)如果一个结点是红的,那么它的两个儿子都是黑的。 (5)对于任意结点而言,其到叶结点树尾端nil指针的每条路径都包含相同数目的黑结点 节点操作: (1)左旋 (2)右旋 (3)变色
treemap(有序、线程不安全)
- 底层就是红黑二叉树
linkedhashmap(有序、线程不安全)
-
底层实现,源码如下:
static class entry<k,v> extends hashmap.node<k,v> { //这里维护了一个before和after的entry, 见名思意, 就是每个entry<k,v>都维护它的上一个元素和下一个元素的关系。这也是linkedhashmap有序的关键所在。 entry<k,v> before, after; entry(int hash, k key, v value, node<k,v> next) { super(hash, key, value, next); } }
linkedhashmap是继承hashmap, 也就是说linkedhashmap的结构也是和hashmap那样(数组+链表)
注意:linkedhashmap分为插入的顺序排列和访问的顺序排列两种方式,通过accessorder参数来控制
hashtable(线程安全)
- 底层数据结构同hashmap。线程安全,效率低,没什么卵用,需要使用线程安全的map可以使用concurrenthashmap
list
arraylist(位置有序、可重复、线程不安全)
- 底层数据结构是数组,查询快
linkedlist(有序、线程不安全)
- 底层数据结构是双向链表,查询慢,增删快
vector(有序、线程安全)
- 底层数据结构是数组,查询快,增删慢
并发集合
concurrenthashmap(线程安全)
- 利用了锁分段的思想提高了并发度,把map分成了n个segment,每个segment相当于hashtable
copyonwritearraylist(线程安全)
- 读写分离,写时复制出一个新的数组,完成插入、修改或者移除操作后将新数组赋值给array
queue
非阻塞队列
- priorityqueue :实质上维护了一个有序列表
- concurrentlinkedqueue :基于链接节点的、线程安全的队列
阻塞队列
- arrayblockingqueue :一个由数组支持的有界队列。
- linkedblockingqueue :一个由链接节点支持的可选有界队列。
- priorityblockingqueue :一个由优先级堆支持的*优先级队列。
- delayqueue :一个由优先级堆支持的、基于时间的调度队列。
- synchronousqueue :一个利用 blockingqueue 接口的简单聚集(rendezvous)机制。
总结
- 本来想详细的总结一下各种集合的使用和底层实现,但发现说来说去还是数据结构的事,你要能把数组、链表、二叉树、红黑树等数据结构弄明白,这些所谓的集合也就是不同的实现而已。
- 以后有机会还是直接来搞数据结构、算法吧!
个人博客地址:
csdn:
cnblogs:
segmentfault:
github: