Java集合总结
Java集合类主要有2大分支，Collection及Map。 Collection体系如下：
image.png
image.png
Map体系如下：
image.png
** 补充图**
image.png
1、List接口和Set接口都继承自Collection接口，Collection接口继承Iterable接口（Iterable有一个Iterator方法），即可迭代的；Collection只能存储引用类型，并且是单个存储； 2、List接口存储元素特点：有序（存进去什么顺序取出来还什么顺序），可重复；Set接口存储元素特点：无序，不可重复 3、实现List接口主要的类包括ArrayList，LinkedList，Vector；实现Set的主要类包括：hashSet，另外还有一个TreeSet接口继承它（自动排序）
List
1、ArrayList （1）ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。
（2）特点： A、查询效率高，插入删除效率低。查找的话，直接通过下标可以查找到，所以效率快；插入删除的话，由于插入（删除）位置后面的元素都需要移动，所以效率较差。 B、size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。 C、add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。
image.png
D、数组扩容： 从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。ArrayList默认扩容1.5倍
image.png
E、在源码中看到 int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 这里其实有点意思，数组的最大长度为整数最大值减8。网上看到有人解释： 数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节
参考：https://blog.csdn.net/ChineseYoung/article/details/80787071
（3）数组默认长度： 10，表示底层数组的实际大小。容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。
image.png
（4）非线程安全。为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。
2、LinkedList （1）LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。 （2）关于栈或队列，现在的首选是ArrayDeque（双端队列），它有着比LinkedList（当作栈或队列使用时）有着更好的性能。 A、ArrayDeque内部使用数组实现，并且是循环数组 B、LinkedList内部使用链表实现 具体原因参考：https://blog.csdn.net/weixin_35785121/article/details/52165457 LinkedList底层通过双向链表实现。LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。
（3）查询效率比较低，插入、删除效率比较高。查询的时候，每次都需要从头开始查询，查询效率O(N)，但是插入（删除）只需要影响到插入位置前后的元素，因此插入（删除）效率较高
3、Vector （1）和ArrayList一样，底层使用数组实现 （2）vector是线程安全的，效率受到影响。 （3）vector在多线程环境下也会受到线程安全问题。比如说，一个线程去删除i位置上的元素，另外一个线程去拿i位置上的元素，就会报异常。 （4）默认长度：10
4、Stack Stack是继承自Vector的，所以用法啊，线程安全什么的跟Vector都差不多，只是有几个地方需要注意：
（1）add()和push()，stack是将最后一个element作为栈顶的，所以这两个方法对stack而言是没什么区别的，但是，它们的返回值不一样，add()返回boolean，就是添加成功了没有；push()返回的是你添加的元素。为了可读性以及将它跟栈有一丢丢联系，推荐使用push。
（2）peek()和pop()，这两个方法都能得到栈顶元素，区别是peek()只是读取，对原栈没有什么影响；pop()，从字面上就能理解，出栈，所以原栈的栈顶元素就没了。
5、List、ArrayList , LinkedList , Vector的对比 ArrayList和Vector本质都是用数组实现的，而LinkedList是用双链表实现的；所以，Arraylist和Vector在查找效率上比较高，增删效率比较低；LinkedList则正好相反。ArrayList是线程不安全的，Vector是线程安全的，效率肯定没有ArrayList高了。实际中一般也不怎么用Vector,可以自己做线程同步，也可以用Collections配合ArrayList实现线程同步。
6、适用场景 （1）查询数据，适用ArrayList （2）插入、删除适用LinkedList （3）保证数据安全用vector （4）因为ArrayList在内存不够的时候，默认是原来的1.5倍，vector默认是原来的2倍，因此，当元素数目越来越大，扩展次数多的时候，使用vector比较有优势。
Set
1、HashSet （1）不能保证元素的排列顺序，顺序有可能发生变化 （2）不是同步的 （3）集合元素可以是null,但只能放入一个null
2、TreeSet TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。向TreeSet中加入的应该是同一个类的对象。 TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0 自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法。
（1）TreeSet 是二叉树实现的,TreeSet中的数据是自动排好序的，不允许放入null值。
（2）HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
（3）HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashCode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。
Map
image.png
1、HashMap （1）HashMap的结构：HashMap采用了链地址法，也就是数组+链表的方式处理hash冲突（HashMap主要作用是解决hash冲突）。
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。
image.png
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
将对向放入到HashMap或HashSet中时，有两个方法需要特别关心：A、hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象”。所以，如果要将自定义的对象放入到HashMap或HashSet中，需要@Override hashCode()和equals()方法。 B、插入使用头插法
（2）get() get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.getValue()。因此getEntry()是算法的核心。 算法思想是首先通过hash()函数得到对应bucket的下标，然后依次遍历冲突链表，通过key.equals(k)方法来判断是否是要找的那个entry。
image.png
（3）put( ) 当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。 当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部（头插法，形成hash桶）
（4）HashMap的resize（rehash） 当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。 那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。
（5）HashMap的性能参数 有两个参数可以影响HashMap的性能：初始容量（inital capacity，初始为16）和负载系数（load factor，初始为0.75）。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以减少重新哈希的次数。
HashMap 包含如下几个构造器： HashMap()：构建一个初始容量为 16，负载因子为 0.75 HashMap。 HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。 HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。 HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。 initialCapacity：HashMap的最大容量，即为底层数组的长度。 loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。 负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，哈希冲突多，然而后果是查找效率的降低；如果负载因子太小，哈希冲突少，那么散列表的数据将过于稀疏，对空间造成严重浪费。 HashMap的实现中，通过threshold字段来判断HashMap的最大容量： threshold = (int)(capacity * loadFactor) 结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：
（6）Fail-Fast机制 java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。 这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。
在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map (注意到modCount声明为volatile，保证线程之间修改的可见性。)
迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。
2、LinkedHashMap （1）继承自HashMap （2）能够按插入的顺序进行遍历。 （3）内部使用双向链表实现。默认按插入元素的顺序排序，也可以更换成按照访问顺序排序。
3、TreeMap 红黑树算法的实现，说下红黑树的几种特征 （1）颜色特征：节点永远是红色或者黑色 （2）根特征：根节点永远是黑色 （3）外部特征：扩充外部节点都是 空的 黑色节点 （4）内部特征：“红色节点”的两个子节点都是 黑色的 （5）深度特征：任何节点到其子孙外部节点的路径，都包含相同数目的“黑色”节点。
4、WeakHashMap 对内部数据使用弱引用。如果内部的键值对在其他地方没有强引用引用着它，当系统内存不够的情况下，系统会自动清除该键值对。可以作为简单缓存表的解决方案（假如直接使用HashMap来存键值对，该键值对不会被GC回收）
5、HashMap和Hashtable对比 （1）HashMap不是线程安全的；HashTable是线程安全的，其线程安全是通过Sychronized实现。由于上述原因，HashMap效率高于HashTable。 （2）HashMap的键可以为null（key和value都可以），HashTable不可以（key和value都不可以）。 （3）多线程环境下，通常也不是用HashTable，因为效率低。HashMap配合Collections工具类使用实现线程安全。同时还有ConcurrentHashMap可以选择，该类的线程安全是通过Lock的方式实现的，所以效率高于Hashtable。 （4）Hashtable多了一个elements()方法，返回一个Enumeration对象，但是不能用iterator遍历。 （5）Hashtable数组默认大小为11，Hashmap为16，且一定是2的指数。 （6）Hashtable基于Dictionary类，Hashmap基于AbstractMap类。、
6、ConcurrentHashMap高并发原理总结 HashMap是线程不安全的，ConcurrentHashMap是线程安全的。
（1）采用锁分段技术 HashEntry为基本键值对存储单元，构成HashEntry数组。Segement继承自可重入锁ReentrantLock，充当了锁角色。ConcurrentHashMap将数组分段，每段由一个segment以及它的锁负责。减小锁的粒度能让并发性能更好。当一个线程获得一个segment锁、能够访问其中一段数据的时候，其他分段也能被其他线程正常访问，是互不干扰的。
（2）读写分离 读操作get不需要加锁，写操作put需要在对应的segment加锁。
（3）HashEntery 对象部分属性设为final 降低处理链表时的复杂性，减少了锁相关的操作。
（4）HashEntry 类的 value 域被声明为 Volatile 型 保证了能被多个线程读，而且不会读到过期数据。