Java集合面试题——哈希！

1.说说 Java 中 HashMap 的原理？

①　哈希函数：当我们向HashMap中存入一个键值对时，首先会通过哈希函数将键映射到一个索引位置上。
②　数组存储：HashMap内部使用一个数组来存储键值对。在对应索引位置上，将键值对存储在数组中。
③　冲突处理：由于哈希函数的结果可能会出现冲突，即多个键值对映射到了同一个索引位置上。为了解决冲突问题，HashMap使用了链表或红黑树的数据结构来存储多个键值对。链表：当冲突发生时，新的键值对会被添加到链表的末尾。这样，从数组中的索引位置开始，通过遍历链表，即可找到对应的键值对。红黑树：为了提高查找效率，当链表长度超过一定阈值（默认为8）时，链表会转化为红黑树存储方式。当我们需要删除一个键值对时，也是通过查找找到对应的键值对，然后将其从链表或红黑树中删除。

2.使用 HashMap 时，有哪些提升性能的技巧？

①　合理设置初始容量：如果知道大概会存储的数据量，可以在创建HashMap时指定初始容量，减少扩容次数，提高性能1。
②　选择合适的负载因子：负载因子是HashMap决定扩容的重要参数。适当提高负载因子可以减少扩容次数，但也可能增加哈希冲突的概率1。
③　减少哈希冲突：通过重写键的hashCode()和equals()方法，让键的哈希值分布更均匀，可以提高HashMap的查询效率1。
④　避免频繁的插入和删除操作：频繁操作会导致HashMap不断调整内部结构，影响性能。尽量批量进行插入和删除操作1。
⑤　使用合适的键类型：选择合适的键类型很重要。如果键是自定义类，要确保其hashCode()和equals()方法正确实现。尽量使用不可变类作为键，避免键的值变化影响查询结果1。
⑥　及时清理不再使用的HashMap：当HashMap不再使用时，及时将其设置为null，以便垃圾回收器回收内存，避免内存泄漏1。
⑦　避免在多线程环境下使用HashMap：HashMap不是线程安全的，在多线程环境下可能出现数据不一致问题。可以使用ConcurrentHashMap替代1。
⑧　善用JDK的工具类：JDK提供了一些工具类可以帮助优化HashMap的使用1。
⑨　监控和调优：通过监控工具观察HashMap的使用情况，根据监控结果调整参数，优化性能1。
⑩　
⑪　了解底层实现原理：了解HashMap的底层实现原理有助于更好地使用它1。
⑫　避免使用可变对象作为key：否则hashCode()可能变化，导致数据丢失或找不到2。
⑬　对于可能重复的字符串：可以考虑使用Objects.hash()方法优化哈希计算2。
⑭　以上就是使用HashMap时提升性能的一些技巧。需要注意的是，这些技巧并不是孤立的，它们之间可能存在相互影响。因此，在实际应用中，需要根据具体情况综合考虑，并通过测试来验证优化效果。

3.什么是 Hash 碰撞？怎么解决哈希碰撞？

①　链地址法(Chaining)：每个哈希表的槽位不直接存放单个元素，而是存放一个链表（或其他数据结构，如平衡树），所有映射到同一槽位的元素都插入该链表中。在查询时，只需遍历该链表来查找目标元素。
②　开放地址法(OpenAddressing)：当发生碰撞时，不在原位置存放冲突数据，而是在哈希表中寻找下一个空槽。常见策略包括线性探测、二次探测和双重散列。
③　扩容+再哈希操作：扩容时会增加哈希表的槽位数量，从而降低每个槽位上的平均负载。再哈希之后，原有键在旧哈希表中的位置可能不再适用于新表。这样可以更均匀地分布数据，降低碰撞的概率。
④　其他高级方法：如布谷鸟哈希和跳跃哈希等，通过设计特殊的存储和探测机制来进一步优化冲突解决和查询效率。

4.Java 的 CopyOnWriteArrayList 和 Collections.synchronizedList 有什么区别？分别有什么优缺点？

