Java集合类面试题

一. 概述

1. Java集合概览

Java集合类面试题总结Java集合类面试题

Collection

Set

TreeSet：基于红黑树实现，支持有序性操作.

HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。

LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。

List

ArrayList：基于动态数组实现，支持随机访问。

Vector：和 ArrayList 类似，但它是线程安全的。

LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

Queue

LinkedList：可以用它来实现双向队列。

PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

Map

TreeMap：基于红黑树实现。

HashMap：基于哈希表实现。

HashTable：和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。

LinkedHashMap：使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。

2. List,Set,Map 三者的区别？

List：存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
Map: 使用键值对（kye-value）存储，Key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

3. 数组与集合的对比

数组的一旦声明之后，长度就不可变了；同时，声明数组时的数据类型也决定了该数组存储的数据的类型；而且，数组存储的数据是有序的、可重复的，特点单一。
集合提高了数据存储的灵活性，Java 集合不仅可以用来存储不同类型不同数量的对象，还可以保存具有映射关系的数据。

4. RandomAccess 接口的作用

RandomAccess接口是一个标记接口，它并未定义方法。其目的是用于指示实现类具有随机访问特性，在遍历时使用下标访问较迭代器更快。

如在 binarySearch（) 方法中，它要判断传入的 list 是否 RamdomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法

5. 哪些集合类提供对元素的随机访问？

ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。

6.什么是Iterator？

标准化各类容器的遍历过程，使得遍历容器不依赖于容器的内部结构而采用同一种逻辑。Iterator的具体实现由各容器根据其数据结构特点自行实现。

7. Iterator与ListIterator有什么区别？

Iterator：只能正向遍历集合，适用于获取移除元素。ListIerator：继承Iterator，可以双向列表的遍历，同样支持元素的修改。
Iterator可以遍历Set和List集合，而ListIterator只能遍历List
ListIterator从Iterator接口继承，然后添加了一些额外的功能，比如添加一个元素、替换一个元素、获取前面或后面元素的索引位置。

8. fail-fast（快速失败）

“快速失败”也就是fail-fast，它是Java集合的一种错误检测机制。当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。记住是有可能，而不是一定。例如：假设存在两个线程（线程1、线程2），线程1通过Iterator在遍历集合A中的元素，在某个时候线程2修改了集合A的结构（是结构上面的修改，而不是简单的修改集合元素的内容），那么这个时候程序就会抛出 ConcurrentModificationException 异常，从而产生fail-fast机制。
产生原因：迭代器在调用next()、remove()方法时都会检测modCount == expectedModCount，如果不相同则抛出ConcurrentModificationException 异常。expectedModCount是在获取迭代器时获取的，而ArrayList中无论add、remove、clear方法只要是涉及了改变ArrayList元素的个数的方法都会导致modCount的改变。

9. fail-fast解决方案

方案一：在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，这样就可以解决。但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
方案二：使用CopyOnWriteArrayList来替换ArrayList。推荐使用该方案。

10. fail-fast 与 fail-safe 有什么区别？

Iterator 的 fail-fast 属性与当前的集合共同起作用，因此它不会受到集合中任何改动的影响。Java.util 包中的所有集合类都被设计为 fail-fast 的，而 java.util.concurrent 中的集合类都为 fail-safe 的。当检测到正在遍历的集合的结构被改变时，fail-fast 迭代器抛出ConcurrentModificationException，而 fail-safe 迭代器从不抛出 ConcurrentModificationException。

11.为什么 Collection 不能继承 Cloneable 和 Serializable？

Collection表示一个集合，包含了一组对象。如何存储和维护这些对象是由具体实现来决定的。因为集合的具体形式多种多样，例如list允许重复，set则不允许。而克隆（clone）和序列化（serializable）只对于具体的实体，对象有意义，你不能说去把一个接口，抽象类克隆，序列化甚至反序列化。所以具体的collection实现类是否可以克隆，是否可以序列化应该由其自身决定，而不能由其超类强行赋予。
如果collection继承了clone和serializable，那么所有的集合实现都会实现这两个接口，而如果某个实现它不需要被克隆，甚至不允许它序列化（序列化有风险），那么就与collection矛盾了。

