Java数据结构面试题（一）

一.ArrayList和LinkedList的区别

二.ArrayList和Vector的区别

三.HashMap的底层实现

四.HashMap和ConcurrentHashMap的区别

五.HashMap和HashTable的区别

六.多线程的情况下使用HashMap呢？

七.HashMap的如何扩容呢？

八.哈希冲突

本专栏全是博主自己收集的面试题，仅可参考，不能相信面试官就出这种题目。

一.ArrayList和LinkedList的区别

实现，ArrayList 和 LinkedList 都是 Java 中的 List 接口的实现类。

不同点：

它们的底层实现不同：ArrayList 是基于动态数组的数据结构，而 LinkedList 是基于链表的数据结构。
随机访问性能不同：ArrayList 优于 LinkedList，因为 ArrayList 可以根据下标以 O(1) 时间复杂度对元素进行随机访问。而 LinkedList 的访问时间复杂度为 O(n)，因为它需要遍历整个链表才能找到指定位置的元素。
插入和删除性能不同：LinkedList 优于 ArrayList，因为 LinkedList 的插入和删除操作时间复杂度为 O(1)，而 ArrayList 的时间复杂度为 O(n)。

单独针对ArrayList的解析：

初始化时可以指定初始容量的大小，默认为10，扩容机制：增加当前容量的 50%。

二.ArrayList和Vector的区别

ArrayList 和 Vector 实现了 List 接口，它们都是动态数组的实现，使用方法也是一样，但是也有不同的地方：

线程安全性：Vector 是线程安全的，而 ArrayList 不是。所以在多线程环境下，应该使用 Vector。
性能：由于 Vector 是线程安全的，所以它的性能通常比 ArrayList 差。在单线程环境下，ArrayList 比 Vector 快。
初始容量增长方式：当容量不足时，ArrayList 默认会增加 50% 的容量，而 Vector 会将容量翻倍。这意味着在添加元素时，ArrayList 需要更频繁地进行扩容操作，而 Vector 则更适合于存储大量数据。

三.HashMap的底层实现

在jdk1.7版本之前，HashMap的底层设计通过数组 + 链表实现的，而jdk1.8版本之后，HashMap 底层是通过数组 + 链表或红黑树实现的。

详细解析：在jdk 8 中，当链表达到阈值8时，会自动转化为红黑树！这个优化的目的是为了在哈希冲突较严重时，仍然能够保持较快的查询性能，因为红黑树的查找、插入和删除操作的时间复杂度为 O(log n)，相比于链表的 O(n) 更加高效。

当红黑树的节点小于等于 6 时，为了节省内存空间会将红黑树退化为链表。

四.HashMap和ConcurrentHashMap的区别

HashMap 是 Java 中常用的一种基于哈希表实现的数据结构，用于存储键值对。它提供了快速的插入、删除和查找操作，适用于需要频繁操作的场景。

ConcurrentHashMap 是 Java 中线程安全的哈希表实现，专为高并发场景设计。它提供了比 HashMap 更好的并发性能，同时保持了类似的接口和功能。

两者之间的对比：

线程安全上：HashMap是不安全的，但是 ConcurrentHashMap是安全的。
键值对上：HashMap是允许存在null键和null值的，但 ConcurrentHashMap不允许
性能表现上：在单线程环境当中，HashMap性能高，因为HashMap不需要额外的控制开销，而ConcurrentHashMap 在多线程并发访问时通常表现更好，特别是在读多写少的场景下，由于其分段锁设计能够显著减少线程之间的竞争，提高并发度，从而提升性能。
迭代方面：HashMap 的迭代器是快速失败的（迭代过程中不允许结构发生改变），ConcurrentHashMap 的迭代器是弱一致的（可以发生改变，但是不保证获取最新的修改）
初始化：HashMap 在初始化时可以指定初始容量和负载因子，用于优化性能；ConcurrentHashMap 也可以初始化时指定初始容量和负载因子，但不需要考虑并发情况下的扩容问题，因为它使用了分段锁来管理并发。

扩展问题：ConcurrentHashMap 为什么不能插入null键值对？

解析：从Java8版本之后就可以插入null键了，最开始不能插入的原因是：

如果允许键为 null，ConcurrentHashMap 内部的哈希算法可能会将 null 的哈希值映射到某个有效的 Segment 或桶位上，这样会导致无法确定存储位置，或者在其他操作中造成错误。

如果值为 null，其他线程可能无法准确判断是键不存在还是键对应的值为 null，这会增加实现的复杂性和不确定性。

