集合：

集合是动态保存多个任意对象，使用增加、删除元素时比较方便（自动扩缩容，不需要自己编写逻辑）；

集合有单列集合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 键和值。