Java集合总结

摘要：概述集合类主要有大分支，及。不能保证元素的排列顺序，顺序有可能发生变化不是同步的集合元素可以是但只能放入一个是接口的唯一实现类，可以确保集合元素处于排序状态。如果这两个的通过比较返回，新添加的将覆盖集合中原有的，但不会覆盖。

Java集合类主要有2大分支，Collection及Map。
Collection体系如下：

https://upload-images.jianshu...

https://upload-images.jianshu...

Map体系如下：

https://upload-images.jianshu...

Collection体系如下
https://upload-images.jianshu...

1、List接口和Set接口都继承自Collection接口，Collection接口继承Iterable接口（Iterable有一个Iterator方法），即可迭代的；Collection只能存储引用类型，并且是单个存储；
2、List接口存储元素特点：有序（存进去什么顺序取出来还什么顺序），可重复；Set接口存储元素特点：无序，不可重复
3、实现List接口主要的类包括ArrayList，LinkedList，Vector；实现Set的主要类包括：hashSet，另外还有一个TreeSet接口继承它（自动排序）

（1）ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

（2）特点：
A、查询效率高，插入删除效率低。查找的话，直接通过下标可以查找到，所以效率快；插入删除的话，由于插入（删除）位置后面的元素都需要移动，所以效率较差。
B、size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
C、add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。

https://upload-images.jianshu...

D、数组扩容：
从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。ArrayList默认扩容1.5倍

https://upload-images.jianshu...

E、在源码中看到 int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 这里其实有点意思，数组的最大长度为整数最大值减8。网上看到有人解释： 数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节
参考：https://blog.csdn.net/Chinese...

（3）数组默认长度： 0，表示底层数组的实际大小。容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

https://upload-images.jianshu...

（4）非线程安全。为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

（1）LinkedList同时实现了List接口和Deque接口，也就是说它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（Stack）。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。
（2）关于栈或队列，现在的首选是ArrayDeque（双端队列），它有着比LinkedList（当作栈或队列使用时）有着更好的性能。
A、ArrayDeque内部使用数组实现，并且是循环数组
B、LinkedList内部使用链表实现
具体原因参考：https://blog.csdn.net/weixin_...
LinkedList底层通过双向链表实现。LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

（3）查询效率比较低，插入、删除效率比较高。查询的时候，每次都需要从头开始查询，查询效率O(N)，但是插入（删除）只需要影响到插入位置前后的元素，因此插入（删除）效率较高

（1）和ArrayList一样，底层使用数组实现
（2）vector是线程安全的，效率受到影响。
（3）vector在多线程环境下也会受到线程安全问题。比如说，一个线程去删除i位置上的元素，另外一个线程去拿i位置上的元素，就会报异常。
（4）默认长度：10

Stack是继承自Vector的，所以用法啊，线程安全什么的跟Vector都差不多，只是有几个地方需要注意：

（1）add()和push()，stack是将最后一个element作为栈顶的，所以这两个方法对stack而言是没什么区别的，但是，它们的返回值不一样，add()返回boolean，就是添加成功了没有；push()返回的是你添加的元素。为了可读性以及将它跟栈有一丢丢联系，推荐使用push。

（2）peek()和pop()，这两个方法都能得到栈顶元素，区别是peek()只是读取，对原栈没有什么影响；pop()，从字面上就能理解，出栈，所以原栈的栈顶元素就没了。

ArrayList和Vector本质都是用数组实现的，而LinkedList是用双链表实现的；所以，Arraylist和Vector在查找效率上比较高，增删效率比较低；LinkedList则正好相反。ArrayList是线程不安全的，Vector是线程安全的，效率肯定没有ArrayList高了。实际中一般也不怎么用Vector,可以自己做线程同步，也可以用Collections配合ArrayList实现线程同步。

（1）查询数据，适用ArrayList
（2）插入、删除适用LinkedList
（3）保证数据安全用vector
（4）因为ArrayList在内存不够的时候，默认是原来的1.5倍，vector默认是原来的2倍，因此，当元素数目越来越大，扩展次数多的时候，使用vector比较有优势。

（1）不能保证元素的排列顺序，顺序有可能发生变化
（2）不是同步的
（3）集合元素可以是null,但只能放入一个null

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是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。

https://upload-images.jianshu...

（1）HashMap的结构：HashMap采用了链地址法，也就是数组+链表的方式处理hash冲突（HashMap主要作用是解决hash冲突）。

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。

https://upload-images.jianshu...

简单来说，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。

https://upload-images.jianshu...

（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。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

（1）继承自HashMap
（2）能够按插入的顺序进行遍历。
（3）内部使用双向链表实现。默认按插入元素的顺序排序，也可以更换成按照访问顺序排序。

红黑树算法的实现，说下红黑树的几种特征
（1）颜色特征：节点永远是红色或者黑色
（2）根特征：根节点永远是黑色
（3）外部特征：扩充外部节点都是 空的 黑色节点
（4）内部特征：“红色节点”的两个子节点都是 黑色的
（5）深度特征：任何节点到其子孙外部节点的路径，都包含相同数目的“黑色”节点。

对内部数据使用弱引用。如果内部的键值对在其他地方没有强引用引用着它，当系统内存不够的情况下，系统会自动清除该键值对。可以作为简单缓存表的解决方案（假如直接使用HashMap来存键值对，该键值对不会被GC回收）

（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类。、

HashMap是线程不安全的，ConcurrentHashMap是线程安全的。

（1）采用锁分段技术
HashEntry为基本键值对存储单元，构成HashEntry数组。Segement继承自可重入锁ReentrantLock，充当了锁角色。ConcurrentHashMap将数组分段，每段由一个segment以及它的锁负责。减小锁的粒度能让并发性能更好。当一个线程获得一个segment锁、能够访问其中一段数据的时候，其他分段也能被其他线程正常访问，是互不干扰的。

（2）读写分离
读操作get不需要加锁，写操作put需要在对应的segment加锁。

（3）HashEntery 对象部分属性设为final
降低处理链表时的复杂性，减少了锁相关的操作。

（4）HashEntry 类的 value 域被声明为 Volatile 型
保证了能被多个线程读，而且不会读到过期数据。