2020年的面试整理，请指教，关于（1）集合的整理

约定不等于承诺〃 2023-07-17 12:38 2阅读 0赞

好记性不如烂笔头，面对面试，该复习还是得复习，要不然被摁在地上摩擦，摩擦，在摩擦.......

直接开门见山，希望赶紧面完，还得回家看我家的小可爱，么么哒

**一、关于集合的整理**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhb3l1YW5ibw_size_16_color_FFFFFF_t_70][]

在下就不一一整理了，主要整理下面试中常问的：

（1）ArrayList

底层是个动态数组，每次创建一个ArrayList实例时会分配一个初始化容量，以add方法为例，如果没有指定容量，当执行add方法时，会先判断当前数组是不是为空，如果为空则给保存数组的对象分配一个初始化容量，默认为10，当添加大容量时，会先增加数组的大小，也就是我们常说的扩容，默认扩容一半，调用grow（），Arrays.copyof()等方法进行处理，他是线程不安全，允许元素为null当然，数组是有下标/索引的，查询时可以根据下标/索引提升查询效率，插入或者删除时会导致后面的元素重新调整索引位置，产生一定的性能消耗。

（2）LinkedList

底层是个双向链表的数据结构，添加删除都是靠移动指针来完成的，所以性能较ArrayList要高出好多，他是一个双向链表，没有初始化大小，也没有扩容，但是在查询的时候，需要根据二分法来看index和size的距离来判断是从头结点正序查还是从尾节点倒序查，从源代码中可以看出，判断给定的索引值，若索引值大于整个链表长度的一半，则从后往前遍历找，若索引值小于整个链表的长度的一半，则从前往后遍历找。这样就可以保证，不管链表长度有多大，搜索的时候最多只搜索链表长度的一半就可以找到，相对来说大大提升了效率。总结来说，LinkedList 插入，删除都是移动指针效率很高。查找需要进行遍历查询，效率较低。（3）ArrayList和linkedlist的区别

*  **1. 是否保证线程安全：** ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
 *  **2. 底层数据结构：** Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向链表数据结构
 *  **3. 插入和删除是否受元素位置的影响：** ① **ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。** 比如：执行`add(E e)`方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（`add(int index, E element)`）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② **LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。**
 *  **4. 是否支持快速随机访问：** LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于`get(int index)`方法)。
 *  **5. 内存空间占用：** ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）

（4）hashmap底层原理

我们主要是通过put（）和get（）方法存储和获取对象，当键值传递给put时，他会调用键对象的hashcode（）方法计算出hashcode值，然后找到bucket位置来存储值对象，当获取时，会通过键对象的equals方法找到正确的键值对，然后返回对象，他的底层数据结构是数组+链表+红黑树，红黑树就是一个查找树，可以提供查询效率，数组则是hashmap 的主体，也就是我们常说的entry数组，该数组是hashmap的基本组成单元，每个数组存储一个key-value键值对，链表则是为了解决hash冲突，所谓hash冲突就是当我们对某个元素进行hash运算时，得到一个存储地址，然后在存值过程中发现该位置已被其他元素占用，这就是哈希冲突或者哈希碰撞，当发生哈希冲突并且实际存储键值对的size大于阈值的时候，需要进行扩容resize操作，扩容时，需要创建一个新的数组，然后将之前的entry数组全部迁移过去，扩容原来的2倍，扩容是个拷贝的过程，相对来说比较消耗资源，如果定位到数组不含列表，也就是entry指向null，那么对于添加查找等只需要一次寻址即可，如果定位到数组包含链表，对于添加操作，则需要遍历链表，存在就覆盖，否则新增，对于查找来说，仍需遍历链表，然后通过key对象的equals方法逐一对比查找，所以，处于性能考虑，hashmap中出现链表越少越好。hashmap允许键值为空，不会抛出空指针异常，将元素添加到table\[0\]的位置，因为hashmap不支持线程同步，费线程安全，如果一个时刻有多个线程同时写hashmap，可能会导致线程不安全，如需同步，可以使用collections和SynchronizedMap使hashmap具有同步能力，或者也可使用concurrentHashMap。

（5）hashtable

可以等同hashmap的实现，他是通过synchronized同步get，put等方法，并且key不允许为null保证线程安全。

（6）hashset

无序，不重复，底层使用hashmap的实现不重复，使用map键存储保证key不重复，value只是一个虚拟值。

（6）treemap

可排序键值映射集合，对key集合进行有序遍历，使用迭代器Iterator遍历

（7）concurrentHashMap

concurrentHashMap可以支持并发读写功能，首先他不允许key，value为null，否则抛出空指针异常，底层还是使用数组链表红黑树的方式实现，在jdk1.8引入CAS和synchronized一起实现线程安全，1.8之前采用设置并发度实现，在源码中可以看出，他是多个segment\[\]实现，每个并发度默认为16，也可以在构造 函数中设置，在程序运行时同时更新concurrentHashMap，并且不产生锁竞争，整个过程就是获取segment锁，在申请锁之前，put方法会根据trylock的方式尝试获得锁，整个过程会对hashcode的链表进行遍历，如果找不到与key相同的hashentry节点，会提前创建一个hashentry，当trylock一直无法获取锁，则会通过lock申请锁，但是，如果并发度设置小，会带来严重的锁竞争问题，如果设置小了，或导致segment扩散，导致CPU命中率下降，程序性能下降。1.8引入CAS算法，同时增加一些辅助类如treebin，travesrserde 等对象的内部类，如在中添加过程中，首先会判断保存键值对的数组是不是第一次添加元素，如果是则进行初始化操作，通过计算hash值来确定存储位置，保证数组不越界，如果没有初始化，则取出该节点，判断这个节点有没有元素，没有则尝试通过CAS方式尝试添加，像代码中的U对象，如u.cmpareAndSwapObject，直接操作内存来保证线程安全，是一种硬件的安全机制，这个时候没有加锁，如果该节点有值，则需要判断是否需要扩容，复制元素到新数组，也有就是该节点不为空也不需要扩容，则通过synchronized来加锁，进行添加，先判断这个节点时存放链表还是树，是链表，则遍历链表，用key和要存放的key比较，一样就替换，否则添加到链表末尾，如果是树，则调用putTreeVal添加，再添加完成之后，判断存储之前该节点的节点数，超过8就调用treeifBin来尝试将链表转为树，否则数组扩容，对于插叙就方便多了，如果key,value 为空，就抛空指针异常，否则根据key遍历节点返回value。

以上就是个人对集合方面的整理，还望大家谢指点指点......

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhb3l1YW5ibw_size_16_color_FFFFFF_t_70]: /images/20230528/f55ed0caa0a24f7fab335a0053ab4703.png