1.集合类分三个顶级接口：Set,List,Map,其中Set List 继承至Collection接口，Map为独立接口。
2.分类
Set下有HashSet，LinkedHashSet，TreeSet
List下有ArrayList，Vector，LinkedList
Map下有AbstractMap AbstractMap下 Hashtable，LinkedHashMap，HashMap，TreeMap
ArrayList优点: 底层数据结构是数组，查询快，增删慢。缺点: 线程不安全，效率
Vector优点: 底层数据结构是数组，查询快，增删慢。缺点: 线程安全，效率低
LinkedList优点: 底层数据结构是链表，查询慢，增删快。缺点: 线程不安全，效率高
3.常见的集合
HashSet
底层数据结构是哈希表。(无序,唯一)
如何来保证元素唯一性?
1.依赖两个方法：HashSet的构造方法其实就是在内部实例化了一个HashMap对象，通过hashCode()和equals()
如果hash码值相同，且equles判断相等，说明元素已经存在，不存；
如果hash码值相同，且equles判断不相等，说明元素不存在，存；
LinkedHashSet
底层数据结构是链表和哈希表。(FIFO插入有序,唯一)
1.由链表保证元素有序
2.由哈希表保证元素唯一
TreeSet
底层数据结构是红黑树。(唯一，有序)
1. 如何保证元素排序的呢?
自然排序
比较器排序
2.如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定
hashMap
HashMap的默认大小是16
结构：1.7 数组+链表 1.8 数组+链表+红黑树
转红黑树的条件：HashMap转红黑树的条件是链表长度大于8且桶的数量大于64
hashMap红黑树的复杂度：红黑树是一种平衡的二叉搜索树，其最坏情况下的时间复杂度为O(log n)。在最坏情况下，所有的元素都会被放置在同一个桶中，形成一个长链表，即HashMap中所有元素的哈希值都相同时，时间复杂度会退化为O(n)，
底层原理：当添加元素到HashMap时，会先通过哈希函数计算出该元素在数组中的位置，然后判断该位置是否已存在其他元素。如果存在，新元素就会以链表的形式添加到这个位置；如果不存在，则直接存储在该位置。1.8后，当一个位置的链表长度超过8时，元素个数超过64,转为红黑树。提高查询效率。
扩容机制：HashMap中的元素数量达到当前容量的一半时，会触发扩容操作。扩容操作会将HashMap的容量扩大为原来的两倍，并将所有元素重新计算哈希值并放置到新的数组中。这个操作相对比较耗时，因此，在创建HashMap时，可以根据预期的元素数量指定一个合适的初始容量，以减少扩容的次数和避免出现过于接近容量上限的情况，从而提高HashMap的性能。
linkList：
其底层结构是由一个双向链表维护的，包含头指针和尾指针。每个节点包含用于存数据的item、指向前一节点的指针prev和指向后一节点的指针next
线程安全的list:
- Vector：Vector是大家熟知的线程安全的List集合，不过它的性能不是最优的，所有的方法都是加了synchronized来同步，从而保证线程安全。
- Collections.SynchronizedList：SynchronizedList是Collections类的静态内部类，它能把所有List接口的实现类转换成线程安全的List，比Vector有更好的扩展性和兼容性。
为什么数组比链表查询速度更快？
数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块 更大的空间，再把数据全部复 制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。
链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度O(1)。但是 正因为存储空间不连续，你无 法根据一个索引算出对应元素的地址，所以不能随机访问；而且由于每个元素必须存储指向前后元素位置的指针，会消耗相对更多的储存空间。
java中数组怎么扩容的？
ArrayList，默认大小为10
- 创建一个新的数组，其长度通常是原有数组长度的两倍（也可以根据需要设定其他倍数）。
- 将原有数组中的元素复制到新数组中。
- 让 ArrayList 引用指向新数组。
标签：HashMap,元素,哈希,链表,理解,线程,数组,集合 From： https://www.cnblogs.com/zuoyi2319516228/p/17889447.html