①　CopyOnWriteArrayList和Collections.synchronizedList是Java中两种实现线程安全列表的方式，它们各有特点和适用场景。以下是它们的区别及各自的优缺点31：
②　线程安全的实现方式
CopyOnWriteArrayList：在进行修改操作时，会拷贝一个新的数组来存放新的数据，这样读写操作互不影响，从而避免了线程安全问题。
Collections.synchronizedList：通过对部分操作加上synchronized关键字来保证线程安全，但其iterator()操作并不是线程安全的。
③　性能表现
CopyOnWriteArrayList：写操作性能较差，因为每次写操作都会进行数组复制；但读操作性能较好，不需要等待写操作完成。
Collections.synchronizedList：写操作性能在多线程情况下比CopyOnWriteArrayList好；读操作性能不如CopyOnWriteArrayList，因为采用了synchronized关键字。
④　数据一致性
CopyOnWriteArrayList：只能保证最终一致性，无法保证数据的实时一致。
Collections.synchronizedList：读写操作的数据是一致的。
⑤　适用场景
CopyOnWriteArrayList：适用于读多写少的场景，如白名单、黑名单、商品类目的访问和更新场景。
Collections.synchronizedList：适用于读写操作较为均衡的场景。
综上所述，CopyOnWriteArrayList和Collections.synchronizedList在实现线程安全的方式、性能表现、数据一致性和适用场景上都有所不同。开发者应根据具体的应用场景选择合适的实现类。

5.Java 中有哪些集合类？请简单介绍

在Java编程语言中，集合类用于存储和操作一组对象，提供更高级别的数据结构，如列表、集（Set）、映射（Map）等。以下是一些常用的Java集合类的简单介绍：

6.数组和链表在 Java 中的区别是什么？

Java数组和链表的主要区别在于它们的内存分配、存取方式、存储位置、存储空间、按序号查找时的时间复杂度、按值查找时的时间复杂度、插入和删除时的效率以及空间分配方面。具体如下：
①　内存分配：数组从栈中分配空间，对于程序员方便快速，但自由度小。链表从堆中分配空间，自由度大但申请管理比较麻烦。
②　存取方式：数组可以顺序存取或者随机存取，而链表只能顺序存取。
③　存储位置：数组逻辑上相邻的元素在物理存储位置上也相邻，而链表不一定。
④　存储空间：链表由于带有指针域，存储密度不如数组大。
⑤　按序号查找时的时间复杂度：数组可以随机访问，时间复杂度为O(1)，而链表不支持随机访问，平均需要O(n)。
⑥　按值查找时的时间复杂度：若数组无序，数组和链表时间复杂度均为O(1)，但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)。
⑦　插入和删除时的效率：数组平均需要移动n/2个元素，而链表只需修改指针即可。
⑧　空间分配方面：数组在静态存储分配情形下，存储元素数量受限制，动态存储分配情形下，虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且如果内存中没有更大块连续存储空间将导致分配失败。
综上所述，数组和链表各有优劣，适用于不同的场景。如果应用需要快速访问数据，并且很少插入和删除元素，那么数组是更好的选择。相反，如果应用需要经常插入和删除元素，那么链表更适合。

7.Java 中的 List 接口有哪些实现类？

List接口是继承自Collection的子接口，允许使用重复元素，可以通过索引来进行元素的获取或设置，也可以通过索引来进行元素的插入和删除等操作。List接口的主要实现类有以下几种：

ArrayList：基于动态数组实现，提供快速的随机访问，但在中间插入或删除元素时可能较慢。适用于需要频繁读取数据、较少进行中间插入和删除的场景1。
LinkedList：基于双向链表实现，支持快速的插入和删除操作，尤其是首尾位置的操作。随机访问元素的时间复杂度为O(n)。适用于需要频繁插入和删除元素的场景。
Vector：也是基于动态数组实现，但它是线程安全的。所有操作都是同步的，因此线程安全，但性能相较于ArrayList稍慢。在现代开发中不常用，通常推荐使用ArrayList或者Collections.synchronizedList()来代替1。
Stack：是Vector的子类，代表了一个后进先出（LIFO）的栈结构。提供了标准的栈操作方法如push()、pop()、peek()等。通常推荐使用Deque接口的实现类如ArrayDeque作为栈来代替Stack类。
CopyOnWriteArrayList：是List接口的线程安全实现，基于写时复制机制。适用于读操作远多于写操作的场景.

