Java集合部分总结

1. 概述

       首先我们常用的集合分为Set、List、Queue和Map体系，其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表有映射关系的集合，而Java5又新增了Queue体系集合，代表一种队列集合的实现。

2. ArrayList & LinkedList

       常用的List集合有ArrayList、LinkedList。ArrayList首先它的底层是数组，它初始化的时候它的数量是0，当你add的时候它会默认变成10,每次扩容它会是之前容量的1.5倍，它的特性是查询比较快，它的删除效率是比较低的；

       像LinkedList的底层是带头结点和尾结点的双向链表，LinkedList提供了两种插入方式，一个是头插LinkedFirst另一个是尾插LinkedLast，它的特性是非常适合经常删除的场景。它在查询的时候如果量很大是很慢的，原因是：它在查询的时候，因为它是链表查询，拿值进行一个一个的比较，是从第一个开始比较，所以比较慢，而ArrayList查询是根据脚标查询所以比较快。

       还有ArrayList和LinkedList都是不同步的，都不能保证线程安全，保证线程安全的方法有，使用Vector它跟ArrayList一样底层都是数组，其中大部分方法被Synchronized关键字修饰，所以是线程安全的，它的扩容方式是2倍的方式进行扩容。还有一个方法是Collections.synchronizedList()把一个普通的ArrayList包装成一个线程安全的集合。原理就是把所有的方法都套上一层Synchronized,还有就是CopyOnWriteArrayList应用于读多写少的场景。我们先说一下COW思想，如果有多个调用者要求相同的资源，他们会共同获取相同的指针指向直到有调用者修改内容时，系统才会复制一份专用副本给调用者，其他调用者看到的资源仍然保持不变。它的缺点是不能保证数据实时的一致。

3. Set

       Set集合下的HashSet底层是基于HashMap实现的，HashSet除了clone()、writeObject()、readObject()是自己不得不实现外，其他都是调用HashMap；LinkedHashSet是HashSet的子类，其内部是通过LinkedHashMap实现的。

4. Map

       Map集合下常用的有HashMap首先HashMap主要用来放键值对，它是基于哈希表的Map接口实现的，是非线程安全的，HashMap可以存储值为null的key和value，但null作为key只能有一个而作为value却可以有很多个，在jdk1.7的时候它的底层是一个数组加上一个单链表,数组是HashMap的主体，链表是为了解决哈希冲突而存在的(“拉链法解决”)，到了1.8的时候就变成了数组加上单链表或者说是红黑树的方式，单链表和红黑树之间相互转换。他的单链表长度≥8，并且他的数组长度≥64的时候，它的单链表会转化成红黑树的形式。
       它在红黑树的节点数量，如果要是小于6的时候，它会重新再转化成一个单链表这是他底层的一个变化，另外一点就是关于它的数组的数量，默认是16，他的阈值是0.75，这还关乎到它的扩容。
       扩容的时候HashMap会检查数组里元素的个数，因为有loadFactor的默认值是0.75,它的数组长度默认是16，阈值为0.75,16*0.75=12,当他的数组长度大于12的时候，他就会触发扩容，扩容成之前哈希桶长度的而被(哈希表总以2的幂作为哈希表的大小),然后把之前元素重新进行一次哈希计算，然后添加到新的数组里面。

       ConcurrentHashMap:首先它的数据结构在1.7版本底层是个分片数组(分段数组+链表)，为了保证线程安全是有一个Segment锁，这个Segment继承于ReentrantLock来保证线程安全，它每次只给一段加锁来保证它的并发度，而且每一个Segment是一个类似于HashMap的结构，所以每一个HashMap内部可以扩容，但是Segment个数一旦初始化就不能改变，默认是16个，你也可以认为ConcurrentHashMap默认最多16个线程并发。在1.8的时候它改成了与HashMap一样的数据结构就是数组加单链表或者红黑树的数据结构。在1.8版本也放弃了这种分片锁机制，而使用Synchronized+CAS操作。因为1.6版本的时候JVM对Synchronized版本的优化非常大。现在也是用这种方法来保证安全。在1.7版本的时候默认是Segments[0]默认大小是2，负载因子是0.75,2*0.75=1.5插入第二个才会扩容。

5. ConcurrentHashMap和HashTable的区别

底层数据结构：JDK1.7的时候，ConcurrentHashMap底层采用分段数组+链表实现，JDK1.8中采用与HashMap1.8一样数组+链表/红黑树。HashTable和JDK1.8之前的HashMap的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主题，链表则是为了解决Hash冲突而存在的。
实现线程安全方式（重要）：①在Jdk1.7的时候，ConcurrentHash（分段锁）对整个桶数组进行了分段分割(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器不同数据段的数据就不会存在锁竞争，提高并发访问率。到了JDK1.8的时候已经摒弃了Segment的概念，而是直接使用数组+链表/红黑树的数据结构来实现，并发控制使用Synchronized和cas操作。虽然在JDK1.8中还能看到Segment的数据结构但也是为了兼容旧版本。②HashTable（通一把锁）：使用Synchronized来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或者轮询。

6.LinkedHashMap（有序的Map）

       LinkedHashMap是HashMap的子类，使用双向链表来维护key-value对的次序(其实只需要考虑key的次序)，该链表负责维护Map的迭代顺序，迭代顺序与插入顺序保持一致。
       LinkedHashMap可以避免对HashMap、HashTable里的key-value对进行排序(只要插入key-value对时保持顺序即可)，同时又可以避免使用TreeMap所增加的成本。
       LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能；但是因为它以链表来维护内部顺序，所以在迭代访问Map里的全部元素时将有较好的性能。
       LinkedHashSet 链表和hash表组成，由链表保证元素的排序，由hash表保证元素的唯一。

附录

附录1.集合面试点

这是之前我收集到资料