目录Java集合概述作为Java集合基础的数据结构HashMap和Hashtable的差异HashMap和HashSet的差异ConcurrentHashMap和Hashtable的差异补充： Arraylist和linked lilise
Java集合概述
从下图中可以看到，在Java中，除了以Map结尾的类以外，其他类都实现了Collection接口。 并且，以Map结尾的类都实现了Map接口。
JVA集合的基础数据结构总结1. List
的要素有序、可重复。
Arraylist: Object[]数组Vector:Object[]数组链接列表：双向链表(JDK1.6或更早版本是循环链表，JDK1.7取消循环) http://www.Sina .
的要素是无序的，不可重复的。
HashSet :无序、唯一、基于HashMap实现，基础上采用HashMap存储元素的LinkedHashSet:LinkedHashSet是HashSet的子类，其内部由LinkedHashMap实现TreeSet :有序、唯一的红黑树2. Set，类似于LinkedHashMap内部基于HashMap实现的内容。
HashMap:JDK1.8之前的HashMap由数组链表组成，该链表主要用于解决散列冲突。 从JDK1.8开始，在解决散列冲突时发生了更改。 如果链表的度数为阈值(默认值为8 )，则将链表转换为红色树，以减少搜索时间。 链接的HashMap :由于链接的HashMap继承了HashMap，因此它的基础基于数组和链表/红色树。 除了上述结构之外，LinkedHashMap还添加了一个双向链表，使上述结构能够保持键-值对的插入顺序。 同时通过适当操作链表，实现了访问顺序的相关逻辑。 Hashtable :由数组链表构成，数组是Hashtable的主体，链表主要是解决哈希冲突存在的TreeMap :红黑树
HashMap和Hashtable的区别3. Map
HashMap是非线程安全的。
HashTable是线程安全的，因为HashTable内部的方法基本上由同步限定。
1. 线程是否安全
由于线程安全问题，HashMap比HashTable稍微高效一些。 此外，HashTable已基本废除，请勿在代码中使用。
2. 效率
HashMap可以存储空密钥和值，但只能有一个空密钥，多个空值作为值。
HashTable不能使用空键和空值。 抛出NullPointerException。
3. 对 Null key 和 Null value 的支持
如果在创建时不指定容量初始值
HashMap的默认初始化大小为16。 之后，每次扩展容量都会增加一倍。
Hashtable的默认初始大小为11，之后每次扩展时容量都为原始的2n 1。
4. 初始容量大小
如果在创建时给出了容量的初始值
HashMap将它扩展到2的幂的大小
Hashtable直接使用你给的尺寸
5. 每次扩充容量大小
在解决散列冲突时修改了JDK1.8和更高版本的HashMap。 如果链表长度大于阈值(默认值为8 )，则将链表转换为红黑树以减少搜索时间。
对于3358www.Sina.com/:8，红黑树的平均寻道长度为log(n )=3，链表的平均寻道长度为8/2=4。
Hashtable没有这样的机制。
混洗与混洗的区别混洗的基础是基于混洗的基础实现的。 HashSet的源代码非常少。 clone ()、writeObject、readObject ) )是因为HashSet本身必须实现的其他方法直接调用HashMap中的方法。
HashMapHashSet实现Map接口实现Set接口仅存储关键值对象的调用put ) )向Map添加元素add )方法向调用Set添加元素HashMap使用键(Key )
等性
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
1. 底层数据结构
JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟HashMap 1.8 的结构一样，是数组+链表/红黑二叉树。
Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似，都是采用数组+链表的形式。
2. 实现线程安全的方式
JDK1.7 的ConcurrentHashMap通过分段锁实现线程安全，先对整个桶数组进行分割分段，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据就不会存在锁竞争，提高并发访问率。
JDK1.8 的ConcurrentHashMap摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。synchronized只锁定当前链表或红黑树的首节点，整个看起来就像是优化过且线程安全的 HashMap
Hashtable通过全表锁来实现线程安全，相当于给整个哈希表只加了一把锁，get/put所有相关操作都是synchronized的。在多线程访问的时候，当一个线程访问或操作该对象，其他线程只能进入阻塞或轮询状态。比如某一线程使用put添加元素，那么其他线程不能使用put添加元素，也不能使用get，在并发场景中性能就会非常差。
1. 是否保证线程安全
ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
但是Vector是线程安全的。
2. 底层数据结构
Arraylist 底层使用的是 Object 数组
LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）。
3. 插入和删除是否受元素位置的影响
ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)） 时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
4. 是否支持快速随机访问
ArrayList 支持快速随机访问。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
而LinkedList 不支持高效的随机元素访问。
5. 内存空间占用
ArrayList 的空 间浪费主要体现在在 list 列表的结尾会预留一定的容量空间
LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。
参考：
https://github.com/Snailclimb/JavaGuide
https://www.cnblogs.com/chengxiao/p/6842045.html