Java 集合相关问题整理

ArrayList 和 LinkedList 的区别？

1. ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。

2. ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。

3. 在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为 ArrayList 增删操作要影响数组内的其他数据的下标。

4. LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

5. ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。

综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

ArrayList 和 Vector 的区别？

这两个类都实现了 List 接口（List 接口继承了 Collection 接口），他们都是有序集合，都是基于数组实现，初始容量都是 10，最大容量都为 Integer.MAX_VALUE-8。

1. ArrayList 是非线程安全的，而 Vector 使用了 synchronized 来实现线程同步，是线程安全的。
2. 由于 Vector 加了锁，所以 ArrayList 在性能方面要优于 Vector。
3. ArrayList 和 Vector 都会根据实际的需要动态的调整容量（不够的时候），只不过在 Vector 扩容每次会增加 1 倍，而 ArrayList 只会增加 50%。

Vector 类的所有方法都是同步的。可以由两个线程安全地访问一个 Vector 对象、但是一个线程访问 Vector 的话代码要在同步操作上耗费大量的时间。

什么是 Hash 算法？

哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

HashMap 的实现原理？

HashMap 是 JDK1.2 引进的 Map 的一个实现，是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。它不保证映射的顺序，特别是不保证该顺序恒久不变。

在 1.8 之前是基于数组+链表，出现 hash 冲突时使用头插法插入到链表。

JDK1.8 主要的改进：

1. resize 扩容优化，不再全部计算 hash 重新分发，而是将 hash 值与原容量与运算来判断是否需要移动位置，此时的元素要么位置不变，要么变为原位置 + 旧容量；
2. 引入了红黑树，当链表的节点数量大于或者等于 8 的时候且数组的容量大于 64 的时候，就会将链表转换为红黑树，目的是避免单条链表过长而影响查询效率；
3. 出现 hash 冲突时将头插法改为尾插法，解决了多线程死循环问题，但仍是非线程安全的，多线程时可能会造成数据丢失问题。

构造的时候只初始化了负载因子 0.75，首次 put 的时候直接调用 resize 进行容器初始化，初始容量为 16（hash 算法，保证哈希值平均分布，只有当为 16 的时候才可以最大程度的保证平均分布），默认负载因子为 0.75，即达到容量的 0.75 时，扩容一倍。

在 1.8 之前，扩容之后需要重新去计算其 Hash 值，根据 Hash 值对其进行分发，在 1.8 版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为 0，重新进行 hash 分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上。

put 的时候，会通过 hash 算法（对 key 进行 hash 之后再和数组容量-1 进行与运算），计算出节点数组的下标，此时这个实体就被存储到这个数组对应的下标位置。出现 hash 冲突时采用链表的方式，挂载相同下标的实体。在 1.8 以后，当链表的节点数量大于或者等于 8 的时候且数组的容量大于 64 的时候，就会将链表转换为红黑树。

HashMap 如何计算下标的？

先用 key.hashCode() 与 key.hashCode()>>>16 进行异或操作，作用是：高 16bit 不变，低 16bit 和高 16bit 做了一个异或，目的是减少碰撞。再用这一步的结果和数组容量-1 进行与运算，得到数组容量范围内的下标。

HashMap 如何解决哈希冲突的？

在出现 hash 冲突时，使用链表或链表+红黑树来实现相同数组下标的存储。

HashMap 如何实现线程安全？

1. 使用 HashTable
2. 使用 Collections.synchronizeMap(hashMap);
3. 使用 JDK1.5 加入的 ConcurrentHashMap。

HashTable 的实现原理？

Hashtable 比较古老，是 JDK1.0 就引入的类，它继承于 Dictionary 类，实现了 Map 接口。

它是数组+链表的结构，默认数组容量为 11，也可以指定容量。因为它是直接使用除留余数法定位地址，所以不要求容量必须为 2 的整数次幂。

它计算下标位置是直接用 key 的 hashCode()方法，然后取模运算得到下标位置。