12. Arrays.sort()的原理

对于很小的数组（长度小于47），使用插入排序。
至于大过47且小于286的，用一种快速排序（多轴快排）的方法：
1. 从数列中挑出五个元素，称为 “基准”（pivot）；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
至于大于286的，它会进入归并排序（Merge Sort）

二. List

¥1. ArrayList 和 LinkedList 的区别？

底层数据结构： Arraylist 底层使用的是Object数组；LinkedList 底层使用的是双向链表数据结构；
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，插入和删除元素的时间复杂度受元素位置的影响，近似为 O（n）。 ② LinkedList 采用链表存储，插入，删除元素时间复杂度不受元素位置的影响，近似 O（1）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而ArrayList 实现了RandmoAccess 接口，所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

2. ArrayList 的增删是否一定比 LinkedList 要慢？

如果增删都是在末尾来操作，此时 ArrayList 就不需要移动和复制数组来进行操作，速度是比 LinkedList 要快的。
如果删除操作的位置是在中间。由于 LinkedList 的消耗主要是在遍历上，ArrayList 的消耗主要是在移动和复制上（底层调用的是 arrayCopy() 方法，是 native 方法）。LinkedList 的遍历速度是要慢于 ArrayList 的复制移动速度的，如果数据量有百万级的时，还是 ArrayList 要快。

¥3. ArrayList 的扩容机制？

如果数组为空，则创建一个容量为10的初始数组（当真正对数组进行添加元素操作时，才真正分配容量）
添加元素时首先调用 ensureCapacityInternal 方法，传入 size+1 进去，检查是否需要扩充 elementData 数组的大小；
如果需要扩容，newCapacity = 扩充数组为原来的 1.5 倍(不能自定义)
如果扩容后数组大小超过了MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)，就使用所需的最少容量 minCapacity ，如果minCapacity大于Integer的最大值，则报异常；否则判断 minCapacity 是否大于 MAX_ARRAY_SIZE，如果大于，就取 Integer.MAX_VALUE，否则扩容到MAX_ARRAY_SIZE；
使用 System.arraycopy 方法，将 original 数组的所有数据复制到 copy 数组中，这是一个本地方法。

4. System.arraycopy() 和 Arrays.copyOf()方法的区别

copyOf()内部实际调用了 System.arraycopy() 方法
arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

5. Arraylist 和 Vector 的区别?

ArrayList 线程不安全；Vector 是 List 的古老实现类，线程安全。
ArrayList的扩容因子是1.5，Vector 默认扩容因子是2，可指定
ArrayList在第一次添加元素时才创建数组，Vector在初始化时就创建好容量为10的数组

6. 为什么Vector类认为是废弃的或者是非官方地不推荐使用？

Vector同步了每个方法，导致效率很低。
而通常有想要同步的是整个操作序列。同步单个的操作也不安全.而且效率更慢。
如果需要保证线程安全，可以使用Collections.sychronizedList来装饰一个集合。

7.在 Queue 中 poll()和 remove()有什么区别？

相同点：都是返回第一个元素，并在队列中删除返回的对象。

不同点：如果没有元素 poll()会返回 null，而 remove()会直接抛出 NoSuchElementException 异常。

三. Set

1. HashSet 的实现原理？

HashSet 的实现是依赖于 HashMap 的。HashSet 的值是作为 HashMap 的 key 存储在 HashMap 中的，HashMap 的 value 则是 PRESENT 变量（new Object())，这个变量只作为放入 map 时的一个占位符而存在，所以没什么实际用处。
由于HashMap的Key不允许重复，因此HashSet的元素不会重复

四. Map

1. HashMap 和 Hashtable 的区别

线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
效率：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

2.HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8

JDK1.7：Entry数组 + 链表

JDK1.8：Node 数组 + 链表+红黑树，当链表上的元素个数超过 8 个并且数组长度 >= 64 时自动转化成红黑树，节点变成树节点，以提高搜索效率和插入效率到 O(logN)。Entry 和 Node 都包含 key、value、hash、next 属性。

2.5 HashMap的红黑树节点存储的是什么

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 红黑树父节点
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // 删除后需要取消链接
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }　　　　 //省略后续代码

