集合（List、Set、Map）ArrayList、LinkedList、Vector、HashSet、LinkedHashSet、HashMap
集合：
集合是动态保存多个任意对象，使用增加、删除元素时比较方便（自动扩缩容，不需要自己编写逻辑）；
集合有单列集合Collection和双列集合Map：
其中Collection有两个子接口：Set、List；
List：有序、可以重复、支持索引、允许有多个null；
有三种遍历方式（迭代器、增强for、普通for （因为有索引））；
List有实现类：ArrayList、LinkedList、Vector；
Set：无序、不可以重复、最多有一个null、无索引；
有两种遍历方式：迭代器、增强for；
取出的顺序和添加的顺序不一样，但只要取了 一次，每次都一样；
Set有实现类：HashSet、LinkedHashSet、TreeSet；
Map有三个实现类：HashMap、Hashtable、TreeMap；
保存的是具有映射关系的键值对key-value；
key和value可以是任何引用类型的数据，会封装到HashMap&Node中；
key不允许重复，value可以重复；
key可以为null，但只能有一个，value可以为null，可以有多个；
一对key-value保存到Node中，而Node又实现Entry接口，所以Map有三种遍历方式：
keySet：获取所有键的集合，用get（key）通过键获得对应的值；
values：获取所有值的集合，但无法获取对应的键；
entrySet：获取所有键值对的Set集合，每个元素都是一个Map.Entry对象，代表一个键值对；
迭代器Iterator：所有实现Collection接口的集合类都有一个iterator()方法，遍历集合，并返回一个实现了Iterator接口的对象，但他本身并不存放对象；
Iterator.hashNext()：判断是否还有下一个元素；
Iterator.next()：光标下移，并将下移后集合的元素返回；
注：在iterator.next()前必须先使用iterator.hashNext来判断一下受否还有下一个元素，否则将会抛出异常；
增强for就是简易版的迭代器；
ArrayList：
允许有null，可以多个null；
是由数组来实现数据存储的；
基本等同于Vector，除了ArrayList是线程不安全（但执行效率高），在多线程情况下不建议使用；
扩容机制：ArrayList中维护了一个Object类型的数组elementDate：
translent Object[] elementDate;其中translent表示短暂的，该属性不会被序列化；
当创建ArrayList对象时，如果使用的是无参构造器，则elementDate初始容量为0，第一添加时，会扩容到10，再次扩容时elementDate容量会扩容到10*1.5=15，以此类推；
如果使用的是指定大小的构造器，则elementDate初始容量为指定的大小，如果需要扩容时，则直接扩容为1.5倍，以此类推；
LinkedList：
底层维护了一个双向链表；
LinkedList中维护了两个属性first和last，其中first指向首节点，las指向尾节点；
每个节点（Node对象）里又维护了三个属性pre、next、item，其中通过pre指向前一个节点、next指向后一个节点、item指向实际数据元素；
LinkedList的添加、删除不是通过数组来完成的，而是通过调整节点引用来完成元素的添加和删除的，所以效率更高；
线程不安全，没有实现同步；
LinkedList和ArrayList比较：
ArrayList底层维护的是数组，因为有索引，所以改查效率更高一点；
LinkedList底层维护的是链表，因为增删可以直接通过修改链表的指向即可，所以增删的效率更高一点；
Vector：
底层也是一个对象数组：protected Object[] elementDate；
Vector是线程同步的（即线程安全），Vector中的操作方法synchronized；
扩容机制：创建Vector对象时，如果使用的是无参构造器，则elementDate初始容量为10，如果需要扩容时，会扩容到2倍，以此类推；
如果使用的是有参构造器，则elementDate的初始容量为指定的大小，如果需要扩容时，则直接扩容为2倍，以此类推；
HashSet：
底层是HashMap，HashMap底层是数组+链表+红黑树；
添加一个元素时，先通过计算得到哈希值，然后转变成数组的索引值，根据索引值来看存储数据表table中的对应位置是否已经有存放的元素：
如果没有则直接添加到数组中（链表的头节点）；
如果有则调用equals()来比较：如果相同就放弃添加；
如果不相同则添加到链表的最后；
因为HashSet的底层是HashMap，所以当一条链表的元素个数达到8，且数组中的个数 >= 64，就会进行树化（红黑树）；
扩展：
根据 Java 官方文档和
HashMap的源码实现，链表转换为红黑树的条件是：
- 链表长度 >= 8：一个桶（bucket）中的链表长度达到了 8。
- 数组长度 >= 64：
HashMap的数组长度（即桶的数量）已经达到了 64 或更大。这两个条件必须同时满足，才会触发链表到红黑树的转换。如果其中一个条件不满足，即使链表长度达到了 8，也不会进行树化。它仍然还会保持链表的形式。
LinkedHashSet：
底层是一个LinkedHashMap，底 层维护了一个数组+双向链表；
每一个节点有属性before和after，这样就形成了双向链表；
在添加一个元素时，先求哈希值来确定元素位置，如果没有相同的则直接添加到双向链表中，如果相同则不添加（和HashSet一样）：
如果相等：不执行任何操作，因为集合不允许重复元素；
如果不相等：将新节点插入到双向链表的尾部，并更新相关指针，如：
tail.after = newElement;
newElement.before = tail;
tail = newElement;
其中tail尾节点，newElement新添加的元素；
HashMap：
当添加相同的key时，则会覆盖原来的key-value，等同于 修改，但key不会被替换，value会被替换；
没有实现同步，线程不安全；
底层维维护了Node类型的数组table ：
Node<K,V>[] table数组，默认为null；扩容机制：当创建对象时，加载因子初始为0.75；
当添加元素时，通过key的哈希值来得出在table的索引，判断该索引处是否有元素：
如果没有直接添加；
如果有再判断key是否相等：
如果相等则覆盖（替换value）；
如果key不相等则需判断是树结构还是链表结构并作出相应处理：
如果是链表：将新节点插入链表尾部；
如果是红黑树：按照红黑树规则插入新节点；
第一次添加需扩容table容量为16，临界值16*0.75=12；以后再扩容，table和临界值都扩大两倍32和24，以此类推；
当table大小>= 64且一条链上的元素个数超过默认值8，就会树化（红黑树），链表会转换为红黑树，以提高查找效率； 相反地，如果某个红黑树中的节点数减少到小于 6，它会被转换回链表，以节省空间；
HashSet 和 HashMap 的区别：
HashSet：
是 Java 集合框架中的一个类，它实现了
Set接口。HashSet不保证元素的顺序，并且不允许存储重复元素。它是基于HashMap实现的，具体来说，HashSet使用HashMap的键来存储元素，而值则使用一个静态的对象（通常是一个PRESENT标记），因为HashSet只关心元素是否存在于集合中，而不关心它们关联的值。使用场景：
当你需要一个不包含重复元素的集合时，
HashSet是一个很好的选择；对于频繁的插入、删除和查找操作，
HashSet提供了高效的性能；HashMap：
是 Java 集合框架中的一个类，它实现了
Map接口。HashMap存储键值对（key-value pairs），并且允许一个null键和多个null值。它不保证键值对的顺序，并且基于哈希表（hash table）实现。使用场景：
当你需要一个键值对映射关系，并且需要高效地进行插入、删除和查找操作时，
HashMap是一个很好的选择；它适用于大多数不需要保持插入顺序的场景；
功能差异：
HashSet 关注的是元素的存在性，不允许重复元素，也不关心元素之间的关联值；
HashMap 关注的是键值对的映射关系，允许一个
null键和多个null值；性能相似：
两者都依赖于哈希表结构，因此在插入、删除和查找操作上具有相似的性能特点；
Hashtable（了解即可）：
基本和HashMap一样，但key和value都不能为null，否则会抛出NullPointerExceptioon异常；
是线程安全的；
它是一个更古老的类，最早出现在 Java 1.0 中。
历史原因：
Hashtable 是基于早期的 Java 设计理念，当时的设计目标是提供一种线程安全的哈希表实现，而不允许 null 键和值是为了简化内部实现和避免潜在的并发问题；
Hashtable 最初设计时，Java 还没有引入泛型（generics），并且对 null 的处理相对简单。为了确保线程安全和简化实现，Hashtable 决定不支持 null 键和值。