2024年java面试准备--集合篇
集合面试准备
Collection接口是集合类的根接口，Java中没有提供这个接口的直接的实现类。但是却让其被继承产生了两个接口，就是Set和List。Set中不能包含重复的元素。List是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式。
Map是Java.util包中的另一个接口，它和Collection接口没有关系，是相互独立的，但是都属于集合类的一部分。Map包含了key-value对。Map不能包含重复的key，但是可以包含相同的value。
Iterator，所有的集合类，都实现了Iterator接口，这是一个用于遍历集合中元素的接口，主要包含以下三种方法： 1.hasNext()是否还有下一个元素。 2.next()返回下一个元素。 3.remove()删除当前元素。
List
有索引，有序可重复。ArrayList与Vector底层是数组，查询快增删慢。LinkedList底层是双向链表，查询慢增删快。ArrayList，LinkedList都是线程不安全，Vector线程安全。
List遍历
①普通for循环遍历List删除指定元素
for(int i=0; i < list.size(); i++){ if(list.get(i) == 5) list.remove(i); }
② 迭代遍历,用list.remove(i)方法删除元素
Iterator<Integer> it = list.iterator(); while(it.hasNext()){ Integer value = it.next(); if(value == 5){ list.remove(value); } }
③foreach遍历List删除元素
for(Integer i:list){ if(i==3) list.remove(i); }
Set
无索引。无序不重复，Set实质上使用的是Map的Key存储，如果要将自定义的类存储到Set中，需要重写equals和hashCode方法。HashSet底层是通过Hashmap来实现的，HashSet是无序不重复的，且不能排序,集合元素可以是null,但只能放入一个null
LinkedHashSet底层是链表（保证有序）+哈希表（保证集合的唯一性），查询慢增删快，它是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的顺序所以遍历的时候会按照添加时的顺序来访问。
TreeSet底层是红黑树，一般用于排序，可以使用compareTo进行排序方法来比较元素之间大小关系，然后将元素按照升序排列，有序。
Map
Map: Key无序不重复，Value可重复。
HashMap底层是数组+链表，它根据键的HashCode值存储数据,根据键可以直接获取它的值，访问速度很快。所以在Map中插入、删除和定位元素比较适合用hashMap。
LinkedHashMap底层是链表+哈希表，它是HashMap的一个子类，如果需要读取的顺序和插入的相同,可以用LinkedHashMap来实现。
TreeMap底层是红黑树，与TreeSet类似，取出来的是排序后的键值对。但如果是要按自然顺序或自定义顺序遍历键，那么TreeMap会更好，有序。
Collection
List
- Arraylist： Object数组
- Vector： Object数组
- LinkedList： 双向循环链表
Set - HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
- LinkedHashSet（有序）： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
- TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)
Map
- HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是 主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较 大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
JDK1.7 HashMap：
底层是 数组和链表 结合在⼀起使⽤也就是链表散列。如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。扩容翻转时顺序不一致使用头插法会产生死循环，导致cpu100%
JDK1.8 HashMap：
底层数据结构上采用了数组＋链表＋红黑树；当链表⻓度⼤于阈值（默认为 8-泊松分布），数组的⻓度大于 64时，链表将转化为红⿊树，以减少搜索时间。（解决了tomcat臭名昭著的url参数dos攻击问题）
- LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散 列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加 了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的 操作，实现了访问顺序相关逻辑。
- HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突 而存在的
- TreeMap： 红黑树（自平衡的排序二叉树）
List
ArrayList和LinkedList的区别
1.首先，他们的底层数据结构不同，ArrayList底层是基于数组实现的，LinkedList底层是基于链表实现的
2.由于底层数据结构不同，他们所适用的场景也不同，ArrayList更适合查找，LinkedList更适合删除和添加
3.另外ArrayList和LinkedList都实现了List接口，但是LinkedList还额外实现了Deque接口，所以LinkedList还可以当做队列来使用
4.ArratList的底层使用动态数组，默认容量为10，当元素数量到达容量时，生成一个新的数组，大小为前一次的1.5倍，然后将原来的数组copy过来；
Set
HashSet的实现原理？
HashSet 是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，value统一为present，因此 HashSet 的实现比
较简单，相关 HashSet 的操作，基本上都是直接调用底层HashMap 的相关方法来完成，HashSet 不允许重复的值。
List接口和Set接口的区别
List：有序、可重复集合。按照对象插入的顺寻保存数据，允许多个Null元素对象，可以使用iterator迭代器遍历，也可以使用get(int index)方法获取指定下标元素。
Set：无序、不可重复集合只允许有一个Null元素对象，取元素时，只能使用iterator迭代器逐一遍历。
Map : key-value键值对形式的集合，添加或获取元素时，需要通过key来检索到value。
Map
HashMap
hashmap底层实现
HashMap 基于 Hash 算法实现的：
- 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
- 存储时，如果出现hash值相同的key，此时有两种情况。
(1)如果key相同，则覆盖原始值；
(2)如果key不同（出现冲突），则将当前的key-value放入链表中 - 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
- 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
数组加链表（1.8以前)，1.8之后添加了红黑树，基于hash表的map接口实现
阈值（边界值)>8并且桶位数(数组长度)大于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。
HashTable与HashMap的区别
（1）HashTable的每个方法都用synchronized修饰，因此是线程安全的，但同时读写效 率很低
（2）HashTable的Key不允许为null
（3）HashTable只对key进行一次hash，HashMap进行了两次Hash
（4）HashTable底层使用的数组加链表
（5）HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。
线程不安全体现
在HashMap扩容的是时候会调用resize（）方法中的transfer()方法，在这里由于是头插法所以在多线程情况下可能出现循环链表，所以后面的数据定位到这条链表的时候会造成数据丢失。和读取的可能导致死循环。
- 并发修改导致数据不一致
HashMap的数据结构是基于数组和链表实现的。在进行插入或删除操作时，如果不同线程同时修改同一个位置的元素，就会导致数据不一致的情况。具体来说，当两个线程同时进行插入操作时，假设它们都要插入到同一个数组位置，并且该位置没有元素，那么它们都会认为该位置可以插入元素，最终就会导致其中一个线程的元素被覆盖掉。此外，在进行删除操作时，如果两个线程同时删除同一个元素，也会导致数据不一致的情况。
- 并发扩容导致死循环或数据丢失
当HashMap的元素数量达到一定阈值时，它会触发扩容操作，即重新分配更大的数组并将原来的元素重新映射到新的数组上。然而，在进行扩容操作时，如果不加锁或者加锁不正确，就可能导致死循环或者数据丢失的情况。具体来说，当两个线程同时进行扩容操作时，它们可能会同时将某个元素映射到新的数组上，从而导致该元素被覆盖掉。此外，在进行扩容操作时，如果线程不安全地修改了next指针，就可能会导致死循环的情况。
想要线程安全的HashMap怎么办？
（1）使用ConcurrentHashMap
（2）使用HashTable
（3）Collections.synchronizedHashMap()方法
put操作步骤：
1、判断数组是否为空，为空进行初始化;
2、不为空，则计算 key 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;
3、查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
4、存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据；
5、若不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；
6、若不是红黑树，创建普通Node加入链表中；判断链表长度是否大于 8，大于则将链表转换为红黑树；
7、插入完成之后判断当前节点数是否大于阈值，若大于，则扩容为原数组的二倍
2024年java面试准备--集合篇（二）https://developer.aliyun.com/article/1393078