TreeNode继承自LinkedHashMap中的内部类——LinkedHashMap.Entry，而这个内部类又继承自Node，所以算是Node的孙子辈了。
属性：parent指向父节点，left指向左孩子，right指向右孩子，prev则指向前一个节点（原链表中的前一个节点），red表示颜色

3.HashMap 的 put 方法的执行过程？

首先会计算 key 的 hash 值，然后根据 hash 值确认在 table 中存储的位置。
若该位置没有元素，则直接插入。
否则迭代该处元素链表并依次比较其 key 的 hash 值。如果两个 hash 值相等且 key 值相等(e.hash == hash && ((k = e.key) == key || key.equals(k)))，则用新的value 覆盖原来节点的 value。
如果两个 hash 值相等但 key 值不等，若为树结构则按树的方式插入，若为链表结构则在链表尾部插入新节点
插入后若达到红黑树阈值（链表上的元素个数超过 8 个并且数组长度 >= 64 ）则转化为红黑树
更新size，达到扩容阈值则开始扩容

3.5 转换为红黑树的阈值为什么是8

首先和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡。在负载因子0.75（HashMap默认）的情况下，单个hash槽内元素个数为8的概率小于百万分之一，将7作为一个分水岭，等于7时不做转换，大于等于8才转红黑树，小于等于6才转链表。链表中元素个数为8时的概率已经非常小，再多的就更少了，所以原作者在选择链表元素个数时选择了8，是根据概率统计而选择的。

红黑树中的TreeNode是链表中的Node所占空间的2倍，虽然红黑树的查找效率为o(logN)，要优于链表的o(N)，但是当链表长度比较小的时候，即使全部遍历，时间复杂度也不会太高。所以，要寻找一种时间和空间的平衡，即在链表长度达到一个阈值之后再转换为红黑树。

4. HashMap 的 get 方法的执行过程？

通过 key 的 hash 值找到在 table 数组中的位置，在该位置用迭代查找有没有相等的key，有则返回该key对应的value，没有则返回null

判断相等：先判断hash是否相等，再判断==，再判断equals

if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))

4.5 为什么先判断hash再判断equals

因为只要hash不等equals一定不等，无需再去调用equals方法，提前返回

5.HashMap 的 resize 方法的执行过程？

有两种情况会调用 resize 方法：

第一次调用 HashMap 的 put 方法时，会调用 resize 方法对 table 数组进行初始化，如果不传入指定值，默认大小为 16。
扩容时会调用 resize，即 size > threshold 时，创建一个原容量两倍大小的新数组，再将原数组的元素按照put的规则逐个转移至新数组。

如果转移时发现该位置处拉着一条链表，则先讲链表拆分：

链表中的 node 要么在 newtab 的 i 位置（不变），要么在 newtab 的 i + n 位置。
因此可以把 table[i] 这个桶中的 node 拆分为两个链表 l1 和 l2：如果 hash & oldCap == 0，那么当前这个 node 被连接到 l1 链表；否则连接到 l2 链表。
当遍历完 table[i] 处的所有 node 的时候，我们得到两个链表 l1 和 l2，这时我们令 newtab[i] = l1，newtab[i + n] = l2，这就完成了 table[i] 位置所有 node 的迁移（rehash），这也是 HashMap 中容量一定的是 2 的整数次幂带来的方便之处。

6.HashMap 的 size 为什么必须是 2 的整数次方？

提升计算数组位置效率：size 为 2 的 n 次方时，hash& (size- 1) 等价于对 size 取模，且速度比直接取模快得多。
若size为奇数， (size- 1)最后一位为0，hash& (size- 1) 最后一位必为0，浪费了一半空间
扩容转移时便于链表的拆分（根据hash & oldCap == 0拆分）

7. JDK1.7和 JDK1.8 HashMap实现原理的区别

底层数据结构：1.7为数组+链表，1.8为数组+链表+红黑树
hash的计算方式：1.7算法包含4次位运算+5次异或；1.8算法为 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 1次位运算+1次异或，比起1.7更加简洁
链表数据插入方式：1.7采用头插法，在多线程环境下会引发死循环；1.8采用尾插法，避免了这一问题
扩容机制：1.7转移链表时逐个计算新位置，且采用头插法；1.8转移链表前统一计算，拆分为两个链表后插入新位置

