常见集合面试篇

常见集合面试篇

• LIST
• • 一、底层实现
  • • 1、数据结构-数组
    • • 1.1为什么数组索引从0开始？从1开始不行吗？
      • 1.2操作数组的时间复杂度
      • • 查询
        • 插入和删除
    • 2、源码分析
    • • 2.1成员变量
      • 2.2构造方法
      • 2.3扩容机制
  • 二、面试问题
  • • 1、ArrayList底层实现原理是什么？
    • 2、ArrayList扩容？
    • 3、如何实现数组与List之间的转换？
    • • 数组转集合
      • 集合转数组
    • 4、ArrayList与LinkedList区别？
• HashMap
• • 1、HashMap的实现原理
  • • 1.1散列表（Hash Table）
    • 1.2散列函数和散列冲突
    • • 1.2.1链表法（拉链）
      • 1.2.2链表法优化
    • 1.3 面试官追问：HashMap的jdk1.7和jdk1.8有什么区别
  • 2、 HashMap的put方法的具体流程
  • 3、 HashMap的扩容机制
  • 4、 4.1HashMap的寻址算法
  • • 4.2为何HashMap的数组长度一定是2的次幂？
  • 5、HashMap在1.7情况下的多线程死循环问题
  • 6、HashSet与HashMap的区别

LIST

一、底层实现

1、数据结构-数组

数组（Array）是一种用连续的内存空间存储相同数据类型数据的线性数据结构。

1.1为什么数组索引从0开始？从1开始不行吗？

0 开始寻址公式：a[i]=baseAddress+i*dataTypeSize
1 开始寻址公式：a[i]=baseAddress+（i-1)*dataTypeSize
baseAddress:指的是首地址；
dataTypeSize指的是数据类型字节数，比如int =4个字节。
可以发现，如果从1索引开始cpu就要多执行一次减法操作，如果数据量小可能区别不大，数据量太大则会导致性能下降。

1.2操作数组的时间复杂度

查询

• 随机查询（根据索引查询）
  直接使用上面说的公式即可 时间复杂度：O(1)
• 未知索引查询分两种情况
  未排序：扫描一遍数组即可 时间复杂度：O(n)
  已排序：根据二分查找即可 时间复杂度：O(logn)

插入和删除

数组是一段连续的内存空间，所以性能很低。
最好的情况就是插入尾部 时间复杂度：O(1)
最坏的情况就是插入首部 时间复杂度：O(n)
所以平均情况 时间复杂度：O(n)

2、源码分析

2.1成员变量

2.2构造方法

2.3扩容机制

初始容量：
ArrayList初始容量为0，当第一次添加数据的时候才会初始化容量为10
扩容逻辑：
ArrayList在进行扩容的时候是原来容量的1.5倍，每次扩容都需要拷贝数组
后续添加逻辑：
确保数组已使用长度（size）加1之后足够存下下一个数据。
计算数组的容量，如果当前数组已使用长度+1后的大于当前的数组长度，则调用grow方法扩容（原来的1.5倍）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。返回添加成功布尔值。

二、面试问题

1、ArrayList底层实现原理是什么？

参考以上源码解析

2、ArrayList扩容？

参考以上扩容机制

3、如何实现数组与List之间的转换？

数组转集合

总结：数组转集合可以使用Arrays中的aslist()方法，但是底层就是引用，因此数组后续改变的话，集合也会跟着改变。

集合转数组

总结：集合转数组使用的集合自带的toArray()方法，本质就是数组的拷贝，因此后期改变集合不影响数组。

4、ArrayList与LinkedList区别？

从四个维度来答：

• 底层数据结构
  ArrayList 是动态数组的数据结构实现
  LinkedList 是双向链表的数据结构实现
• 操作数据效率
  ArrayList按照下标查询的时间复杂度O(1)【内存是连续的，根据寻址公式】
  LinkedList不支持下标查询
  查找（未知索引）： ArrayList需要遍历，链表也需要链表，时间复杂度都是O(n)。
  新增和删除
  ArrayList尾部插入和删除，时间复杂度是O(1)；其他部分增删需要挪动数组，时间复杂度是O(n)
  LinkedList头尾节点增删时间复杂度是O(1)，其他都需要遍历链表，时间复杂度是O(n)
• 内存空间占用
  ArrayList底层是数组，内存连续，节省内存。
  LinkedList 是双向链表需要存储数据，和两个指针，更占用内存。
• 线程安全
  ArrayList和LinkedList都不是线程安全的，如果需要保证线程安全，有两种方案：
  1、在方法内使用，局部变量则是线程安全的。每使用一次就会重新创建。
  2、使用线程安全的ArrayList和LinkedList,但是性能会下降。

List<String> s1 = Collections.synchronizedList(new ArrayList<String>());
List<String> s2 = Collections.synchronizedList(new LinkedList<String>());

HashMap

1、HashMap的实现原理

1.1散列表（Hash Table）

散列表(Hash Table)又名哈希表/Hash表，是根据键（Key）直接访问在内存存储位置值（Value）的数据结构，它是由数组演化而来的，利用了数组支持按照下标进行随机访问数据的特性。

1.2散列函数和散列冲突

将键(key)映射为数组下标的函数叫做散列函数。
可以表示为：hashValue =hash(key)
散列函数的基本要求：

