集合简介
迭代器
Iterable接口
Iterator 接口
Collection接口
List体系
体系结构
List接口
ArrayList源码解析
Map体系
Map接口
HashMap源码分析
HashMap的常见问题
hashCode()、equals()
Set体系
常见实现类
集合遍历
集合工具类 Collections
数组、list的相互转换
使用集合的注意点
jdk源码版本1.8。
体系结构图只列出了常见的接口、类，白色的是接口，黄色的类（包括抽象类）。
集合用于存储指定类型的元素，部分集合还实现了栈、队列、树等数据结构。
集合的两个根接口
Collection 单列集合
Map 双列集合
Map内置了2个单例集合分别存储key、value，key唯一标识一个键值对，使用Set存储，不可重复。
集合的实现类都重写了toString()方法。
iterable 可迭代的，继承了此接口的接口、类都具有可迭代的能力
Iterable接口提供了3个方法，对应3种迭代方式
iterator 迭代器
forEach循环
spliterator()，这个是流式操作中的方法
iterator 迭代器，可通过迭代器迭代元素
Iterator 接口在获取迭代器后，提供了2种迭代方式
while循环 + hasNext() + next()
forEachRemaining()
此外还提供了在迭代中删除底层集合元素的 remove() 方法。
jdk提供了 fail-fast 机制，如果在遍历集合时，其它线程修改了正在遍历的集合，会快速失败，抛出异常。
如果要保证集合的线程安全，尽量使用juc中线程安全的集合。
这篇博文中涉及到的Collection、List、Set、Map接口，都可以仔细看下，学习一下如何设计接口。
相关问题：让你设计一个 list | set | map | 集合，你会怎么设计
Collection接口主要做了2件事
继承了 Iterable 接口，具有迭代能力。Map中存储key、value的2个集合也是Collection体系的，也具有迭代能力。
定义了操作集合本身、单个元素、批量操作、流式操作的一些通用方法。
List 元素有序、可重复，有序是指元素有对应的下标，可通过下标检索元素，元素可重复是建立在元素有序的基础上的。
List的实现类众多，图中只列出了常见的，添加元素时List的常见实现类都可以添加值为null的元素，如果某些实现类不允许添加值为null的元素，则add(null)会抛出空指针异常。
RandomAccess只是一个标记接口，标示具有随机访问能力，一般都是使用内置数组来实现随机访问。
实现 Cloneable 接口，是为了使用根类Object的clone()拷贝集合，但这只是一种浅拷贝。
ArrayList、Vector、Stack
ArrayList、Vector都是基于数组实现的，内置了一个数组，添加元素时如果数组容量不足都会动态扩容。
Vector有一个子类Stack，用于实现栈，Vector、Stack中的很多方法都使用 synchronized 修饰，线程安全，ArrayList则不是线程安全的。
如果不需要保证线程安全，尽量用ArrayList代替Vector；需要要保证线程安全，尽量用juc下的类代替Vector。
LinkedList
LinkedList是基于双向链表实现的list，本身还可以作为（双端）队列使用。
链表本身是按添加顺序进行存储，但不具有下标，所以使用了 AbstractSequentialList 来增加下标操作。AbstractSequentialList 相当于适配器，在链表的基础上增加下标操作。
ArrayList、Vector、LinkedList的比较
ArrayList、Vector基于数组，随机存取，查找元素速度快，但增删元素时要移动大量元素，速度慢，适合以读为主、增删不频繁的场景；LinkedList基于双向链表，查找元素要遍历链表，速度慢，但增删元素只需修改引用，速度快，适合增删元素频繁的场景。
空间利用率 ArrayList、Vector 不如 LinkedList，但这2个类都提供了 trimToSize() 方法用于修剪集合，用容量正合适的数组来存储元素。
ArrayList、LinkedList不是线程安全的，Vector线程安全。维护线程安全有额外开销，且Vector缺点很多，一般不用，如果不要求线程安全，尽量用 ArrayList 代替 Vector。
List中的元素有序（可通过下标操作），List接口定义了常用的下标操作，比如
add()、remove()、set() 在指定位置上添加|删除|更新元素
indexOf() 获取指定元素对应的下标
subList() 获取指定区间上的子集合
ArrayList的部分源码
Arrays.copyOf()、System.arraycopy() 都可以复制数组元素
ArrayList的扩容机制
计算过程如下
如果创建 ArrayList 时没有显式指定初始容量，则第一次添加元素时会取默认容量、所需容量中的较大者作为所需容量；
如果所需容量大于原容量的1.5倍，则取所需容量，否则取原容量的1.5倍
如果目标容量大于容量上限（ Integer.MAX_VALUE - 8 ），则取 Integer.MAX_VALUE
ensureCapacity() 手动扩容
ArrayList、Vector这些基于数组的list都提供了手动扩容的 ensureCapacity() 方法，上面的几个扩容相关的方法都是private，这个是public，暴露出来的手动扩容方法。
如果即将要向ArrayList、Vector、Stack中添加大量元素，可以先调用 ensureCapacity() 一次性扩容，以减少自动扩容次数，提高性能
HashMap：使用哈希表存储元素，使用的哈希值是key的
LinkedHashMap：在哈希表的基础上，增加了一个双向链表维护元素的添加顺序。元素的增改删查都是通过哈希表进行，效率高，更新哈希表时会同步更新到链表，链表只用于遍历。
SortedMap：元素按指定的顺序进行存储。Sorted 有序，指的是存储有序，并没有关联下标。可以用函数式接口 Comparator 指定排序规则。
NavigableMap：可导航的map，可导航指的是提供了一些方法，可以获取key大于、小于指定值的所有键值对，可以获取开头、末尾部分的键值对，可以获取首、尾键值对，可以获取指定区间上的所有键值对。
TreeMap：使用红黑树存储元素。可以构造方法中用 Comparator 接口指定排序规则，未指定时默认使用自然排序。
Hashtable：t是小写，和HashMap一样都是使用哈希表存储元素，但Hashtable线程安全，只是缺点较多，很少使用。
Properties：主要用于加载、解析properties文件
EnumMap：以枚举类的实例作为key
TreeMap可指定排序方式，LinkedHashMap使用双向链表维护添加顺序，TreeMap、LinkedHashMap在某种程度上也可以认为是有序的，只不过不是 list 这种元素关联下标的有序。
性能比较
TreeMap：内部要维护红黑树，增删元素性能差
Hashtable：要保证线程安全，有额外开销，性能差
LinkedHashMap：在HashMap的基础上要维护一个双向链表，增删性能比HashMap稍微差一些，但正由于双向链表，遍历时速度往往比HashMap快。
HashMap：元素的增删查改性能都不错，遍历时需要先过滤掉哈希表中的空桶，速度往往比LinkedHashMap慢。
关于Dictionary
Hashtable在继承Dictionary的同时实现了Map，Dictionary、Map基本是一样的，包含了大量的相同方法
NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.
官方在注释中提示，Dictionary将被废弃，使用Map代替。同时继承Dictionary、实现Map只是作为过渡，后续版本不再 extends Dictionary，直接implements Map。
HashMap、Hashtable的联系与区别
相同点：都是使用哈希表存储元素
HashMap线程不安全，Hashtable提供的方法基本都使用 synchronized 修饰，线程安全
HashMap的key、value都可以为null，Hashtable的key、value都不能为null
Hashtable缺点很多，基本不用，官方建议：如果不需要保证线程安全，尽量使用HashMap代替Hashtable；如果需要保证线程安全，尽量使用juc中的 ConcurrentHashMap 代替 Hashtable。
Map使用内部接口Entry来封装键值对。
成员变量
静态内部类
预留给 LinkedHashMap 重写的空方法
HashMap在自身的元素增删改操作中，分别调用了以下对应的方法，这些方法在HashMap中都是空实现，都是作为扩展点留给LinkedHashMap重写的。
LinkedHashMap在HashMap的基础上要维护链表，对这3个方法的重写都是更新链表，用于在更新哈希表后同步更新链表。
hash()、tableSizeFor()
构造方法
hash系列集合都可以通过构造方法指定初始容量、负载因子。
负载因子较大时，节省内存空间，但容易发生哈希冲突，元素存储效率降低；负载因子较小时，哈希冲突频率低，元素存储效率高，但存在大量空桶、浪费空间，如果不是LinkedHashMap这种有双向链表的，遍历时还需要遍历所有的桶，要判断大量的空桶，遍历速度慢。
默认的负载因子 0.75 是时间、空间的折中，一般使用默认的负载因子即可。
尽量预估元素数量，创建hash系列集合时指定初始容量，避免频繁重哈希，以提升性能，初始容量一般设置为：预估的元素数量 / 0.75，结果向上取整。
put()方法
put()流程
对key进行hash计算，传给 putVal() 方法，后续都是 putVal() 在操作
如果数组为空，则先 resize() 初始化数组
计算数组下标（存储位置）
如果该位置尚未存储元素，则直接存储到该位置；如果该位置已经存储了红黑树或链表，则把元素添加到红黑树中或添加到链表尾部，添加到链表中后，如果链表长度大于8，会将链表转换为红黑树。如果已存在相同的key，不再进行添加，会先记录原来的元素，并替换value。
如果是添加操作，会把哈希表结构修改次数+1、已存储的元素个数+1，如果已存储的元素个数超过重哈希阈值，则进行重哈希，对数组进行扩容。
更新操作返回的是原来的value，添加操作返回的是null。
resize() 扩容|重哈希
resize()除了扩容，还具有初始化功能。
HashMap扩容机制
如果原容量达到容量上限，则重哈希阈值直接取 Integer.MAX_VALUE，不再进行扩容，直接返回原数组，任其发生hash冲突；
如果原容量大于等于默认容量，且扩容为原容量的2倍后仍小于最大容量，则将容量、重哈希阈值都扩大为原来的2倍；
如果原容量为0（负数不合法），且原重哈希阈值大于0，则初始化容量为原重哈希阈值；
否则（原容量、原重哈希阈值都为0），初始化容量为默认容量（16），重哈希阈值为默认容量*默认负载因子再取整（12）。
如果新的重哈希阈值为0，则以单精度浮点数的方式重新计算重哈希阈值。
创建新数组，重新计算存储位置，将原数组各个bucket中存储的元素复制到新数组中，并返回新数组。
get()方法
get()流程
对key进行hash计算，传给 getNode() 方法获取对应的键值对，再从键值对中获取value，不存在对应的键值对时返回null
getNode() 获取对应的键值对时，先计算数组下标，尝试匹配该位置存储的第一个元素，第一个元素匹配就直接返回，如果该位置存储了多个元素，则根据节点类型，从红黑树中获取匹配的键值对，或遍历链表获取匹配的键值对。
开发中用过哪些集合
list：ArrayList、LinkedList
set：HashSet、LinkedHashSet
map：HashMap、LinkedHashMap
juc：CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentHashMap
HashMap的数据结构，和之前版本的区别
jdk6、7：数组+链表，使用链表解决hash冲突
jdk8：数组+链表+红黑树，链表太长会影响哈希表的性能，所以引入了红黑树，链表长度大于8时会转换为红黑树，红黑树节点数量小于6时会退化为链表。总体来看，jdk8的HashMap比jdk7的性能高。
HashMap是如何解决哈希冲突的
使用拉链法，将哈希地址相同的元素存储在链表中。
HashMap使用的哈希算法是怎么实现的
在key的hashCode基础上进行了位移、异或计算，位移16位是时间、空间上折中。
HashMap的容量为什么要是2的n次方
n是哈希表容量（数组长度），hash是 hash(key) 的结果。
将容量指定为2的次方，主要是为了计算哈希地址（数组下标）时的性能考虑
HashMap计算哈希地址（构建的哈希函数）实际使用的是 除留余数法 <code>hash % n</code>，这种方式可以使计算得到的哈希地址比较均匀、分散。
n是2的次方时，<code>hash % n</code> 可以转换为 <code>(n - 1) & hash</code>，位运算 & 比取模 % 高效得多。
添加到链表中时是插入到链表头部还是尾部
jdk8之前：采用头插法，插入链表头部
jdk8及之后：头插法可能发生死循环问题，所以从jdk8开始采用尾插法，插入链表尾部，以解决死循环问题。
HashMap的死循环问题
HashMap不是线程安全的，多线程同时往同一个HashMap的同一个链表中插入元素时，可能出现环形链表，进而导致 get() 获取元素时出现死循环。
在多线程环境下，尽量用 ConcurrentHashMap 代替 HashMap。
相关问题
有没有重写过 hashcode()、equals()？是怎么重写的？
为什么重写 equals() 时必须重写 hashCode()？
为什么要使用hashCode | hashCode的作用
hashCode是专门给哈希表设计的，用于获取获取哈希码值，返回一个 int 型的整数作为哈希码值，在实现哈希表中起着重要作用。
根类Object的hashCode()是native方法，把对象的内存地址转换为int型的整数作为hashCode返回，如果对象的内存地址相同，则hashCode()返回的哈希码值也相同。
hashCode主要有2个作用
计算元素在哈希表中的存储位置（数组下标）
搭配 equals() 用于判断哈希表中是否已存在相同的key|元素
为什么要重写hashCode()、equals()
不重写hashCode()、equals()，默认使用根类Object的这2个方法，情况如下
2个User对象都是new出来的，是不同的对象，它们的hashCode不同，equals()比较内存地址为true，所以都会放到map中。
复用User对象，使用的都是堆中的同一个对象，内存地址相同 => hashCode相同、equals()比较内存地址为true => 哈希表会认为key相同，所以第二个put()是更新操作，只更新对应的value，不会作为新的键值对添加。
从业务逻辑的角度来说，userId都变了，这显然是一个不同的用户，put()应该做添加而非更新。
重写hashCode()、equals()主要是基于业务逻辑上的考虑，确保使用同一个java对象存储不同实体对象的属性时也能被添加到哈希表中。
jdk自带的引用类型（包括String）都重写了 equals()、hashCode()，只需给要存储到哈希表中的、自定义的类重写。这里的存储到哈希表中指的是 HashMap中的key、HashSet中的元素，如果只是作为HashMap的value存储，则不必重写。
重写equals()时为什么要重写hashCode()
因为是根据 hashCode、equals 共同判断哈希表中是否已存在相同的元素|key，只通过equals()无法判断，还需要借助 hashCode。此外根类Object约定
equals() 判断2个对象等价时，这2个对象的 hashCode() 返回的哈希码值也应该相同
所以重写equals()时也应该重写hashCode，确保在equals()返回true时，这2个对象返回的hashCode也相同。
重写hashCode()、equals()的基本原则|要求
equals() 判断2个对象等价，则这2个对象的 hashCode() 返回的哈希码值也应该相同。
这是个充分不必要条件，equals()为true，则hashCode一定相同；hashCode相同，equals()不一定为true。
这也是约定，可在Object类的 hashCode()、equals() 的方法注释上查看这些内容。
重写hashCode()、equals()示例
以上使用的 <code>id.hashCode()</code>、<code>id.equals(another.id)</code> 代码都不健壮，id可能为null，可能发生NPE，使用前应该判断是否为null，或者使用工具类 Objects 中的方法代替
本质都是一样的
Objects的hashCode、equals()源码如下
HashSet
HashSet是通过内置的HashMap实现的，key存储元素，value指向同一个Object对象。
LinkedHashSet
继承自HashSet，实质是使用 LinkedHashMap实现，哈希表+双向链表。
TreeSet
TreeSet实质是通过TreeMap实现的，键值对的value都指向同一个Object对象。
EnumSet
使用内置的 Enum<?>[ ] 存储枚举类实例。EnumSet并没有继承或者内置 EnumMap，但实现思路和EnumMap差不多。
EnumSet：使用数组存储元素，不需要维护链表、树之类的数据结构，性能高。
HashSet：使用哈希表存储元素，增改删查性能不错
LinkedHashSet：在哈希表的基础上还要维护双向链表，增改删查速度比HashSet稍微差一些，但正因为用双向链表维护元素的添加顺序，遍历比HashSet快，可以做到按元素添加顺序进行遍历。
TreeSet：内部要维护红黑树，开销大。
这些set都不是线程安全的，多线程操作时需要用 Collections.synchronizedXxx() 转换为线程安全的集合，或者使用juc提供的CopyOnWriteArraySet、ConcurrentSkipListSet。
单例集合可以直接使用迭代器，Map可以先获取key、value、Entry组成的单例集合，再获取对应的迭代器。
stream 流式操作
forEach
所有集合都可使用
增强的for循环
如果list这种元素关联了下标的，可以使用下标进行迭代
size() 获取已存储的元素个数。
Collections提供了大量的集合操作方法，包括查找最值、二分搜索、统计元素出现次数、替换、排序、反序、同步等，常见的如下
单例集合转数组：单例集合本身都提供了 toArray() 方法可以转换为数组
数组转list：工具类 Arrays.asList()
1、遍历
遍历集合时，不能使用集合本身的删除方法来删除集合元素，会直接抛出异常，可以使用迭代器的remove()来删除迭代器最近一次返回的元素，或使用stream来迭代集合。
使用迭代器遍历集合时，如果循环体内部又嵌套了迭代器，容易出问题，嵌套迭代尽量用增强for循环代替迭代器。
2、集合为空的判断
集合为空、空集合是2个概念，集合为空是指集合自身没有初始化、是null，空集合是指集合自身已初始化、但没有存储元素。空集合用 isEmpty() 进行判断。
3、字符串、list的下标操作
通过下标操作时，一定要考虑下标是否合法、是否会越界。
使用 subXxx(start, end) 提取区间时，都是左闭右开 [start, end) ，如果 start==end ，返回的是空集合、空串。
使用 subXxx() 逐个区间提取时，最后一批的终止坐标应该是元素个数，即 list.size() 或 str.length()，这样才不会遗漏最后一个元素，实际并没有用到最后一个坐标，不会发生越界。