7.5. 为什么HashMap为什么不用跳表替换红黑树?

8. HashMap 多线程死循环问题？

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表，进而使得后面 get 的时候，会死循环。

jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

https://coolshell.cn/articles/9606.html

9. HashMap 的 get 方法能否判断某个元素是否在 map 中？

HashMap 的 get 函数的返回值不能判断一个 key 是否包含在 map 中，因为 get 返回 null 有可能是不包含该 key，也有可能该 key 对应的 value 为 null。因为 HashMap 中允许 key 为 null，也允许 value 为 null。

10. 为什么String, Interger这样的wrapper类适合作为键？

因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。

不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。

因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。

11.能否使用任何类作为 Map 的 key？

可以使用任何类作为 Map 的 key，然而在使用之前，需要考虑以下几点：

如果类重写了 equals() 方法，也应该重写 hashCode() 方法。

类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

如果一个类没有使用 equals()，不应该在 hashCode() 中使用它。

用户自定义 Key 类最佳实践是使之为不可变的，这样 hashCode() 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变，这样就会解决与可变相关的问题了。

12. HashMap 的 7 种遍历方式与性能

使用迭代器（Iterator）EntrySet 的方式进行遍历；
使用迭代器（Iterator）KeySet 的方式进行遍历；
使用 For Each EntrySet 的方式进行遍历；
使用 For Each KeySet 的方式进行遍历；
使用 Lambda 表达式的方式进行遍历；
使用 Streams API 单线程的方式进行遍历；
使用 Streams API 多线程的方式进行遍历。

除了并行循环的 parallelStream 性能比极高之外（多线程方式性能肯定比较高），其他方式的遍历方法在性能方面几乎没有任何差别。

13.LinkedHashMap 的实现原理?

LinkedHashMap 也是基于 HashMap 实现的，不同的是它定义了一个 Entry header，这个 header 不是放在 Table 里，它是额外独立出来的。LinkedHashMap 通过继承 hashMap 中的 Entry，并添加两个属性 Entry before，after 和 header 结合起来组成一个双向链表，来实现按插入顺序或访问顺序排序。

LinkedHashMap 定义了排序模式 accessOrder，该属性为 boolean 型变量，对于访问顺序，为 true；对于插入顺序，则为 false。一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。

13.5 HashMap为什么不是线程安全的

如线程A发现某桶位置没有元素后挂起，然后线程B在该位置处插入元素；之后又切换到A，A会把B插入的元素给覆盖了

if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
            tab[i] = newNode(hash, key, value, null);

size++操作也是非线程安全的

14. HashMap 与 ConcurrentHashMap 的区别是什么?

HashMap 不是线程安全的，而 ConcurrentHashMap 是线程安全的。

ConcurrentHashMap 采用锁分段技术，将整个Hash桶进行了分段segment，也就是将这个大的数组分成了几个小的片段 segment，而且每个小的片段 segment 上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段 segment，然后再在这个片段上面进行插入，而且这里还需要获取 segment 锁，这样做明显减小了锁的粒度。

16.ConcurrentHashMap 的实现原理是什么？

JDK 7：中 ConcurrentHashMap 采用了数组 + Segment + 分段锁的方式实现。
JDK 8：中 ConcurrentHashMap 参考了 JDK 8 HashMap 的实现，采用了数组 + 链表 + 红黑树的实现方式来设计，内部大量采用 CAS 操作。

ConcurrentHashMap 采用了非常精妙的"分段锁"策略，ConcurrentHashMap 的主干是个 Segment 数组。

final Segment<K,V>[] segments;

Segment 继承了 ReentrantLock，所以它就是一种可重入锁（ReentrantLock)。在 ConcurrentHashMap，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，并发环境下，对于不同 Segment 的数据进行操作是不用考虑锁竞争的。就按默认的 ConcurrentLevel 为 16 来讲，理论上就允许 16 个线程并发执行。

