集合

常用集合树：

Collection 接口的接口对象的集合（单列集合）
├ ——-List 接口：元素按进入先后有序保存，可重复
│—————-├ LinkedList 接口实现类，链表，插入删除，没有同步，线程不安全
│—————-├ ArrayList 接口实现类，数组，随机访问，没有同步，线程不安全
│—————-└ Vector 接口实现类数组，同步，线程安全
│———————-└ Stack 是Vector类的实现类
└ ——-Set 接口：仅接收一次，不可重复，并做内部排序
├ —————-└ HashSet 使用hash表（数组）存储元素
│————————└ LinkedHashSet 链表维护元素的插入次序
└ —————-TreeSet 底层实现为二叉树，元素排好序
Map 接口键值对的集合（双列集合）
├ ———Hashtable 接口实现类，同步，线程安全
├ ———HashMap 接口实现类，没有同步，线程不安全-
│—————–├ LinkedHashMap 双向链表和哈希表实现
│—————–└ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└ ———IdentifyHashMap

List和Set的区别：

有序性：
- List：保证按插入顺序排序
- set：set存储和取出顺序不一致
唯一性：
- List：可以重复
- set：元素唯一
获取元素：
- List：可以通过索引直接操作元素
- set：set不能根据索引获取元素

List：

（1）ArrayList：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素

（2）LinkedList ：底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素

（3）Vector:底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素

Set：

(1)HashSet：底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的。

(2)LinkedHashSet：底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。

(3)TreeSet：底层数据结构采用二叉树来实现，元素唯一，它不保留元素的插入顺序，它按升序对元素排序，他不是线程安全的。

HashTable和hashMap的区别：

线程安全：
- HashTable：类中一些方法加入了synchronized关键字，来保证线程安全。
- HashMap：线程不安全。
空值：
- HashTable：不能放入空值
- HashMap：只有一个key可以为null，但是可以有多个value为null。
性能：
- HashTable因为加入synchronized关键字，所以性能较于HashMap较差
- HashMap性能最好。不能保证其元素顺序用作key的对象必须实现hashCode()和equals()方法。

TreeMap：

实现SortMap接口，基于红黑树对所有key进行排序。
排序方式：自然排序和定制排序key以TreeSet的形式存储，要求与TreeSet一致。

HashTable

底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化初始size为11，扩容：newsize = olesize*2+1 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

HashMap

底层数组+链表实现，可以存储null键和null值，线程不安全，初始size为16，扩容：newsize = oldsize*2，size一定为2的n次幂扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀计算index方法：index = hash & (tab.length – 1)

ConcurrentHashMap

底层采用分段的数组+链表实现，线程安全；通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

HashMap底层实现原理：

HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。

HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。
如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。
HashMap底层是通过链表来解决hash冲突的。

JDK 1.8的改变

在Jdk1.8中HashMap的实现方式做了一些改变，但是基本思想还是没有变得，只是在一些地方做了优化，下面来看一下这些改变的地方,数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，在性能上进一步得到提升。

在1.8之前，新插入的元素都是放在了链表的头部位置，但是这种操作在高并发的环境下容易导致死锁，所以1.8之后，新插入的元素都放在了链表的尾部。

HashMap采用hash算法来决定Map中key的存储，并通过hash算法来增加集合的大小。
hash表里可以存储元素的位置称为桶（bucket），如果通过key计算hash值发生冲突时，那么将采用链表的形式，来存储元素。
HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。
HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。

集合