五.HashMap和HashTable的区别

HashMap 和 Hashtable 都实现了 Map 接口，都是 Java 中用于存储键值对的数据结构，它们的底层数据结构都是数组加链表的形式。但即使如此也存在几点不同：

解析：为什么HashTable不允许存储null键和值，是因为它的key值进行哈希计算，如果为null的话，无法调用该方法，还是会抛出空指针异常，而值为null的话，HashTable源码会主动抛出异常。

线程安全：Hashtable 是线程安全的，而 HashMap 是非线程安全的。
性能：因为 Hashtable 使用了 synchronized 给整个方法添加了锁，所以相比于 HashMap 来说，它的性能不如 HashMap。
存储：HashMap 允许 key 和 value 为 null，而 Hashtable 不允许存储 null 键和 null 值。

HashMap 允许 key 和 value 为 null 的原因是因为在 HashMap 中对 null 值进行了特殊处理，如果为 null 时会把它赋值为 0。

扩展知识：Hashtable 不推荐使用，即使线程安全，也不推荐使用，因为整个方法添加 synchronized 来实现线程安全的，所以它的性能很差。而推荐的是ConcurrentHashMap，性能高。

六.多线程的情况下使用HashMap呢？

HashMap是不安全的，可是有些面试官就是搞事情，说我就要用，你就说怎么搞吧！

在多线程的情况下，使用HashMap的方法：

使用 Collections.synchronizedMap() 包装：

Map<K, V> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

缺点：并发的性能很低

七.HashMap的如何扩容呢？

说起HashMap，我们可以了解一下它的底层原理，由数组+链表组建，而扩容则是扩容数组，当元素个数 > 容量*负载因子时，就会进行扩容，而默认的负载因子：0.75，初始容量可以调节，默认是16.

或许面试官会追问：为什么不是满了之后再扩容呢？

答：哈希表不像其他的数据容器，它的内部存储数据是有不一样的。元素都会根据键对象的HashCode()方法得到，然后进行一系列的运算，确定键值对在数组当中的位置。

追问：为什么负载因子是0.75呢？怎么不能是0.8、0.6呢？

答：0.75是空间利用率和性能的一个平衡点，可以保证大多数情况下较高的查找效率和插入效率，过高会增加哈希冲突发生的概率，过低会造成存储的元素过少。

八.哈希冲突

元素在存储的过程当中，是怎么样的一个过程呢？

第一步：得到键的哈希值hash

第二步：确定存储位置，方法：(n - 1) & hash 其中的n是数组的长度

第三步：插入键值对，如果确定的存储位置为空，则直接存储，若不为空，则进行查找该存储位置下的链表或者红黑树是否有对应的键值，若有，则更新，若无，则添加在末尾！

第四步：当前元素数量达到了负载因子乘以数组容量的阈值，进行扩容操作，扩容包括创建一个更大的数组，并重新计算所有键值对的存储位置，然后将它们移到新数组中。

哈希冲突，为什么会有哈希冲突呢？

原因：不同的键可能有相同的哈希码

解决方法：

链地址法：也就是数组+链表，链表过长转为红黑树
开放地址法：发生哈希冲突时，通过一定的探测方法（线性探测、二次探测、双重哈希等）在哈希表中寻找下一个可用的位置。这种方法的优点是不需要额外的存储空间，适用于元素数量较少的情况。缺点是容易产生聚集现象，即某些桶中的元素过多，而其他桶中的元素很少。
再哈希法（Rehashing）：当发生哈希冲突时，使用另一个哈希函数计算出一个新的哈希值，然后将元素插入到对应的桶中。这种方法的优点是简单易懂，适用于元素数量较少的情况。缺点是需要额外的哈希函数，且当哈希函数不够随机时，容易产生聚集现象。

扩展知识：线性探测VS二次探测

线性探测：发生哈希冲突时，线性探测会在哈希表中寻找下一个可用的位置，具体来说，它会检查哈希表中下一个位置是否为空，如果为空，则将元素插入该位置；如果不为空，则继续检查下一个位置，直到找到一个空闲的位置为止。

二次探测：如果初始位置已被占用，则使用二次探测序列计算下一个位置，通过二次探测序列，然后依次检查哈希表中的每个位置，直到找到一个空闲的位置为止。二次探测序列通常是一系列平方数的序列，例如 (1^2, 2^2, 3^2, \ldots)。二次探测序列：[ h_i = (hash + c1 \cdot i + c2 \cdot i^2) \mod m ]