8.Java 中 ArrayList 和 LinkedList 有什么区别？

ArrayList是基于动态数组的数据结构，而LinkedList则是基于链表的数据结构。对于随机访问（如get和set操作），ArrayList的性能优于LinkedList，因为ArrayList可以根据下标以O(1)时间复杂度对元素进行随机访问，而LinkedList的每一个元素都依靠地址指针和它后一个元素连接在一起，在这种情况下，查找某个元素的时间复杂度是O(n)。对于新增和删除操作（如add和remove），LinkedList的性能优于ArrayList，因为当元素被添加到LinkedList任意位置的时候，不需要像ArrayList那样重新计算大小或者是更新索引。

9.Java ArrayList 的扩容机制是什么？

ArrayList的扩容机制是在添加元素时判断当前数组大小是否已经满了，如果已经满了，则创建一个新的更大的数组，并将原来的元素全部复制到新的数组中。
以下是关于ArrayList扩容机制的详细信息：
①　初始容量：当创建一个ArrayList对象时，它会分配一定的初始容量，默认情况下，这个初始容量通常是10。这样做的目的是为了节省内存，因为并不是所有的ArrayList都需要大量的空间。
②　容量增长：当ArrayList中的元素数量达到当前容量时，ArrayList会自动增加其容量。在Java中，它以当前容量的一定增量进行扩容，默认情况下增量为当前容量的一半。
③　扩容操作：当需要扩容时，ArrayList会创建一个更大的内部数组，并将所有的元素从旧数组复制到新数组中。这涉及到创建新数组、复制元素以及销毁旧数组的操作。由于这些操作的开销较大，频繁的扩容可能会影响性能。
④　扩容规则：ArrayList的扩容规则是将其容量增加为原来容量的1.5倍。这是通过将旧容量右移1位（相当于除以2），然后加上旧容量来实现的。例如，如果原始容量是10，那么第一次扩容后的容量将是15（10右移1位得到5，再加上10）。
⑤　特殊情况：在某些情况下，例如使用addAll()方法时，ArrayList的扩容机制可能会有所不同。例如，如果当前ArrayList中有10个元素，而addAll()方法需要添加6个元素，当ArrayList触发扩容后的新容量应该为15，而旧容量加上需要添加的元素容量为16，从中取一个较大值为16，所以新容量应该为16。
⑥　手动设置初始容量：为了避免频繁的扩容操作，可以在创建ArrayList时手动设置足够的初始容量。这样可以减少扩容的次数，从而提高性能。

10.Java 中的 HashMap 和 Hashtable 有什么区别？

Java中的Hashtable和HashMap是两种常用的实现Map接口的数据结构，它们在设计和实现上有显著的区别：
①　线程安全性：Hashtable是线程安全的，而HashMap不是。这意味着在多线程环境中，Hashtable可以直接使用，而HashMap则需要额外的同步机制。
②　性能：由于Hashtable是线程安全的，它在单线程环境下比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
③　null值支持：HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。
④　继承的父类不同：HashMap是继承自AbstractMap类，而HashTable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable(可复制)、Serializable(可序列化)这三个接口。
⑤　初始容量和扩容方式：HashTable中hash数组默认大小是11，增加的方式是old*2+1。而HashMap为16，扩容时，将容量变为原来的2倍。
综上所述，在选择使用Hashtable还是HashMap时，需要根据具体的应用场景来决定。如果需要线程安全的集合，并且性能不是首要考虑因素，那么可以选择Hashtable。如果只需要单线程环境下的高性能集合，或者需要支持null键或值的集合，那么应该选择HashMap。

11..ConcurrentHashMap 和 Hashtable 的区别是什么？

