原创不易，如需转载，请注明出处https://www.cnblogs.com/baixianlong/p/10703558.html，否则将追究法律责任！！！
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