一、ArrayList，LinkedList，Vector的相同点与区别
Java集合框架提供多种数据结构，其中ArrayList、LinkedList和Vector是常用列表实现。它们具有共同特性，如实现List接口、有序性和可动态调整大小，但也存在底层数据结构、线程安全性和性能等方面的区别。选择哪种集合取决于具体使用场景。除这三种外，Java还提供了其他集合类，如HashSet、TreeSet和HashMap等
Java中的集合（Collection）框架提供了多种数据结构，用于存储和操作对象集合。其中，ArrayList、LinkedList和Vector是三种常用的列表（List）实现。这些类都实现了List接口，因此它们具有一些共同的特性，但也有一些重要的区别。
相同点：
- 实现List接口：ArrayList、LinkedList和Vector都实现了Java的List接口，这意味着它们具有相同的基本操作，如添加（add）、删除（remove）、获取（get）元素等。
- 有序性：这三种集合都是有序的，即元素的插入顺序与迭代顺序相同。
- 可包含重复元素：ArrayList、LinkedList和Vector都允许存储重复的元素。
- 可动态调整大小：这些集合都可以动态地增长和缩小，以适应不同的数据量。
区别： - 底层数据结构：
ArrayList：底层基于动态数组实现，支持快速的随机访问（get和set操作），但在插入和删除元素时可能涉及到数组元素的移动，因此效率相对较低。
LinkedList：底层基于双向链表实现，插入和删除元素时只需要改变相邻节点的引用，因此效率较高。但随机访问元素时需要遍历链表，效率较低。
Vector：与ArrayList类似，底层也是基于动态数组实现，但Vector是线程安全的，因此在多线程环境下性能更好。然而，由于线程同步的开销，Vector在单线程环境下的性能通常不如ArrayList。 - 线程安全性：
ArrayList：不是线程安全的，如果在多线程环境下使用，需要外部同步。
LinkedList：同样不是线程安全的。
Vector：是线程安全的，因为它在方法调用上加了同步锁，但这也导致了性能上的损失 - 性能：
由于底层数据结构和线程安全性的差异，这三种集合在性能上有所不同。一般来说，ArrayList在随机访问和遍历方面表现较好，LinkedList在插入和删除方面表现较好，而Vector由于线程同步的开销，性能通常不如ArrayList。 - 扩容策略：
ArrayList：在需要扩容时，默认将容量增加到原来的1.5倍，然后再进行必要的截断。
LinkedList：由于基于链表实现，不需要扩容。
Vector：在需要扩容时，默认将容量增加到原来的2倍。此外，Vector还提供了一个增长因子（growth factor）参数，可以在创建时指定。
综上所述，选择哪种集合取决于具体的使用场景。如果需要频繁的随机访问和遍历操作，且不需要线程安全，那么ArrayList可能是一个不错的选择。
如果需要在列表中间频繁地插入和删除元素，且对性能要求较高，那么LinkedList可能更适合。而如果需要线程安全的列表，并且不介意性能上的一些损失，那么Vector是一个合适的选择。
总结
Java的集合框架提供了多种实现方式，每种都有其独特的优点和适用场景。了解这些集合的底层数据结构、线程安全性、性能和扩容策略，可以帮助我们更好地选择适合的集合来优化我们的代码。在实际编程中，我们应该根据具体的需求和场景，权衡各种因素，选择最合适的集合来实现我们的功能。
除了ArrayList、LinkedList和Vector之外，Java的集合框架还提供了其他许多有用的集合类，如HashSet、TreeSet、HashMap等。这些集合类也有各自的特性和适用场景。对于更复杂的数据结构和算法问题，我们还可以考虑使用Java 8引入的Stream API来进行更高效的数据处理。随着技术的不断发展，我们也需要不断学习和掌握新的工具和技术，以更好地应对各种编程挑战。
二、HashSet、LinkedHashSet、TreeSet区别
如果你需要一个访问快速的Set，你应该使用HashSet；当你需要一个排序的Set，你应该使用TreeSet；当你需要记录下插入时的顺序时，你应该使用LinedHashSet。
HashSet是采用hash表来实现的。其中的元素没有按顺序排列，add()、remove()以及contains()等方法都是复杂度为O(1)的方法。
TreeSet是采用树结构实现(红黑树算法)。元素是按顺序进行排列，但是add()、remove()以及contains()等方法都是复杂度为O(log (n))的方法。
它还提供了一些方法来处理排序的set，如first(), last(), headSet(), tailSet()等等。
LinkedHashSet介于HashSet和TreeSet之间。它也是一个hash表，但是同时维护了一个双链表来记录插入的顺序。基本方法的复杂度为O(1)。
HashSet
不能保证元素的排列顺序，顺序有可能发生变化
不是同步的，非线程安全
集合元素可以是null，但只能放入一个null
当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。
简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等
注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作
equals比较标准的属性，都应该用来计算hashCode的值。
LinkedHashSet
nkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。
LinkedHashSet中不能有相同元素，可以有一个Null元素，元素严格按照放入的顺序排列。
LinkedHashSet如何保证有序和唯一性？
底层数据结构由哈希表和链表组成。
链表保证了元素的有序即存储和取出一致，哈希表保证了元素的唯一性。
添加、删除操作时间复杂度都是O(1)。
非线程安全
TreeSet
TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。
TreeSet支持两种排序方式，自然排序 和定制排序，其中自然排序为默认的排序方式。
向TreeSet中加入的应该是同一个类的对象。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0
自然排序
自然排序使用要排序元素的CompareTo（Object obj）方法来比较元素之间大小关系，然后将元素按照升序排列。
定制排序
自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现 int compare(T o1,T o2)方法
1.TreeSet是中不能有相同元素，不可以有Null元素，根据元素的自然顺序进行排序。
2.TreeSet如何保证元素的排序和唯一性？
底层的数据结构是红黑树(一种自平衡二叉查找树)
3.添加、删除操作时间复杂度都是O(log(n))
4.非线程安全
通过以上特点可以分析出，三者都保证了元素的唯一性，如果无排序要求可以选用HashSet；
如果想取出元素的顺序和放入元素的顺序相同，那么可以选用LinkedHashSet。如果想插入、删除立即排序或者按照一定规则排序可以选用TreeSet。
三、HashMap、HashTable、ConcurrentHashMap
相同点
三者都是存储键值对的Key-Value
key会被映射到数组索引, Entry对象则是数组中对应的值。
Key通过Hash算法得到哈希码（HashCode）, 通过哈希码与数组中的索引对应。
因此所有的键值对Hash表都是无序储存的。
键值对的查找过程： （hashCode（）计算出索引，通过键的equals方法找到对应的键值对， 返回值对象）先对键做一个hashCode()的计算来得到它在bucket数组（这里的计算方法略有区别）中的位置来存储Entry对象。当获取对象时，通过get获取到bucket的位置，再通过键对象的equals()方法找到正确的键值对，然后在返回值对象。
负载因子为什么是0.75而不是1或者0.5?
因为如果是0.5的话, 散列表会比较稀疏, 更大程度上避免了哈希碰撞的可能性, 索引效率高, 此时会对空间造成浪费
如果是1的话, 散列表会变得密集, 空间利用率提高了, 但是哈希碰撞的可能性变大了, 链表和红黑树会变得复杂, 索引效率会变低
经检测, 0.7-0.75的索引效率是最高的
HashTable
采用数组和链表， 1.8依然是数组和链表
线程安全的：使用synchronized来保证线程安全， 但是读写的时候会锁住整张表
扩容机制： HashTable的初始大小是11，扩容通过rehash()来实现, 当HashTable的数组元素个数达到临界值的时候, 就会调用rehash来进行扩容, 扩容后的大小是2oldSize + 1, 临界值就是数组大小乘以负载子(loacFactor) , 通常负载因子默认为0.75。因此数组元素个数达到数组大小的0.75倍时， 就会进行扩容。
计算index方法：（取模方法） index = (hash & 0x7FFFFFFF) % tab.length，采用取模方法，减少哈希碰撞， 使数组分布更均匀， 但是效率比HashMap的位运算低。
链表依然采用头插法，而没有像HashMap在jdk1.8中为了避免并发情况下扩容死锁改为尾插法，因为头插法的效率比尾插法更高，同时HashTable是线程安全的, 并发下不会出现扩容死锁的情况。
HashMap
线程不安全的
扩容机制：初始容量默认16， 元素个数达到临界值后扩容, 新的容量为 2oldSize, 大小一定为2的n次幂 , 临界值依然是数组容量 * loadFactor(负载因子)
扩容resize():
1.初始化数组table
2.当数组table的size达到阙值时即++size > load factor * capacity 时，也是在putVal函数中
具体实现
1.通过判断旧数组的容量是否大于0来判断数组是否初始化过
否：进行初始化
判断是否调用无参构造器，
是:使用默认的大小和阙值
否:使用构造函数中初始化的容量，当然这个容量是经过tableSizefor计算后的2的次幂数
是，进行扩容，扩容成两倍(小于最大值的情况下)，之后在进行将元素重新进行与运算复制到新的散列表中
put的过程
通过hash() 计算出键的hashcode， 再通过indexFor() 方法计算出对应的索引
如果散列表为空, 调用resize()初始化散列表
添加元素到散列表中
如果没有发生hash碰撞, 直接添加到散列表中
如果发生碰撞
无论是红黑树还是链表, 如果equals相同, 则替换旧的键值对
equals不同
链表, 循环遍历整个链表, 知道链表的某个节点为空(jdk1.8尾插法, 但是在jdk1.7采用的是头插法会引起并发死锁), 查看链表长度是否达到8以及容量是否大于64, 如果满足条件, 将链表转化成红黑树
红黑树插入方法
如果元素个数大于临界值(数组容量*loadFactor), 则通过resize()进行扩容
为什么扩容必须是2的幂
为了数据的均匀分布，减少哈希碰撞。因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。
输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字
计算index方法：index = hash & (tab.length – 1)
ConcurrentHashMap
线程安全的, jdk1.7利用分段锁来提高并发程度, jdk1.8采用CAS和synchronized 来保证并发线程安全
如何保证线程安全的,
jdk1.7保证线程安全: 通过把整个Map分为N个Segment，可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。(因为Segment实现了ReentrantLock, 读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值。)
jdk1.8保证线程安全的方式:
储存Map数据的数组时被volatile关键字修饰，一旦被修改，其他线程就可见修改。因为是数组存储，所以只有改变数组内存值是才会触发volatile的可见性
进行put操作的时候通过hashcode计算出的索引位置没有哈希冲突, 采用自旋+CAS操作。如果还在进行扩容操作就先进行扩容。如果存在hash冲突， 就会使用synchronized 给首节点进行加锁， 如果是链表结构采用尾插法插入尾端， 如果是红黑树按照红黑树的结构进行插入。如果hash冲突形成链表长度超过8， 而且数组长度超过64，就会将链表转化成红黑树， 如果只是链表长度超过8， 数组长度没有超过64，就会进行扩容操作。如果添加成功就调用addCount()方法统计size, 来检查是否需要扩容
一句话总结: 存储Map的数组被volatile关键字修饰, 一旦修改, 其他线程就可见修改, 方便进行CAS操作。读操作不加锁， 关键是写操作，如果索引位置没有哈希冲突， 采用自旋+CAS操作进行写操作， 如果有哈希冲突， 通过synchronized给首节点进行加锁， 后面的操作和HashMap类似（链表和红黑树以及扩容判断）
ConcurrentHashMap的键和值不能为空
原因: 当你通过get(k)获取对应的value时，如果获取到的是null时，你无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。HashMap是非并发的，可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains(key)和m.get(key)的时候，m可能已经不同了。
扩容机制:
jdk1.7的扩容机制:
进行写操作和扩容操作时候, 会对Segment进行加锁, 但是只会影响这一个Segment, 不同的Segment依然可以进行并发操作, 提高了并发效率, 解决了线程安全问题(一个Segment相当于一个HashMap)
jdk1.8的扩容机制:
sizeCtl 和 ForwordNode 在扩容中起关键作用
sizeCtl ：默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。
-1 代表table正在初始化
-N 表示有N-1个线程正在进行扩容操作
其余情况：
如果table未初始化，表示table需要初始化的大小。
如果table初始化完成，表示table的容量，默认是table大小的0.75倍
当数组元素个数超过临界值的时候, 就会进行扩容操作, 同时将sizeCtl的值修改。扩大后的长度和HashMap是一样的， 依然是原数组容量的2倍。扩容操作开始之后， 会将旧数组上的值迁移到新数组中，迁移完成的节点和空节点会被设置成ForwordNode节点, 其他线程进行读写操作时, 若节点是ForwordNode节点 , 也会加入到扩容操作。如果节点是正常节点， 读操作（get方法）依然和之前一样