- 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: https://blog.csdn.net/tiantuo6513
- cnblogs:https://www.cnblogs.com/baixianlong
- segmentfault: https://segmentfault.com/u/baixianlong
- GitHub: https://github.com/xianlongbai
来源: https://www.cnblogs.com/baixianlong/p/10703558.html