• 散列函数计算得到的散列值必须是大于等于0的正整数，因为hashValue需要作为数组的下标。
• 如果key1==key2，那么经过hash后得到的哈希值也必相同即： hash(key1)==hash(key2）
• 如果key1 != key2，那么经过hash后得到的哈希值也必不相同即：hash(key1) != hash(key2)

实际的情况下想找一个散列函数能够做到对于不同的key计算得到的散列值都不同几乎是不可能的，即便像著名的MD5,SHA等哈希算法也无法避免一情况，这就是散列冲突(或者哈希冲突，哈希碰撞，就是指多个key映射到同一个数组下标位置)。
解决方法：

1.2.1链表法（拉链）

在散列表中，数组的每个下标位置我们可以称之为桶（bucket）或者槽
（slot），每个桶(槽)会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。
操作的时间复杂度：
新增： 只需要计算hash值（散列槽的位置），插入链表即可。时间复杂度为O(1)
查询和删除： 我们同样通过散列函数计算出对应的槽，然后遍历链表查找或者删除。
平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)
散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n)

1.2.2链表法优化

将链表法中的链表改造为其他高效的动态数据结构，比如红黑树，查询的时间复杂度是 O(logn）。
将链表法中的链表改造红黑树还有一个非常重要的原因，可以防止DDos攻击

分布式拒绝服务攻击(英文意思是Distributed Denial of Service，简称DDoS）
指处于不同位置的多个攻击者同时向一个或数个目标发动攻击，或者一个攻击者控制了位于不同位置的多台机器并利用这些机器对受害者同时实施攻击。由于攻击的发出点是分布在不同地方的，这类攻击称为分布式拒绝服务攻击，其中的攻击者可以有多个。

面试回答：
HashMap的数据结构： 底层使用hash表数据结构，即数组和链表或红黑树

1. 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。
   a. 如果key相同，则覆盖原始值；
   b. 如果key不同（出现冲突），则将当前的key-value放入链表或红黑树中。
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

1.3 面试官追问：HashMap的jdk1.7和jdk1.8有什么区别

JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时并且数组长度达到64时，将链表转化为红黑树，以减少搜索时间。扩容resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。

2、 HashMap的put方法的具体流程

回答：
第一次添加时，table表（底层的数组）为空会初始化数组长度为默认容量16，然后根据key计算数组下标索引直接插入即可。
之后的添加：先根据key计算数组的索引值，然后判断该索引是否有值，如果为空直接插入即可，否则判断key是否与第一个节点key相同，相同则直接覆盖，如果第一个不相等则需要向后去判断。首先判断是不是红黑树，是则直接按照红黑树的规则添加即可，如果不是则进行链表遍历，遍历key是否存在，存在覆盖，不存在则插入尾部，然后再判断链表长度是否大于8，大于则转换成红黑树。
添加之后：插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold（数组长度*0.75），如果超过，进行扩容。

3、 HashMap的扩容机制

首先是第一次初始化：这个时候容量为0则需要调用resize()方法将数组容量设置为16，并且设置扩容阈值为12（加载因子*容量），然后创建数组即可。
达到阈值触发扩容：当实际存在的键值对数量size达到阈值则将数组容量变为原来两倍，并且新建数组，再去遍历旧数据，首先判断是数组上是否为空，如果为空不管，不为空这里分为三种情况，如果数组索引位置上元素指向为空（没有指向红黑树和链表），则直接通过e.hash & (newCap - 1);计算出新数组中的索引位置并且插入，如果指向为红黑树，则调用split()方法添加红黑树，如果指向的是链表，则需要判断e.hash & oldCap==0成立则插入的索引值和老数组一样，否则插入索引值为老数组容量+原索引值。

4、 4.1HashMap的寻址算法

首先获取key的hashCode值，然后右移16位 异或运算 原来的hashCode值，主要作用就是使原来的hash值更加均匀，减少hash冲突

寻找算法就是将数组长度减一然后和hash值进行&运算，其等价于hash对数组长度取余。（目的就是提高性能，%周期比&长，&效率高导致性能好）
注意：HashMap的数组长度（上面的n）一定是2的次幂。

4.2为何HashMap的数组长度一定是2的次幂？

• 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
• 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap。（前面的扩容机制）

5、HashMap在1.7情况下的多线程死循环问题

在jdk1.7的hashmap中在数组进行扩容的时候，因为链表是头插法，在进行数据迁移的过程中，有可能导致死循环。
比如说，现在有两个线程
线程一：读取到当前的hashmap数据，数据中一个链表，在准备扩容时，线程二介入。
线程二：也读取hashmap，直接进行扩容。因为是头插法，链表的顺序会进行颠倒过来。比如原来的顺序是AB，扩容后的顺序是BA，线程二执行结束。
线程一：继续执行的时候就会出现死循环的问题。
线程一先将A移入新的链表，再将B插入到链头，由于另外一个线程的原因，B的next指向了A，所以B->A->B,形成循环。遍历的时候就会发生死循环。
当然，JDK 8 将扩容算法做了调整，不再将元素加入链表头（而是保持与扩容前一样的顺序），尾插法，就避免了jdk7中死循环的问题。

6、HashSet与HashMap的区别

(1)HashSet实现了Set接口, 仅存储对象; HashMap实现了 Map接口, 存储的是键值对。
(2)HashSet底层其实是用HashMap实现存储的, HashSet封装了一系列HashMap的方法.。依靠HashMap来存储元素值,(利用hashMap的key键进行存储), 而value值默认为Object对象。 所以HashSet也不允许出现重复值, 判断标准和HashMap判断标准相同, 两个元素的hashCode相等并且通过equals()方法返回true。