集合

常用集合关系图 各种集合的区别

集合分为单列集合和双列集合两种：

一.单列集合：

Collection的结构图

Collection是单列集合的顶级接口：

其中有三类集合：

1.List（ArrayList,LinkedList,Vector等）

有序的可以重复的集合，JDK1.6和JDK1.7的时候创建集合时初始容量是10，而JDK1.8中默认容量是0，首次添加元素不超过10时，容量变为10。

List的加载因子系数<=1，即当元素个数超过（容器长度*加载因子系数）时，进行扩容

①ArrayList集合是动态数组的数据结构实现的，它的随机访问和遍历的效率比较高，在需要频繁的读取集合中的元素的时候，推荐使用ArrayList，但是增删操作要影响数组内的其他数据的下标，所以增删操作的效率比较慢。

ArrayList每次扩增容量为原本的1.5倍，JDK1.8之后算法为oldCapacity+(oldCapacity >>1)。

ArrayList的扩容上限约21亿，int的最大值。

②LinkedList集合是双向的链表的数据结构实现，没有下标，通过链来连接数据，在非首尾的增加和删除操作时，LinkedList比ArrayList的效率要高，推荐使用LinkedList，但是查询的时候，每次都要从首位移动指针往后依次查找，所以查询的效率比较慢。

③Vector集合与ArrayList集合类似，内部都是维护一个数组，只不过前者在方法上加上了synchronized关键字、线程安全、效率低，后者线程不安全，但是效率高。

Vector每次扩增容量为原来的两倍。

2.Set（HashSet等）

除了TreeSet集合外元素无序，不允许元素重复。

Set的扩容量为原来的2倍，加载因子为0.75。

①HashSet集合是基于HashMap实现的，HashSet底层使用HashMap来保存元素，HashMap是数组和链表的数据结构（下面HashMap具体介绍），HashSet和HashMap的初始容量都是16

3.Queue/Deque

①Queue队列，队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，LinkedList类实现了Queue接口，可以吧LinkedList当成Queue来用

②Deque双端队列，可以在两端进行插入和删除操作

二.双列集合：

Map的结构示意图

1.Map（HashMap,Hashtable等）

①HashMap集合线程非安全，使用键值对（key-value）的方式存储数据，允许key和value为null，键（key）不能重复，值（value）可以重复，它和HashSet是基于哈希表的链表散列的数据结构，即底层是数组和链表（模拟指针）实现的，到了JDK1.8后变成了数组+链表+红黑树。

HashMap底层是通过一个transient（防止反序列化） Node[]table node数组实现的,接下来单个Node数据类型：是HanshMap静态内部类。静态内部类中有一个成员变量：

Node<K,V>next;

 通过该成员变量，其实底层用的是单向链表,性能低

HashMap的结构示意图
HashMap的执行流程

HashMap 基于 Hash 算法实现的，我们通过 put(key,value)存储，get(key)来获取。当传入 key 时，HashMap 会根据 key. hashCode() 计算出 hash 值，根据 hash 值将 value 保存在 bucket 里。当计算出的 hash 值相同时并且equals比较的值不同时，我们称之为 hash 冲突，HashMap 的做法是用链表和红黑树存储相同 hash 值的 value。当 hash 冲突的个数比较少时，使用链表否则使用红黑树。

在向HashMap中添加数据的时候，会先调用hashCode方法计算并比较hash值，当hash相同的情况在调用equals方法比较，当两个均不相同时判定集合中不存在，然后将数据插入到集合中。两个对象的hash值相同，但是不一定是同一个对象，也就是说自身的值可能会不相同。

（例如：String a ="通话";String b="重地";这两个字符串生成的hash值同为1179395，但是其自身的值却不相同）

HashMap和Entry的关系

从图中可以看出： 

1）HashMap继承于AbstractMap类，实现了Map接口。Map是"key-value键值对"接口，AbstractMap实现了"键值对"的通用函数接口。 

2）HashMap是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table, size, threshold, loadFactor, modCount。

table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。

size是HashMap的大小，它是HashMap保存的键值对的数量。 

threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。

loadFactor就是加载因子。 

modCount是用来实现fail-fast机制的。

LinkedHashMap:底层也是一个Entry<k,v>数组，接下来单个Entry数据类型

Entry<K,V>before,after;

②Hashtable线程安全，是线程安全的，但是其同步锁是全局锁，效率很低，所以Hashtable现在是保留类不建议使用。

单线程的情况下HashMap效率高，推荐使用；多线程的情况下可以使用java.util.concurrent包下的ConcurrentHashMap替代，它之前采用Segment方式的分段同步锁，将所有的数据分割成几部分的数据区域，一个区域一把锁，访问不同区域时不会收到影响，JDK1.8版本之后采用优化后的synchronized，将每一个数据分别锁住，不同数据间的访问不会收到影响，效率大大增加，并且线程是安全的，多线程并发情况下很推荐使用！

双列集合的五种遍历方式

1）通过map.keySey();获取所有的key的Set集合，然后可以通过增强for自动迭代，也可以获取迭代器iterator然后用while循环进行手动遍历

2）通过map.values();获得所有的value的集合，返回值为Collecton，然后用增强for自动迭代

3）（推荐）通过map.entrySet();获取所有的键值对的Set集合，Set集合中保存的是每一个键值对（Map.Entry），然后可以通过增强for自动迭代，也可以获取迭代器iterator然后用while循环进行手动遍历

三.关于迭代器

迭代器是Iterator接口：该接口中有三个核心方法 ，维护指针可以向下移动（next），移动到指定位置后，取出当前位置的元素（next），以及重置指针操作（remove）。

为什么数组和集合可以使用for循环进行迭代遍历？

解析：所有的数组和集合都实现了Iterable接口，Iterable接口中只有一个方法，iterator方法返回值类型是Iterator类型，我们将思路转到Iterator，我们发现该接口三个方法。hasNext，next和remove，最主要的是hasNext和next。他们在底层帮我们去维护的可以被迭代数组或者集合的迭代策略。

四.JDK版本差异更新

排序算法

线程安全的集合

集合扩容的算法

五.集合在特定场景下的应用方案

最近浏览可以选取LinkedList

先进先出可以考虑Queue队列

先进后出可以考虑Stack，递归，压栈 ，弹栈