①　线程安全性：Hashtable是线程安全的，而ConcurrentHashMap在Java 5中引入，是为了提供更高的并发性能。ConcurrentHashMap通过细粒度的锁机制，允许多个线程同时访问不同的桶（bucket），从而提高了并发性。
②　性能：由于Hashtable在多线程环境下需要锁住整个结构，所以在高并发情况下性能较差。而ConcurrentHashMap通过分段锁技术，将Hash表分为多个桶，默认是16个，每个桶都可以被看作是一个独立的Hashtable，大部分操作都没有用到锁，而对应的put、remove等操作也只需要锁住当前线程需要用到的桶，而不需要锁住整个数据。
③　同步：Hashtable的所有方法都是同步的，这意味着在任何时候只有一个线程可以访问它。而ConcurrentHashMap提供了更低级别的同步，例如，它使用了“锁分离”的技术，使得多个修改操作可以并发进行。
④　null键和值：Hashtable不允许null键和null值，而HashMap（与ConcurrentHashMap相似）可以接受null键和null值。
⑤　迭代器：Hashtable的enumerator迭代器不是fail-fast的，而HashMap的迭代器是fail-fast的。这意味着当有其他线程改变了HashMap的结构（增加或移除元素）时，将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出此异常。
综上所述，如果你的应用场景需要高度的并发性能，并且你使用的是Java 5或更高版本，那么ConcurrentHashMap通常是更好的选择。然而，如果你在一个多线程环境中需要一个简单的、线程安全的映射接口，并且不需要复杂的并发控制，那么Hashtable可能更适合你的需求。

12.Java 中的 HashSet 和 HashMap 有什么区别？

①　实现的接口不同：HashMap实现了Map接口，而HashSet实现了Set接口。
②　存储内容不同：HashMap用于存储键值对，其中键是唯一的，而HashSet用于存储对象，它不允许有重复的元素。
③　添加元素的方法不同：在HashMap中，使用put()方法将元素加入到map中；在HashSet中，则使用add()方法将元素放入set中。
④　计算hashCode的方式不同：HashMap是通过Key来计算hashCode值，而HashSet是通过成员对象来计算hashcode值。由于两个对象的hashcode可能相同，所以需要使用equals()方法来判断对象的相等性。
⑤　效率方面的差异：一般来说，HashMap的效率更高，因为它使用唯一的键来获取对象。而HashSet在添加元素时需要额外的比较和处理，所以在添加大量元素时可能会稍慢一些59。
⑥　空值的处理不同：HashMap允许有一个键为空，多个值为空；而HashSet只允许有一个空值。
⑦　数据结构和存储原理：虽然HashSet和HashMap在表面上看起来不同，但HashSet实际上是通过HashMap来实现的。在HashSet中，元素被视为键，而所有的值都被设定为一个固定的对象。这意味着HashSet中的元素需要通过equals()和hashCode()方法来确保唯一性，这与HashMap中键的处理方式相同。
⑧　应用场景的差异：HashMap适用于需要通过唯一键快速检索值的场景，而HashSet适用于需要确保集合中元素唯一性的场景。如果你只需要存储不重复的元素，那么使用HashSet更为合适；如果你需要存储键值对，那么应该使用HashMap。
综上所述，尽管HashSet和HashMap在某些方面有相似之处，但它们的设计目的和使用场景是不同的。选择哪个数据结构取决于具体的需求。

13.Java 中 HashMap 的扩容机制是怎样的？

HashMap的扩容机制是通过在元素数量达到阈值时将数组容量扩大为原来的两倍，并重新计算键的哈希值来实现的。
具体来说，扩容操作包括以下几个步骤：
①　重新计算哈希值：遍历原数组中的每个元素，并将其重新计算哈希值后放入新数组中。这个过程确保了元素在新数组中仍然具有相同的哈希值，从而维持了元素的有序性。
②　重新定位元素：通过哈希函数重新定位每个元素在新的数组中的位置，确保元素之间的索引关系依然正确。
③　更新阈值：扩容后，HashMap的阈值也会相应更新为新数组大小与加载因子的乘积。例如，如果新数组大小为32，加载因子为0.75，则新的阈值为24。
总之，通过上述扩容机制，HashMap能够在数据量增长时自动调整其内部结构，以保持高效的存取性能。

14.为什么 HashMap 在 Java 中扩容时采用 2 的 n 次方倍？

