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 ]