所以，对于同一个 Segment 的操作才需考虑线程同步，不同的 Segment 则无需考虑。Segment 类似于 HashMap，一个 Segment 维护着一个HashEntry 数组：

transient volatile HashEntry<K,V>[] table;

HashEntry 是目前我们提到的最小的逻辑处理单元了。一个 ConcurrentHashMap 维护一个 Segment 数组，一个 Segment 维护一个 HashEntry 数组。因此，ConcurrentHashMap 定位一个元素的过程需要进行两次 Hash 操作。第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。

17. 有哪些计算Hash值的方法

直接寻址法：取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b，当中a和b为常数（这样的散列函数叫做自身函数）
数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成散列地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
平方取中法：取keyword平方后的中间几位作为散列地址。
折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为散列地址。
随机数法：选择一随机函数，取keyword的随机值作为散列地址，通经常使用于keyword长度不同的场合。
除留余数法：取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，若p选的不好，easy产生同义词。

18. 常见的Hash算法

MD4。MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用快速软件实现–它是基于 32 位操作数的位操作来实现的。
MD5。MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本号。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 同样。MD5比MD4来得复杂，而且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

MD5算法的原理可简要的叙述为：MD5码以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

步骤：每次的运算都由前一轮的128位结果值和当前的512bit值进行运算

SHA-1 及其它。SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4同样原理,而且模仿了该算法。

19. 红黑树节点的插入

先看父节点：

父黑直接插入
父红看叔叔：
- 叔红父叔涂黑爷爷涂红
- 叔黑:
  - 父左我左以父R
  - 父左我右以我LR
  - 父右我左以我RL
  - 父右我右以父L

20. HashMap有哪些内部类

有以下内部类

Java集合类面试题总结Java集合类面试题

常用的有Node,TreeNode,EntrySet,KeySet,KeyIterator

Java集合类面试题总结Java集合类面试题

Java集合类面试题

一. 概述

1. Java集合概览

Collection

Set

List

Queue

Map

2. List,Set,Map 三者的区别？

3. 数组与集合的对比

4. RandomAccess 接口的作用

5. 哪些集合类提供对元素的随机访问？

6.什么是Iterator？

7. Iterator与ListIterator有什么区别？

8. fail-fast（快速失败）

9. fail-fast解决方案

10. fail-fast 与 fail-safe 有什么区别？

11.为什么 Collection 不能继承 Cloneable 和 Serializable？

12. Arrays.sort()的原理

二. List

¥1. ArrayList 和 LinkedList 的区别？

2. ArrayList 的增删是否一定比 LinkedList 要慢？

¥3. ArrayList 的扩容机制？

4. System.arraycopy() 和 Arrays.copyOf()方法的区别

5. Arraylist 和 Vector 的区别?

6. 为什么Vector类认为是废弃的或者是非官方地不推荐使用？

7.在 Queue 中 poll()和 remove()有什么区别？

三. Set

1. HashSet 的实现原理？

四. Map

1. HashMap 和 Hashtable 的区别

2.HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8

2.5 HashMap的红黑树节点存储的是什么

3.HashMap 的 put 方法的执行过程？

3.5 转换为红黑树的阈值为什么是8

4. HashMap 的 get 方法的执行过程？

4.5 为什么先判断hash再判断equals

5.HashMap 的 resize 方法的执行过程？

6.HashMap 的 size 为什么必须是 2 的整数次方？

7. JDK1.7和 JDK1.8 HashMap实现原理的区别

7.5. 为什么HashMap为什么不用跳表替换红黑树?

8. HashMap 多线程死循环问题？

9. HashMap 的 get 方法能否判断某个元素是否在 map 中？

10. 为什么String, Interger这样的wrapper类适合作为键？

11.能否使用任何类作为 Map 的 key？

12. HashMap 的 7 种遍历方式与性能

13.LinkedHashMap 的实现原理?

13.5 HashMap为什么不是线程安全的

14. HashMap 与 ConcurrentHashMap 的区别是什么?

16.ConcurrentHashMap 的实现原理是什么？

17. 有哪些计算Hash值的方法

18. 常见的Hash算法

19. 红黑树节点的插入

20. HashMap有哪些内部类

继续阅读