HashMap在Java中扩容采用2的n次方倍是为了减少哈希碰撞，提高查询效率，并且方便重新计算元素的位置。
HashMap在Java中扩容采用2的n次方倍的原因如下：
①　当HashMap的容量是2的幂次方时，哈希值的分布更加均匀，这有助于减少哈希碰撞的发生。哈希碰撞是指不同的键映射到了同一个数组索引上。虽然不能完全避免哈希碰撞，但可以通过合理选择容量大小来最小化这种情况。
②　当HashMap需要扩容时，新的容量也是2的幂次方，这使得旧的哈希值在新的容量下重新计算索引时，可以更好地分散到更大的数组中，从而进一步降低哈希碰撞的概率。
③　在Java中，HashMap的容量大小通常设置为2的幂次方，这是因为当容量是2的幂次方时，(capacity-1)就是一个只有低位为1，其余位为0的数。在这种情况下，hash(key)&(capacity-1)的效果等价于hash(key)%capacity，但前者更快，因为按位与操作在现代处理器上通常比取模运算要快得多。

15.为什么 Java 中 HashMap 的默认负载因子是 0.75？

HashMap的负载因子默认为0.75,这是因为这是一个时间和空间效率的权衡。
负载因子过高（如1.0）会导致过多的Hash冲突，影响查询效率；过低（如0.5）则会浪费空间。0.75既能保持较高的空间利用率，又能有效减少冲突，维持较好的查询性能。比如当前的容器容量是16，负载因子是0.75，16*0.75=12，也就是说，当容量达到了12的时候就会进行扩容操作。他的作用很简单，相当于是一个扩容机制的阈值。当超过了这个阈值，就会触发扩容机制。

16.为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

JDK 1.8 对 HashMap 进行红黑树的改动是为了优化性能，特别是在处理哈希冲突时的插入、删除和查找操作。
在 JDK 1.8 之前，HashMap 的实现是数组加链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量元素存放到同一个桶中时，这个桶下会有一条长长的链表，这个时候 HashMap 就相当于一个单链表，遍历的时间复杂度是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(log n)）来优化这个问题。

17.JDK 1.8 对 HashMap 除了红黑树还进行了哪些改动？

①　CAS操作：在某些情况下，JDK1.8使用CAS(Compare and Swap)操作来实现线程安全，尤其是在多线程环境下，减少了锁的竞争，提高了并发性能。
②　hashmap初始化：默认初始容量必须是2的幂，即static final int DEFAULT_INITIAL_CAPACITY=1<<4;//aka16。

18.Java 中的 LinkedHashMap 是什么？

Java中的LinkedHashMap是HashMap的一个子类，它除了具有HashMap的所有特性外，还维护了元素的插入顺序。
以下是LinkedHashMap的一些关键特性和用法：

19.Java 中的 TreeMap 是什么？

TreeMap使用键值对存储数据，支持添加、删除、查询等操作，时间复杂度为O(logn)。TreeMap的常用方法包括：put(Object key,Object value)：将指定的键值对添加到TreeMap中；get(Object key)：获取指定键的对应值；remove(Object key)：删除指定键的键值对；size()：返回TreeMap中键值对的数量；firstKey()：返回TreeMap中最小的键；lastKey()：返回TreeMap中最大的键；keySet()：返回TreeMap中所有键的集合；values()：返回TreeMap中所有值的集合。

20.Java 中的 IdentityHashMap 是什么？

Java中的IdentityHashMap是一个特殊的Map实现，它在比较键（key）是否相等时，使用引用相等性而非对象相等性。
①　键的比较方式：在IdentityHashMap中，当且仅当两个键严格相等（即它们指向内存中的同一位置）时，才认为这两个键相等。这与HashMap不同，后者使用equals()方法来判断键是否相等。
②　处理冲突的方式：IdentityHashMap处理冲突的方式是开放地址法中的线性再探测。当前位置被占用时，它会在右相邻的位置寻找，而在IdentityHashMap中，一个键值对会占用表中的两个位置，因此操作是加2，如果超出表大小，则从0开始。
③　特殊用途：IdentityHashMap有其特殊用途，例如序列化、深度复制或记录对象代理。在某些情况下，使用IdentityHashMap可以带来便利。
④　null值的支持：IdentityHashMap允许使用null作为键和值。
⑤　继承关系和接口实现：IdentityHashMap继承了AbstractMap抽象类，拥有Map的基本操作。它还实现了Map接口，用法与HashMap差不多，都是用Hash表实现数据的存储。此外，IdentityHashMap实现了Cloneable接口，覆盖了clone()方法，能被克隆。它也实现了Serializable接口，支持序列化，可通过序列化传输。