默认达到容量的 0.75 的时候进行扩容，扩为原来的 2 倍加 1，扩容之后会重新 hash。

它的每个操作方法都加上了 synchronized，所以是线程安全的，但是直接对整个容器加锁，多线程效率很低。

HashTable 和 HashMap 的区别？

1. HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰。
2. 因为线程安全的问题，HashMap 要比 HashTable 效率高。
3. HashMap 中，允许一个 key 为 null，多个值为 null，而在 HashTable 中 key 和值都不允许为 null，只要有一个 null，直接抛 NullPointerException。
4. 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
5. 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。
6. JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
7. Hashtable 计算 hash 值，直接用 key 的 hashCode()方法，而 HashMap 重新计算了 key 的 hash 值，Hashtable 在求 hash 值对应的位置索引时，用的是取模运算，而 HashMap 在求位置索引时，用的是与运算。
8. 在 Hashtable 的类注释中有说明，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。

Collections.synchronizeMap 的实现原理？

SynchronizedMap 类中有一个 mutex 信号量，默认为对象本身，对所有操作方法都加了 synchronized(mutex) 来加锁。

ConcurrentHashMap 的实现原理？

JDK1.8 之前

在 JDK1.8 之前，它由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 数组在 ConcurrentHashMap 里扮演锁的角色，HashEntry 则用于存储键-值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组，默认分配 16 个 Segment（比 Hashtable 效率提高 16 倍），Segment 的结构和 HashMap 类似，是一种数组加链表结构；

一个 Segment 里包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素；每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得它对应的 Segment 锁。

JDK1.8 之后

放弃了 Segment 设计，使用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化）synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率提高很多，整个看起来就像是优化过且线程安全的 HashMap。

put 数据时，如果相应位置的 Node 还没有初始化，则调用 CAS 插入相应的数据，然后执行 addCount()方法尝试更新元素个数 baseCount。如果相应位置的 Node 不为空，（且当前该节点不处于移动状态，）则对该节点加 synchronized 锁，（如果该节点的 hash 不小于 0，则）遍历链表更新节点或插入新节点，或者往红黑树中更新节点或插入新节点。

如果该节点是 TreeBin 类型的节点，说明是红黑树结构，则通过 putTreeVal 方法往红黑树中插入节点；如果 binCount 不为 0，说明 put 操作对数据产生了影响，如果当前链表的个数达到 8 个，则通过 treeifyBin 方法转化为红黑树，如果 oldVal 不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值。

虽然在 JDK1.8 中还有 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。

ConcurrentHashMap 是怎样实现线程安全的？

在 JDK1.8 之前，是通过 Segment 分段锁。1.8 之后使用 CAS + Synchronized，向某个数组下标插入数据时，如果此位置为空，就使用 CAS 来插入数据，如果不为空就对这个位置的节点加 Synchronized 锁。

LinkedHashMap 的实现原理？

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

HashSet 的实现原理？

HashSet 是基于 HashMap 实现的，HashSet 的值存放于 HashMap 的 key 上，HashMap 的 value 统一为 present，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，HashSet 不允许重复的值。

Java 集合的快速失败机制 “fail-fast” 是什么？

是 Java 集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会抛出 ConcurrentModificationException 产生 fail-fast 机制。

迭代器 Iterator 是什么？

Iterator 接口提供遍历任何 Collection 的接口，因为所有 Collection 都继承了 Iterator 接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器取代了 Java 集合框架中的 Enumeration，迭代器允许调用者在迭代过程中移除元素。

Iterator 的特点是只能单向遍历，但是更加安全，因为它可以确保，在当前遍历的集合元素被更改的时候，就会抛出 ConcurrentModificationException 异常。

refer:
https://juejin.cn/post/6844904125939843079
https://blog.51cto.com/u_15127640/2873963
https://www.cnblogs.com/kubixuesheng/p/6144535.html