Map
面试官您好，关于 Java 中常见的 Map 集合，我可以从非线程安全和线程安全两个方面来介绍：
首先，我们来看一下非线程安全的 Map 实现，这些在单线程环境下性能通常更好，但在并发场景下需要外部同步：
HashMap：- 这是我们最常用的
Map实现，它的底层是基于哈希表（也称散列表）的。在 JDK 1.8 及以后，具体实现是数组 + 链表 + 红黑树。当链表长度超过一定阈值（默认为8）并且数组长度大于一定阈值（默认为64）时，链表会转换为红黑树，以优化查询效率。 - 它的键和值都允许为
null（键最多一个null）。 - 线程不安全：正如您所说，在多线程环境下，如果多个线程同时对
HashMap进行put操作，尤其是在发生扩容（resize）的时候，可能会导致数据不一致，甚至在 JDK 1.7 及之前版本中可能因为头插法导致链表形成环，从而引发死循环。JDK 1.8 虽然改用了尾插法，避免了死循环，但并发put依然可能导致数据覆盖或丢失。
- 这是我们最常用的
LinkedHashMap：- 它继承自
HashMap，因此具备HashMap的所有特性，包括非线程安全。 - 它的特别之处在于额外维护了一个双向链表，这个链表可以记录元素的插入顺序或者访问顺序（通过构造函数参数控制）。因此，迭代
LinkedHashMap时，元素的顺序是可以预期的。 - 线程不安全：由于其核心结构和操作依赖于
HashMap，并且双向链表的维护也未做并发控制，所以在多线程环境下，它同样存在与HashMap类似的线程安全问题，并发修改会破坏其内部结构和顺序。
- 它继承自
TreeMap：TreeMap是基于红黑树实现的，这使得它能保证键值对按照键的自然顺序或者自定义比较器（Comparator）的顺序进行排序。- 它的键不允许为
null（除非自定义比较器允许），值可以为null。 - 线程不安全：红黑树的插入、删除、旋转等操作在并发环境下如果没有同步机制，很容易破坏树的平衡和结构，导致数据不一致或程序异常。
接下来，是线程安全的 Map 实现，它们设计用来在并发环境中使用：
Hashtable：- 这是 Java 早期提供的一个线程安全的
Map实现，它的底层也是哈希表。键和值都不允许为null，否则会抛出NullPointerException。 - 它实现线程安全的方式比较“粗暴”：几乎所有公开的方法（如
get,put,remove,size等）都使用了synchronized关键字进行修饰。这意味着在任何时刻，只有一个线程能访问Hashtable的这些同步方法。 - 缺点：虽然保证了线程安全，但由于锁的粒度太大（锁整个对象），并发性能非常低下，在高并发场景下会成为严重的瓶颈。现在基本不推荐使用了。
- 这是 Java 早期提供的一个线程安全的
ConcurrentHashMap：- 这是 JUC (java.util.concurrent) 包下的一个高效的线程安全
Map，是目前并发场景下Map的首选。 - JDK 1.7 及以前：它采用了分段锁（Segment-based locking） 的技术。
ConcurrentHashMap内部由多个Segment组成，每个Segment类似于一个小的Hashtable，它有自己的锁。当对某个Segment中的数据进行操作时，只需要锁定那个Segment，而不是整个Map。这样，不同Segment上的操作可以并发进行，大大提高了并发效率。默认的并发级别（concurrencyLevel）是16，意味着有16个Segment。 - JDK 1.8 及以后：实现有了很大的变化，摒弃了
Segment的设计，而是采用了更细粒度的锁机制，类似于HashMap的数组 + 链表 + 红黑树结构。- 它主要通过
volatile保证可见性，通过 CAS (Compare-And-Swap) 操作来尝试无锁更新节点。 - 当 CAS 更新失败或者需要初始化某个哈希桶的头节点时，会使用
synchronized关键字来锁定哈希桶的头节点 （即数组中的那个 Node）。这意味着锁的粒度非常小，只锁住当前操作的那个哈希桶的头节点，不同哈希桶的操作完全可以并发执行。 - 这种设计使得在大多数情况下，尤其是读操作和不同桶的写操作，并发性能非常好。
- 它主要通过
- 这是 JUC (java.util.concurrent) 包下的一个高效的线程安全
总结一下：
在选择 Map 时，如果是在单线程环境或者能保证外部同步，HashMap 因其高效性通常是首选；如果需要保持插入顺序或访问顺序，则选择 LinkedHashMap；如果需要排序，则选择 TreeMap。
而在多线程并发环境下，强烈推荐使用 ConcurrentHashMap，它提供了优秀的并发性能和线程安全性。Hashtable 由于性能问题，已经不建议使用。另外，也可以通过 Collections.synchronizedMap(new HashMap<>()) 来获取一个线程安全的 Map，但它的实现方式类似于 Hashtable，通过在外部包装一层 synchronized，性能也不如 ConcurrentHashMap。
如何对Map进行快速遍历？
好的，关于如何快速遍历 Map，这确实是日常开发中经常遇到的问题。遍历的“快”通常指的是执行效率高、代码简洁。以下是我认为比较高效和推荐的几种遍历方式：
1. 遍历 entrySet() (最推荐，通用且高效)
这是遍历 Map 的首选方式，因为它允许我们同时访问键（key）和值（value），并且只需要对集合进行一次迭代。
- 原理：
entrySet()方法返回一个Set<Map.Entry<K, V>>，Map.Entry对象包含了键和值。我们遍历这个Set，然后从每个Entry对象中获取键和值。 - 效率：对于
HashMap、LinkedHashMap和TreeMap，这种方式都是高效的。因为你直接拿到了 Entry 对象，避免了像keySet()后再通过map.get(key)进行二次查找的开销（虽然对于HashMap这种get是 O(1) 的操作，开销不大，但entrySet更直接）。
Map<String, Integer> map = new HashMap<>();
// ... (populate map) ...
// 使用 for-each 循环 (JDK 5+)
System.out.println("--- Iterating using entrySet() with for-each ---");
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
}
// 使用 Iterator (更底层，但原理相同)
System.out.println("--- Iterating using entrySet() with Iterator ---");
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> entry = iterator.next();
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println("Key: " + key + ", Value: " + value);
// 如果需要在遍历时安全删除元素，使用 iterator.remove()
// if (someCondition) {
// iterator.remove();
// }
}
2. 使用 forEach() 方法 (JDK 8+，简洁)
Java 8 引入了 forEach() 方法，可以配合 Lambda 表达式使用，代码更简洁。
- 原理：
Map接口本身提供了forEach(BiConsumer<? super K, ? super V> action)方法。 - 效率：对于
HashMap等，其内部实现通常也是基于entrySet或者类似的高效机制，所以性能与直接遍历entrySet相当，主要优势在于代码的简洁性。
Map<String, Integer> map = new HashMap<>();
// ... (populate map) ...
System.out.println("--- Iterating using Map.forEach() (JDK 8+) ---");
map.forEach((key, value) -> {
System.out.println("Key: " + key + ", Value: " + value);
});
3. 遍历 keySet() 然后获取值 (一般不推荐，除非特定场景)
这种方式是先获取所有的键集合，然后遍历键集合，再通过 map.get(key) 获取对应的值。
- 效率：
- 对于
HashMap，get(key)操作的平均时间复杂度是 O(1)，所以整体遍历性能尚可，但比entrySet()略逊一筹，因为多了一步get操作。 - 对于
TreeMap，get(key)操作的时间复杂度是 O(log N)，如果通过keySet()遍历再get()，那么整体时间复杂度会是 O(N log N)，这比entrySet()的 O(N) 要差。 - 因此，除非你只需要键，或者有特殊理由，否则不推荐这种方式来同时获取键和值。
- 对于
Map<String, Integer> map = new HashMap<>();
// ... (populate map) ...
System.out.println("--- Iterating using keySet() ---");
for (String key : map.keySet()) {
Integer value = map.get(key); // 额外的 get 操作
System.out.println("Key: " + key + ", Value: " + value);
}
4. 遍历 values() (如果只需要值)
如果你只关心 Map 中的值，而不关心键，那么可以直接遍历 values() 方法返回的 Collection。
Map<String, Integer> map = new HashMap<>();
// ... (populate map) ...
System.out.println("--- Iterating using values() ---");
for (Integer value : map.values()) {
System.out.println("Value: " + value);
}
总结与建议：
- 首选
entrySet()配合 for-each 循环或 Iterator：这是最通用、最高效的遍历键值对的方式。 - JDK 8+ 可用
Map.forEach()：代码更简洁，性能与entrySet()遍历相当。 - 避免
keySet()后再get()：除非你明确知道get()操作非常廉价且你确实需要这种两步操作，否则它的效率通常不如entrySet()。 - 仅需值时用
values()：直接明了。
对于 ConcurrentHashMap 的遍历：
ConcurrentHashMap 的 entrySet(), keySet(), values() 返回的迭代器是弱一致性 (weakly consistent) 的，它们不会抛出 ConcurrentModificationException，并且可以容忍并发修改。它们反映了创建迭代器时或创建后某个时间点的状态，可能不会反映迭代器创建之后的所有修改。
ConcurrentHashMap 在 JDK 8+ 也提供了 forEach、forEachEntry、forEachKey、forEachValue 等并行遍历方法（如 forEachEntry(parallelismThreshold, action)），在大数据量且每个元素处理耗时较长时，可以利用多核 CPU 提升遍历处理速度。但对于简单的打印或累加，串行遍历通常已经足够快且开销更小。
所以在面试时，如果被问到如何快速遍历 Map，我首先会推荐使用 entrySet() 的方式，并解释其效率优势。如果面试官追问 Java 8 的新特性，我会补充 Map.forEach() 方法。
补充Stream API遍历Map
使用 Java 8 引入的 Stream API 来遍历 Map 确实是一种现代且功能强大的方式，特别适合进行链式操作，如过滤、转换等。
这里补充一下如何使用 Stream API 来遍历 Map：
1. 遍历 entrySet() 并转换为 Stream (最常用且推荐)
这是将 Map 的键值对转换为流进行处理的最直接方式。
- 获取
Stream<Map.Entry<K, V>>：通过map.entrySet().stream()获取。 - 操作：你可以对这个流进行各种中间操作（如
filter,map转换）和终端操作（如forEach,collect）。
Map<String, Integer> map = new HashMap<>();
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Orange", 15);
System.out.println("--- Iterating using entrySet().stream() ---");
map.entrySet().stream()
.forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));
// 示例：过滤并打印值大于10的条目
System.out.println("--- Filtering and iterating using entrySet().stream() ---");
map.entrySet().stream()
.filter(entry -> entry.getValue() > 10)
.forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));
// 示例：转换条目 (例如，只获取键)
System.out.println("--- Mapping to keys and iterating ---");
map.entrySet().stream()
.map(Map.Entry::getKey) // 或者 entry -> entry.getKey()
.forEach(key -> System.out.println("Key: " + key));
2. 遍历 keySet() 并转换为 Stream
如果你主要关心键，或者需要基于键进行操作后再获取值。
- 获取
Stream<K>：通过map.keySet().stream()获取。
System.out.println("--- Iterating using keySet().stream() ---");
map.keySet().stream()
.forEach(key -> System.out.println("Key: " + key + ", Value: " + map.get(key))); // 注意这里需要 map.get()
// 示例：过滤键并打印
System.out.println("--- Filtering keys and iterating ---");
map.keySet().stream()
.filter(key -> key.startsWith("A"))
.forEach(key -> System.out.println("Key: " + key + ", Value: " + map.get(key)));
- 注意：与非 Stream 版本的
keySet()遍历类似，如果需要值，仍然需要调用map.get(key)。如果同时需要键和值，entrySet().stream()通常更直接。
3. 遍历 values() 并转换为 Stream
如果你只关心值。
- 获取
Stream<V>：通过map.values().stream()获取。
System.out.println("--- Iterating using values().stream() ---");
map.values().stream()
.forEach(value -> System.out.println("Value: " + value));
// 示例：过滤值并打印
System.out.println("--- Filtering values and iterating ---");
map.values().stream()
.filter(value -> value > 15)
.forEach(value -> System.out.println("Value: " + value));
使用 Stream API 遍历 Map 的优势：
- 声明式编程：代码更易读，更侧重于“做什么”而不是“怎么做”。
- 链式操作：可以非常方便地组合多个操作，如
filter().map().sorted().collect()。 - 简洁性：对于复杂的操作序列，代码通常比传统的迭代方式更短。
- 并行处理潜力：可以通过调用
.parallelStream()来利用多核处理器并行处理流中的元素（适用于大数据量且操作独立的场景，但需注意并行开销）。
// 示例：并行流处理 (仅当数据量大且操作耗时才考虑)
// map.entrySet().parallelStream()
// .forEach(entry -> { /* ... potentially CPU-intensive operation ... */ });
总结：
- 当需要同时处理键和值，并且可能进行过滤、转换等复杂操作时，
map.entrySet().stream()是最佳选择。 - 当仅对键或值进行操作时，
map.keySet().stream()或map.values().stream()也很方便。 - Stream API 提供了更现代、更灵活的方式来处理集合数据，包括
Map。
在面试中，如果被问到 Map 的遍历方式，除了传统的迭代器和 for-each 循环，提及 Stream API 的用法会展示您对 Java 新特性的掌握和更广阔的技术视野。
HashMap实现原理介绍一下？
“面试官您好，关于 HashMap 的实现原理，我的理解主要包含以下几个核心方面：
1. 核心数据结构 (JDK 1.8+)
HashMap的底层主要是一个Node<K,V>[] table数组，这个数组也常被称为“哈希桶”（hash buckets）。每个数组元素可以是一个Node节点，也可以是null。Node<K,V>类：这是存储键值对的基本单元。它通常包含四个主要字段：int hash: 存储键的哈希值。K key: 存储键。V value: 存储值。Node<K,V> next: 指向链表中的下一个节点，用于解决哈希冲突。
- 当哈希冲突发生，并且同一个哈希桶中的链表长度达到一定阈值（默认为
TREEIFY_THRESHOLD = 8）且当前哈希表（数组）的长度也达到一定阈值（默认为MIN_TREEIFY_CAPACITY = 64）时，这个链表会转换为红黑树 (TreeNode) 来存储元素，以优化查询效率。TreeNode是Node的子类。
2. put(K key, V value) 方法的核心流程
- 计算哈希值：
- 首先，如果
key为null，它会被特殊处理，通常存储在table[0]的位置（如果table[0]也是一个链表或树，则按规则插入）。 - 对于非
null的key，会调用key.hashCode()方法获取原始哈希码。 - 然后，
HashMap会对这个原始哈希码进行一次扰动处理（rehash 或 spread），通常是将其高16位与低16位进行异或操作(h = key.hashCode()) ^ (h >>> 16)。这样做是为了让哈希值的高位也能参与到后续的索引计算中，使得哈希分布更均匀，减少冲突。
- 首先，如果
- 计算数组索引 (桶的位置)：
- 使用扰动后的哈希值
hash与(table.length - 1)进行按位与运算(n - 1) & hash来确定元素在table数组中的索引。因为table.length总是2的幂次方，所以(n - 1)的二进制表示就是一串1，按位与操作等效于取模hash % n，但位运算效率更高。
- 使用扰动后的哈希值
- 处理哈希冲突并插入/更新：
- 桶为空：如果计算出的索引位置
table[i]为null，直接创建一个新的Node放入该位置。 - 桶不为空（发生冲突）：
- 键已存在：如果
table[i]的头节点的key与要插入的key相同（通过hash值和equals()方法判断），则直接更新该节点的value。 - 键不存在，是链表：如果
table[i]是一个链表，则遍历链表：- 如果找到
key相同的节点，更新value。 - 如果遍历到链表尾部仍未找到相同的
key，则将新节点以尾插法（JDK 1.8）添加到链表末尾。 - 插入新节点后，检查链表长度是否达到
TREEIFY_THRESHOLD。如果达到，并且table.length >= MIN_TREEIFY_CAPACITY，则调用treeifyBin()方法将此链表转换为红黑树。
- 如果找到
- 键不存在，是红黑树：如果
table[i]已经是一个红黑树，则调用红黑树的插入方法（如putTreeVal()）将新节点插入到树中。如果树中已存在相同的key，则更新value。
- 键已存在：如果
- 桶为空：如果计算出的索引位置
- 更新
size和检查是否需要扩容：- 成功插入一个新节点后，
size（HashMap中键值对的数量）会加1。 - 然后检查
size是否超过了阈值threshold(threshold = capacity * loadFactor)。如果超过，则触发resize()扩容操作。
- 成功插入一个新节点后，
3. get(Object key) 方法的核心流程
- 计算哈希值和数组索引：与
put方法类似，先计算key的哈希值（包括扰动处理）和在table数组中的索引。 - 查找元素：
- 如果
table[i]为null，说明key不存在，返回null。 - 如果
table[i]的头节点的key与要查找的key相同，直接返回其value。 - 如果
table[i]是一个链表，则遍历链表，使用equals()方法比较每个节点的key，找到则返回value，遍历完未找到则返回null。 - 如果
table[i]是一个红黑树，则调用红黑树的查找方法（如getTreeNode()）来查找，找到则返回value，否则返回null。
- 如果
**4. 扩容机制 **resize()
- 触发条件：当
HashMap中的元素数量size超过threshold（capacity * loadFactor，默认loadFactor是0.75）时，或者初始化时（如果指定了初始容量，但内部table仍为null，则会在首次put时进行初始化扩容）。 - 过程：
- 创建新数组：通常，新的容量
newCapacity是旧容量oldCapacity的两倍。新的阈值newThreshold也会相应调整。 - 数据迁移 (Rehashing)：遍历旧的
table数组，将每个桶中的元素重新计算其在新table中的位置，并迁移过去。- 对于单个节点，直接计算新索引并放入。
- 对于链表：JDK 1.8 做了一个巧妙的优化。由于扩容是2倍，元素在新表中的位置要么在原索引
j，要么在原索引j + oldCapacity。可以通过(e.hash & oldCapacity) == 0来判断。这样可以将原链表拆分成两个子链表（一个低位链表，一个高位链表），分别放到新表的对应位置，避免了对每个元素都重新完整计算哈希索引。 - 对于红黑树：同样会进行节点拆分。如果拆分后，树中节点数少于
UNTREEIFY_THRESHOLD（默认为6），则可能会将红黑树退化回链表。
- 创建新数组：通常，新的容量
- 扩容是一个相对耗时的操作，因为它需要重新分配内存并迁移所有元素。
5. 与 JDK 1.7 的主要区别
- 底层数据结构：JDK 1.7 是数组 + 链表。JDK 1.8 是数组 + 链表 + 红黑树。引入红黑树是为了优化哈希冲突严重时链表过长导致的查询性能下降问题（从 O(N) 降到 O(logN)）。
- 链表插入方式：JDK 1.7 采用头插法，在并发环境下，多个线程同时
put且发生扩容时，可能导致链表形成环，从而在get时造成死循环。JDK 1.8 改为尾插法，避免了这个问题（但HashMap本身仍非线程安全）。 - 哈希计算：JDK 1.7 的扰动函数相对复杂一些，会进行多次位运算和异或。JDK 1.8 简化为高16位与低16位异或。
- 扩容时数据迁移：JDK 1.7 需要对每个元素重新计算哈希和索引。JDK 1.8 利用新旧容量是2倍关系，优化了迁移逻辑，如上所述。
6. 关键参数
initialCapacity：初始容量，默认为16。HashMap的容量总是2的幂次方。loadFactor：加载因子，默认为0.75。它决定了何时进行扩容。加载因子越小，空间浪费越多，但冲突概率越小；加载因子越大，空间利用率越高，但冲突概率越大，查询效率可能下降。TREEIFY_THRESHOLD: 8UNTREEIFY_THRESHOLD: 6MIN_TREEIFY_CAPACITY: 64
总结：
HashMap 通过哈希表实现了高效的键值对存取。JDK 1.8 的版本通过引入红黑树、优化哈希算法和扩容机制，进一步提升了其在各种情况下的性能和稳定性。但需要注意的是，HashMap 是非线程安全的，在并发环境下应使用 ConcurrentHashMap。同时，正确实现键对象的 hashCode() 和 equals() 方法对于 HashMap 的性能至关重要。”
了解的哈希冲突解决方法有哪些？
面试官您好，对于哈希冲突的解决方法，我了解到的主要有以下几种：
- 链接法 (Chaining / Separate Chaining)
- 这是最常用的一种方法，
HashMap在 JDK 1.7 及之前就是纯粹使用这种方法，JDK 1.8 中链表仍然是基础。 - 原理：当多个不同的键经过哈希函数计算后得到相同的哈希地址（即哈希桶索引）时，这些键值对不会直接覆盖，而是在这个哈希桶位置形成一个数据结构来存储所有冲突的元素。
- 具体实现：通常是使用链表。每个哈希桶对应一个链表的头指针。发生冲突的元素会依次追加到对应链表的尾部（或者头部，取决于具体实现）。
- Java 中的应用：
java.util.HashMap(链表+红黑树)，java.util.Hashtable(链表)。 - 优点：实现相对简单，删除操作也比较方便。对于均匀分布的哈希函数，性能表现良好。
- 缺点：如果哈希函数设计不当或数据本身特性导致大量冲突集中在少数几个桶，链表可能会变得很长，查询效率会从 O(1) 退化到 O(N)。这也是为什么 JDK 1.8 的
HashMap在链表过长时会转换为红黑树的原因，将查询优化到 O(logN)。
- 这是最常用的一种方法，
- 开放寻址法 (Open Addressing)
- 原理：当发生哈希冲突时，不是在原冲突位置创建链表，而是按照某种探测序列 (probe sequence) 在哈希表中寻找下一个可用的空闲位置来存储冲突的元素。所有的元素都直接存储在哈希表的数组中。
- 常见的探测方法：
- 线性探测 (Linear Probing)：从冲突位置开始，依次检查下一个相邻的空槽，直到找到一个空位。例如，
H(key, i) = (H'(key) + i) mod m，其中i是探测次数 (0, 1, 2, …)，m是表长。- 缺点：容易产生“一次聚集”（Primary Clustering）现象，即连续的已占用槽位会连成一片，使得后续冲突的元素需要探测更长的距离。
- 二次探测 (Quadratic Probing)：探测序列的步长是二次方增加的。例如，
H(key, i) = (H'(key) + c1*i + c2*i^2) mod m。- 优点：可以缓解线性探测的一次聚集问题。
- 缺点：可能会产生“二次聚集”（Secondary Clustering）。
- 双重散列 (Double Hashing / Re-Hashing探测)：使用第二个哈希函数来计算探测序列的步长。例如，
H(key, i) = (H'(key) + i * H''(key)) mod m。H''是另一个哈希函数。- 优点：是开放寻址法中效果较好的一种，能有效避免一次聚集和二次聚集，使得元素分布更均匀。
- 缺点：计算成本相对较高，因为需要执行两次哈希运算。
- 线性探测 (Linear Probing)：从冲突位置开始，依次检查下一个相邻的空槽，直到找到一个空位。例如，
- Java 中的应用：
ThreadLocalMap(ThreadLocal 的内部实现) 就使用了线性探测的开放寻址法。 - 优点：不需要额外的指针存储，节省空间。如果哈希表设计得当（例如，加载因子较低），缓存友好性可能更好。
- 缺点：删除操作比较复杂，通常需要标记为“已删除”而不是真正物理删除，否则会中断探测链。对加载因子比较敏感，当表接近满时，性能会急剧下降。
- 哈希表扩容 (Resizing / Rehashing the entire table)
- 这其实不是一种直接解决单次冲突的方法，而是一种降低整体冲突概率、维持哈希表性能的策略。当哈希表中元素数量达到一定程度（即加载因子超过阈值），冲突的概率会显著增加。
- 原理：创建一个更大的哈希表（通常是原大小的2倍），然后将旧表中的所有元素重新计算哈希值（基于新表的大小）并插入到新表中。
- Java 中的应用：
HashMap、ConcurrentHashMap等都会在适当的时候进行扩容。 - 优点：可以有效降低哈希冲突的概率，保持哈希表操作的平均时间复杂度接近 O(1)。
- 缺点：扩容操作本身是比较耗时的，因为它涉及到所有元素的重新迁移。
总结一下：
- 链接法和开放寻址法是两种最主要的直接解决哈希冲突的策略。
HashMap主要使用链接法（在 JDK 1.8 中结合红黑树优化）。- 开放寻址法有线性探测、二次探测、双重散列等具体实现。
- 哈希表扩容是一种间接的、全局性的冲突缓解机制，通过增大表空间来减少冲突。
在实际应用中，选择哪种冲突解决方法取决于具体的场景需求，比如对空间效率、时间效率、删除操作的复杂度以及实现复杂度等方面的权衡。
HashMap是线程安全的吗？
面试官您好，关于 HashMap 是否线程安全，答案是否定的，HashMap本身并不是线程安全的设计。如果在多线程环境下不加任何外部同步机制而直接操作 HashMap，可能会引发一系列问题。
具体来说，在多线程并发访问 HashMap 时，主要会遇到以下风险：
- JDK 1.7 及之前版本：
HashMap在这个版本使用的是“数组 + 链表”的数据结构。当多个线程同时进行put操作，并且这些操作恰好触发了数组扩容（resize） 时，问题尤为突出。- 链表成环导致死循环：在扩容过程中，元素从旧表迁移到新表时，采用的是头插法。并发迁移时，多个线程可能同时修改链表的指针，在极端情况下会导致链表形成环形结构。之后如果调用
get方法访问到这个环形链表，就会陷入死循环，导致 CPU 占用率飙升。 - 数据丢失：并发
put操作也可能导致某些本应成功插入的键值对丢失。例如，两个线程可能计算出相同的哈希桶索引，然后几乎同时尝试写入，后一个线程的写入可能会覆盖前一个线程刚写入的数据，或者在扩容过程中节点丢失。
- JDK 1.8 及以后版本：
HashMap在这个版本采用了“数组 + 链表 + 红黑树”的结构，并且在扩容时将链表迁移的头插法改为了尾插法。这个改动有效地解决了 JDK 1.7 中扩容导致的链表成环死循环问题。- 数据覆盖问题依然存在：尽管死循环问题被修复了，但
HashMap仍然不是线程安全的。例如，当多个线程并发执行put操作时，即使没有发生扩容，如果它们计算出的哈希桶索引相同，并且它们都判断该位置为空或者需要插入新节点，那么它们可能会竞争性地写入数据。由于put操作（比如++size、修改modCount、在链表或树中添加节点）并非原子操作，这可能导致一个线程的写入被另一个线程的写入所覆盖，从而造成数据丢失或不一致。- 比如
if (tab[i] == null)这个判断，两个线程可能同时判断为true，然后都去创建新节点并赋值给tab[i]，后完成的会覆盖先完成的。
- 比如
那么，如果需要在多线程环境中使用线程安全的 Map，我们有以下几种常见的解决方案：
Hashtable：- 这是 Java 早期提供的一个线程安全的
Map实现。它通过在几乎所有公开方法（如get,put,remove）上使用synchronized关键字来实现线程安全，锁的是整个Hashtable对象。 - 缺点：虽然线程安全，但由于锁的粒度非常大，导致并发性能极差，在高并发场景下会成为瓶颈。现在已不推荐使用。
- 这是 Java 早期提供的一个线程安全的
Collections.synchronizedMap(Map<K,V> m)：- 这个静态工厂方法可以将一个非线程安全的
Map（如HashMap）包装成一个线程安全的Map。 - 它的实现原理与
Hashtable类似，也是通过一个**全局锁（包装对象自身）**来同步所有对Map的访问。 - 缺点：与
Hashtable一样，性能表现不佳，不适合高并发。
- 这个静态工厂方法可以将一个非线程安全的
ConcurrentHashMap(推荐)：- 这是 JUC (java.util.concurrent) 包下提供的专为高并发设计的线程安全
Map，是目前多线程环境下Map的首选。 - JDK 1.7 版本：采用了分段锁 (Segment-based locking) 的技术。
ConcurrentHashMap内部由多个Segment组成，每个Segment继承自ReentrantLock并持有自己的HashEntry数组。写操作只锁定对应Segment，不同Segment上的操作可以并发执行，大大提高了并发度。默认有16个Segment。 - JDK 1.8 版本：实现有了重大改变，摒弃了
Segment的设计，转而采用更细粒度的锁机制，其底层结构类似于HashMap的“数组 + 链表 + 红黑树”。- 它主要通过
volatile保证共享变量的可见性，并大量使用 CAS (Compare-And-Swap) 操作来尝试无锁更新节点（例如，在链表或树中添加节点时）。 - 当 CAS 失败或需要进行某些原子性复合操作（如初始化哈希桶的头节点，或者链表转红黑树）时，会使用
synchronized关键字来锁定哈希桶的头节点。这个锁的粒度非常小，只影响当前操作的那个哈希桶，不同哈希桶的操作可以完全并发。 - 同样，在链表长度达到阈值时会转换为红黑树，以优化查询性能。
- 它主要通过
- 优点：
ConcurrentHashMap在保证线程安全的同时，提供了非常优秀的并发性能。
- 这是 JUC (java.util.concurrent) 包下提供的专为高并发设计的线程安全
总结来说，HashMap绝对不能在未加外部同步的多线程环境下直接使用。如果需要线程安全的 Map，ConcurrentHashMap是目前最佳的选择，因为它在性能和线程安全性之间取得了很好的平衡。
HashMap的put过程介绍一下
面试官您好，HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中，其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下：
- 初始判断与哈希计算：
- 首先，
putVal方法会检查当前的table（也就是内部的Node<K,V>[]数组）是否为null或者长度为0。如果是，则会调用resize()方法进行初始化扩容，分配一个默认大小（通常是16）的数组空间。 - 接下来，计算键
key的哈希值。- 如果
key为null，它有一个特殊的处理逻辑，hash会被置为0，并且通常会尝试将这个键值对放入table[0]的位置。 - 如果
key不为null，则调用key.hashCode()获取原始哈希码，然后通过一个扰动函数(h = key.hashCode()) ^ (h >>> 16)对哈希码进行处理。这样做是为了让哈希值的高16位也参与到后续的索引计算中，使得哈希分布更均匀，减少哈希冲突。
- 如果
- 首先，
- 计算数组索引 (定位哈希桶)：
- 使用经过扰动处理后的哈希值
hash与(table.length - 1)进行按位与&运算，即i = (n - 1) & hash（其中n是table的长度）。这个操作等效于hash % n，但位运算效率更高，前提是n必须是2的幂次方（HashMap的容量设计保证了这一点）。这样就确定了该键值对应该存储在table数组的哪个索引位置（哪个哈希桶）。
- 使用经过扰动处理后的哈希值
- 处理指定索引位置的情况：
- 令
p = table[i]，检查该哈希桶table[i]是否为空：- 情况一：哈希桶为空 (
p == null)- 如果该位置没有任何元素，说明没有发生哈希冲突。直接创建一个新的
Node(hash, key, value, null)对象，并将其放入table[i]位置。
- 如果该位置没有任何元素，说明没有发生哈希冲突。直接创建一个新的
- 情况二：哈希桶不为空 (
p != null)- 这表示发生了哈希冲突，或者找到了一个已存在的键。
- 首先检查头节点：判断桶的第一个节点
p的hash值是否与新键的hash值相同，并且通过key.equals(p.key)（或key == p.key）判断键是否相等。- 如果键完全相同，说明是更新操作。将旧值
p.value记录下来（用于putVal方法返回），然后用新的value替换p.value。操作结束。
- 如果键完全相同，说明是更新操作。将旧值
- 如果头节点不是目标键，则检查节点类型：
- 如果
p是TreeNode类型 (即该桶已经转化为红黑树)：- 调用红黑树的插入方法
p.putTreeVal(this, tab, hash, key, value)将新的键值对插入到红黑树中。如果树中已存在相同的键，则更新其值。
- 调用红黑树的插入方法
- 如果
p是普通的Node类型 (即该桶是链表结构)：- 遍历这个链表。在遍历过程中，使用
binCount计数链表长度（从1开始，因为头节点已经算一个）。 - 对于链表中的每个节点
e：- 如果
e.hash == hash并且e.key.equals(key)（或e.key == key），说明找到了相同的键，更新其值，操作结束。
- 如果
- 如果遍历到链表末尾（即
e.next = = null） 仍未找到相同的键：- 将新的键值对创建为一个新的
Node，并将其追加到链表的末尾（尾插法）。 - 插入新节点后，检查链表长度
binCount（此时binCount是插入前的长度，所以判断binCount + 1）是否达到了**树化阈值 **TREEIFY_THRESHOLD(默认为8)。- 如果达到了，并且当前
table的长度n大于等于MIN_TREEIFY_CAPACITY(默认为64)，则调用treeifyBin(tab, hash)方法将这个链表转换为红黑树。 - 如果
table长度小于MIN_TREEIFY_CAPACITY，则不会树化，而是会优先尝试resize()扩容。
- 如果达到了，并且当前
- 将新的键值对创建为一个新的
- 跳出链表遍历。
- 遍历这个链表。在遍历过程中，使用
- 如果
- 情况一：哈希桶为空 (
- 令
- 更新修改计数和大小：
- 如果成功插入了一个新的键值对（而不是更新已存在的键），
modCount（记录HashMap结构修改次数的变量，用于迭代器的 fail-fast 机制）会自增。 size（HashMap中存储的键值对数量）会自增。
- 如果成功插入了一个新的键值对（而不是更新已存在的键），
- 检查是否需要扩容：
- 在成功插入一个新节点后，会检查
++size是否大于threshold（capacity * loadFactor）。 - 如果大于
threshold，则调用resize()方法对HashMap进行扩容。扩容通常会将容量翻倍，并重新计算所有元素在新表中的位置。
- 在成功插入一个新节点后，会检查
- 返回值：
putVal方法（以及put方法）会返回与指定键关联的前一个值，如果该键之前没有映射关系，则返回null。
总结一下 put 过程的关键点：
- 计算哈希和索引。
- 处理哈希桶：空桶直接放；非空桶则判断是更新、链表追加还是红黑树插入。
- 链表过长且满足条件时会树化。
- 插入新元素后检查是否需要扩容。
- JDK 1.8 使用尾插法，并引入红黑树优化。
这个过程确保了 HashMap 在平均情况下能够提供 O(1) 的插入和查找性能，并在哈希冲突严重时通过红黑树将最坏情况下的性能维持在 O(logN)。
HashMap的put(key,val)和get(key)过程
面试官您好，关于 HashMap 的 put(key, value) 和 get(key) 过程，我的理解如下，这里主要以 JDK 1.8 及之后的版本为基础：
一、 put(K key, V value) 过程 (存储对象)
跟上一个问题一样。
二、 get(Object key) 过程 (获取对象)
- 计算哈希值与数组索引：
- 与
put过程类似，首先对传入的key计算其哈希值（包括扰动处理），然后通过(n - 1) & hash计算出它在table数组中的索引i。
- 与
- 查找元素：
- 获取
table[i]处的节点，我们称之为firstNode。 - 桶为空或首节点匹配：
- 如果
firstNode为null，说明key不存在，返回null。 - 如果
firstNode的hash与目标key的hash相同，并且通过key.equals(firstNode.key)（或==）判断key也相等，那么firstNode就是要找的节点，返回其value。
- 如果
- 桶不为空且首节点不匹配 (处理冲突)：
- 如果
firstNode.next不为null（即桶中有多个元素），则需要进一步查找：- 如果
firstNode是一个TreeNode(红黑树)，则调用红黑树的查找方法（如getTreeNode()）在树中高效地查找目标key。如果找到，返回其value；否则返回null。 - 如果
firstNode是一个普通的Node(链表)，则遍历链表，对链表中的每个节点，依次比较其hash和key（通过equals()）是否与目标key匹配。如果找到匹配的节点，返回其value。如果遍历完整个链表都未找到，则返回null。
- 如果
- 如果
- 获取
总结关键点：
put和get都依赖于key的hashCode()和equals()方法。hashCode()用于快速定位桶，equals()用于在发生哈希冲突时精确匹配键。因此，正确实现这两个方法对于HashMap的正确性和性能至关重要。- JDK 1.8 引入了红黑树来优化哈希冲突严重时链表过长导致的查询性能下降问题。当链表长度超过一定阈值（默认为8）且总容量足够大时，链表会转换为红黑树，将查询时间复杂度从最坏的 O(N) 降低到 O(logN)。
- 加载因子 (Load Factor) 和扩容 (resize) 机制是为了在空间利用率和查找效率之间取得平衡。
理解这两个核心过程，就能很好地掌握 HashMap 的工作原理了。
HashMap调用get方法一定安全吗？
面试官您好，关于 HashMap 调用 get 方法是否一定安全，我的理解是：不一定，需要看具体场景。 主要有以下几点需要注意：
- 空指针异常 (NullPointerException) 的可能性：
HashMap实例本身为null：正如您提到的，如果HashMap对象本身还没有被初始化（即map变量是null），那么调用map.get(key)无论key是什么，都会直接抛出NullPointerException。这是 Java 中对任何null对象引用调用方法时的普遍行为，并非HashMap.get()特有。key参数为null：HashMap是允许null作为键（key）的（最多一个null键）。所以，如果HashMap实例本身不是null，那么调用map.get(null)是完全合法的。它会返回与null键关联的值；如果null键不存在，则返回null。在这种情况下，get(null)本身不会抛出 NPE。- 自定义键对象的
hashCode()或equals()中潜在的 NPE：这是一个更隐蔽的情况。如果在get(key)过程中，key对象不为null，但在其hashCode()或equals()方法内部（如果HashMap需要调用它们来比较键）访问了该对象的某个null成员变量而没有做空检查，可能会间接导致 NPE。但这更多是键对象自身实现的问题，而非HashMap.get()的直接问题。
- 线程安全问题 (核心)：
HashMap本身是非线程安全的。如果在多线程环境中，没有进行正确的外部同步，那么即使是看似简单的get操作也可能不安全。- 数据可见性问题：一个线程通过
put修改了HashMap，如果没有适当的内存屏障（volatile或synchronized），另一个线程通过get可能读取到的是旧的、过时的数据，甚至根本看不到新写入的数据。 - 读取到不一致的状态：如果一个线程正在执行
get操作，而另一个线程同时在对HashMap进行结构性修改（例如put一个新元素导致了resize扩容，或者remove元素），get操作可能会读取到HashMap内部数据结构在修改过程中的一个不一致的、甚至是损坏的状态。这可能导致：- 返回错误的结果（比如返回
null但实际上键存在，或者返回了错误的值）。 - 在 JDK 1.7 及之前版本，如果一个线程正在
get，而另一个线程触发了resize，由于头插法和并发问题，get操作在遍历链表时甚至可能陷入死循环，导致CPU飙升。 - 在 JDK 1.8 版本，虽然
resize导致的死循环问题通过尾插法解决了，但并发读写依然可能导致get读取到中间状态的数据或不正确的数据。
- 返回错误的结果（比如返回
ConcurrentModificationException(CME)：虽然get操作本身通常不会直接抛出 CME（CME 主要与迭代器在迭代过程中集合被修改有关），但并发修改可能导致内部状态损坏，如果后续使用迭代器，则可能触发 CME。更直接的风险是上面提到的数据不一致和死循环（JDK 1.7）。
总结与建议：
- 对于单线程环境，只要
HashMap实例本身不是null，且键对象的hashCode()和equals()实现正确，get(key)操作通常是安全的。 - 对于多线程环境，直接使用
HashMap的get操作是不安全的。为了保证线程安全，应该：- 使用
Collections.synchronizedMap(new HashMap<>())进行包装，但这会牺牲并发性能，因为它对所有操作都进行全局同步。 - **推荐使用 **
java.util.concurrent.ConcurrentHashMap。它是专为高并发设计的线程安全Map实现，通过更细粒度的锁（如 JDK 1.7 的分段锁或 JDK 1.8 的 CAS + synchronized 锁桶头节点）来提供更好的并发性能。ConcurrentHashMap的get操作通常是无锁的（依赖volatile读取），并且能够容忍并发修改，保证能获取到某个一致性时间点的数据。
- 使用
因此，回答‘HashMap 的 get 是否安全’时，关键在于明确‘安全’的上下文，尤其要强调在多线程环境下的不安全性以及推荐的替代方案。
HashMap一般用什么做Key？为啥String适合做Key呢？
面试官您好，关于 HashMap 一般用什么做 Key，以及为什么 String 特别适合，我的理解是这样的：
一、HashMap的Key的一般选择原则：
理论上，任何 Java 对象都可以作为 HashMap 的 Key，但为了保证 HashMap 能够正确和高效地工作，作为 Key 的对象应该满足以下几个关键要求：
- 正确实现
hashCode()和equals()方法：hashCode()：用于快速定位Key在HashMap内部数组中的存储位置（哈希桶）。equals()：当发生哈希冲突（即多个不同的Key经过hashCode()计算后得到相同的哈希桶索引）时，用于精确判断两个Key是否“相等”，从而确定是更新现有值还是添加新条目。- 一致性要求：
- 如果
a.equals(b)为true，那么a.hashCode()必须等于b.hashCode()。 - 如果
a.hashCode()不等于b.hashCode()，那么a.equals(b)必须为false。 - （注意：
a.hashCode()等于b.hashCode()，a.equals(b)不一定为true，这就是哈希冲突）。 - 在一个 Java 应用的多次执行中，只要对象的
equals比较所用的信息没有被修改，那么对这同一个对象调用hashCode方法，它必须始终返回同样的一个整数。
- 如果
- 不可变性 (Immutability) - 非常重要：
- 这是理想的
Key对象应该具备的特性。如果一个可变对象作为Key，并且在其存入HashMap之后，其参与hashCode()或equals()计算的状态发生了改变，那么：hashCode()的值可能会改变，导致HashMap无法再通过原来的哈希值找到这个Key（它可能被放到了错误的桶里，或者说，get(key)时计算出的新哈希值会定位到错误的桶）。equals()的比较结果也可能改变，导致逻辑错误。
- 即使能找到，如果
hashCode变了，HashMap内部的结构（比如链表或红黑树中的顺序）也可能不再正确。
- 这是理想的
二、为什么 String 特别适合做 Key：
String 类被广泛用作 HashMap 的 Key，主要因为它完美地符合了上述要求，特别是不可变性：
- 不可变性 (Immutability)：
String对象一旦被创建，其内部的字符序列（char[] value）就不能被修改。任何对String的“修改”操作（如concat,substring,replace等）实际上都会创建一个新的String对象。- 确保稳定性：由于
String的不可变性，一旦一个String对象作为Key存入HashMap，它的hashCode()值在其生命周期内就永远不会改变，equals()的比较结果也不会因为对象状态变化而变化。这保证了HashMap能够始终如一地、正确地定位和检索到与该StringKey关联的值。
- 正确且高效地实现了
hashCode()和equals()：String类重写了Object的hashCode()和equals()方法。String.hashCode()：它的计算是基于字符串内容的，能够为不同的字符串内容生成（尽可能）不同的哈希码，分布也相对均匀。并且，为了性能，String对象内部会缓存其计算好的hashCode值（private int hash;），第一次调用hashCode()时计算并缓存，后续调用直接返回缓存值，避免了重复计算。String.equals()：它比较的是两个字符串的内容是否相同。
- 广泛使用和直观性：
String是 Java 中最常用的数据类型之一，用字符串作为键来标识和检索数据非常自然和直观。
其他适合做 Key 的类型：
- 基本数据类型的包装类：如
Integer,Long,Double,Boolean等。这些包装类也都是不可变的，并且正确实现了hashCode()和equals()。 - 自定义的不可变类：如果我们创建自定义类作为
Key，强烈建议将其设计为不可变类，并确保正确重写hashCode()和equals()。例如，一个Point类，如果其x和y坐标在创建后不再改变，就可以设计为不可变并作为Key。
不推荐的情况：
- 可变的自定义对象：如果一个自定义对象是可变的，并且其参与
hashCode()或equals()计算的字段在对象存入HashMap后可能发生改变，那么这个对象就不适合直接作为Key。如果必须使用，需要特别小心，确保在它作为Key期间其关键状态不被修改，或者在修改后将其从Map中移除再重新插入（但这通常是糟糕设计的信号）。 - 数组：数组默认的
hashCode()是基于对象内存地址的，equals()比较的是引用。除非你对数组的这种行为有特定需求，否则直接用数组做Key往往不是期望的结果。通常会使用List(特别是不可变的List如List.of()) 或者自定义包含数组内容的不可变包装类。
综上所述，String 因其不可变性和良好实现的 hashCode/equals 方法，成为了 HashMap Key 的理想选择之一。在选择或设计自定义 Key 类型时，也应优先考虑这些特性。
为什么HashMap要用红黑树而不是平衡二叉树？
面试官您好，关于 HashMap 在链表过长时选择使用红黑树而不是像 AVL 树这样的“严格”平衡二叉树，主要原因在于性能和维护成本之间的权衡，尤其是在频繁插入和删除的场景下，红黑树能提供更好的综合性能。
具体来说，可以从以下几个方面理解：
平衡要求的差异与维护成本：
平衡二叉树 (AVL Tree)：AVL 树追求的是一种**“严格”或“完全”的平衡**。它要求任何节点的左右子树高度差不能超过1。这个严格的约束使得 AVL 树在查找时非常高效，因为树的高度始终保持在最小的 O(log N) 级别。
- 维护成本高：但也正因为这个严格的平衡要求，每次进行插入或删除节点时，AVL 树非常容易失去平衡（即破坏高度差不超过1的规则）。因此，它需要频繁地进行旋转操作（左旋、右旋） 来恢复平衡。这些旋转操作本身是有开销的，在写操作（插入、删除）频繁的场景下，这种维护成本可能会变得很高，甚至抵消掉部分查找性能的优势。
红黑树 (Red-Black Tree)：红黑树则不追求这种绝对的平衡，它是一种 “弱平衡”或“大致平衡”的二叉搜索树。它通过满足以下五条性质来确保其平衡性：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL 节点，通常是外部空节点）都是黑色。【根叶黑】
- 如果一个节点是红色的，则它的两个子节点都是黑色的（即不能有连续的红色节点）。【不红红】
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。【黑路同】
- 这条性质保证了最长路径（可能是一串红黑交替）不会超过最短路径（全是黑色节点）的两倍。这意味着红黑树的高度也大致维持在 O(log N) 级别，虽然可能比 AVL 树略高一点，但查找效率仍然是 O(log N)。
- 维护成本相对较低：红黑树的平衡约束相对宽松。在插入或删除节点时，它可能不会像 AVL 树那样频繁地破坏平衡规则。即使破坏了规则，其调整（通过变色和旋转）的次数和复杂度通常也比 AVL 树要少。它通过允许一定程度的“不平衡”来换取更低的维护成本。
HashMap 场景下的考量：
HashMap的主要操作是put(插入/更新) 和get(查找)。当哈希冲突严重导致链表过长时，引入树结构是为了优化这些操作的性能。- 写操作的频率：在很多
HashMap的使用场景中，插入和删除操作是比较常见的。如果选择 AVL 树，频繁的写操作可能导致大量的旋转，影响整体吞吐量。 - 统计上的平衡性：虽然单个哈希桶可能会因为特定数据分布而变得不平衡，但从整个
HashMap的角度看，良好的哈希函数通常能使得大部分桶的元素数量较少，真正需要树化的情况是少数。对于这些少数需要树化的桶，我们希望在保证 O(log N) 查找的同时，插入和删除的开销尽可能小。 - “够用就好”的工程原则：红黑树提供的 O(log N) 查找性能对于
HashMap来说已经足够好了（相比于链表的 O(N) 是巨大的提升）。为了追求 AVL 树那一点点理论上可能更优的查找高度（实践中差异可能不大），而付出更高的写操作维护成本，在工程上可能并不划算。红黑树在查找效率和维护效率之间提供了一个更好的折中。
实现的复杂度：
- 虽然两者都是复杂的平衡树，但一般认为红黑树的旋转和颜色调整逻辑在某些情况下比 AVL 树的旋转逻辑稍微复杂一些，不过这不是主要决策因素。更重要的是它们在动态操作下的平均性能表现。
总结来说，HashMap选择红黑树，是因为它在保持 O(log N) 查找效率的同时，其插入和删除操作的平均维护成本（调整次数和复杂度）通常低于 AVL 树。这使得红黑树在写操作也比较频繁的动态数据集合（如 HashMap 的哈希桶）中，能够提供更稳定和高效的整体性能。这是一种典型的工程上的权衡，牺牲了一点点的“完美平衡”以换取更低的动态维护开销。
HashMap key可以为null吗？
面试官您好，关于 HashMap 的 key 是否可以为 null，答案是可以的，HashMap明确支持将 null 作为键（key）。
具体来说，有以下几点需要注意：
null键的处理机制：- 当我们将
null作为key传递给put或get等方法时，HashMap内部并不会尝试调用null.hashCode()（因为这会抛出NullPointerException）。 - 在
HashMap内部计算哈希值的方法（例如 JDK 8 中的static final int hash(Object key)）中，有一个明确的判断：
- 当我们将
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从这段代码可以看出，如果 key 等于 null，它的哈希值会被直接视为0。这意味着所有 null 键都会被映射到哈希表（Node[] table）的第0个桶（table[0]）中（因为索引计算是 (n-1) & hash，当 hash 为0时，索引自然是0）。
null键的唯一性：HashMap中，null键只能有一个。- 这是因为
HashMap的基本特性是键的唯一性。当我们put(key, value)时，如果key已经存在，新的value会覆盖旧的value。对于null键也是如此。第一次put(null, value1)会成功插入；如果之后再put(null, value2)，那么与null键关联的值就会被更新为value2。
value可以为null且可以有多个：- 与
key不同，HashMap允许value为null。 - 并且，多个不同的
key可以关联到null值。例如，map.put("key1", null)和map.put("key2", null)都是允许的。
- 与
- 与其他
Map实现的对比：- 值得注意的是，并非所有的
Map实现都支持null键。例如，Hashtable就不允许null作为键或值，尝试put(null, ...)或put(..., null)都会抛出NullPointerException。 TreeMap默认情况下也不允许null键（除非其构造时传入的Comparator明确支持对null的比较）。ConcurrentHashMap在 JDK 1.8 及以后版本中，与Hashtable类似，也不允许null作为键或值。
- 值得注意的是，并非所有的
总结一下：
HashMap 是允许 key 为 null 的，并且最多只能有一个 null 键。内部机制会将 null 键的哈希值视为0。同时，value 也可以为 null，并且可以有多个。在选择 Map 实现时，是否需要支持 null 键和/或 null 值是一个需要考虑的因素。
重写HashMap的equal方法不当会出现什么问题？
面试官您好，当我们自定义一个类并打算用其实例作为 HashMap 的 Key 时，正确地重写这个自定义类的 equals() 和 hashCode() 方法至关重要。HashMap 依赖这两个方法来正确存储和检索键值对。如果它们没有被正确实现，会导致 HashMap 行为异常，比如无法找到已存入的元素，或者错误地覆盖元素。
重写 equals() 和 hashCode() 方法时需要注意以下关键点和规则：
equals()方法的实现要点：- 自反性 (Reflexive)：对于任何非
null的引用值x，x.equals(x)必须返回true。 - 对称性 (Symmetric)：对于任何非
null的引用值x和y，当且仅当y.equals(x)返回true时，x.equals(y)必须返回true。 - 传递性 (Transitive)：对于任何非
null的引用值x、y和z，如果x.equals(y)返回true，并且y.equals(z)返回true，那么x.equals(z)必须返回true。 - 一致性 (Consistent)：对于任何非
null的引用值x和y，只要equals的比较操作在对象中所用的信息没有被修改，多次调用x.equals(y)就会一致地返回true，或者一致地返回false。这也是为什么**推荐使用不可变对象作为 **Key的原因之一。如果Key是可变的，并且其参与equals()比较的字段在对象存入HashMap后发生了改变，就可能破坏一致性。 - 非空性：对于任何非
null的引用值x，x.equals(null)必须返回false。 - 类型检查：在
equals()方法的开始，通常会进行类型检查，确保比较的对象是相同类型或兼容类型的实例。例如，使用instanceof。 - 字段比较：
equals()方法的核心是比较对象的关键字段是否都相等。这些字段应该是能够唯一标识对象状态的字段。
- 自反性 (Reflexive)：对于任何非
hashCode()方法的实现要点：- 一致性：在一个 Java 应用的多次执行中，只要对象的
equals比较所用的信息没有被修改，那么对这同一个对象调用hashCode方法，它必须始终返回同样的一个整数。 - 参与计算的字段：
hashCode()的计算应该基于那些参与equals()方法比较的字段。如果一个字段在equals()中被用来判断相等性，那么它也应该被用来计算hashCode()。 - 分散性：理想情况下，
hashCode()方法应该为不相等的对象生成不同的哈希码，即哈希码应尽可能均匀地分布。这有助于减少HashMap中的哈希冲突，提高性能。常用的做法是将各个关键字段的哈希值通过某种方式（如乘以一个素数再相加）组合起来。
- 一致性：在一个 Java 应用的多次执行中，只要对象的
equals()和hashCode()之间的黄金法则 (核心约束)：- 规则1：如果
o1.equals(o2)返回true，那么o1.hashCode()必须等于o2.hashCode()。- 这是至关重要的。如果两个对象通过
equals()判断是相等的，但它们的hashCode()不同，那么当它们作为Key存入HashMap时，它们可能会被放到不同的哈希桶中。这样，即使逻辑上它们是同一个Key，HashMap也可能认为它们是不同的，导致get()操作可能找不到预期的值，或者同一个逻辑Key可能会被重复插入。
- 这是至关重要的。如果两个对象通过
- 规则2：如果
o1.hashCode()等于o2.hashCode()，o1.equals(o2)不一定为true。- 这描述的就是哈希冲突。不同的对象完全可能拥有相同的哈希码。在这种情况下，
HashMap会通过调用equals()方法来进一步区分它们，并将它们（如果equals()返回false）存储在同一个哈希桶的链表或红黑树中。
- 这描述的就是哈希冲突。不同的对象完全可能拥有相同的哈希码。在这种情况下，
- 规则1：如果
总结来说，当我们自定义类作为 HashMap 的 Key 时：
- 必须同时重写
equals()和hashCode()。 只重写一个通常会导致HashMap工作不正常。 - 确保
equals()满足其通用约定（自反、对称、传递、一致、非空）。 - 确保
hashCode()的计算与equals()中使用的字段保持一致，并且满足上述两条黄金法则。 - 强烈推荐将用作
Key的自定义类设计为不可变的，以避免在对象存入HashMap后其状态改变导致hashCode()或equals()的行为不一致。
例如，IDE（如 IntelliJ IDEA, Eclipse）通常提供了自动生成符合规范的 equals() 和 hashCode() 方法的功能，这在实际开发中非常有用，但理解其背后的原理仍然很重要。
列举HashMap在多线程下可能会出现的问题？
面试官您好，HashMap 本身并非线程安全的设计，在多线程环境下并发操作时，如果不加任何外部同步措施，可能会引发一系列严重问题。主要可以归纳为以下几点：
- 数据竞争与不一致性 (Data Races and Inconsistent State)：
- 数据覆盖/丢失：正如您指出的，这是 JDK 1.7 和 JDK 1.8 中都存在的问题。当多个线程同时执行
put操作，并且它们计算出的哈希桶索引恰好相同时：- 它们可能会几乎同时读取到该桶的当前状态（比如都发现桶是空的，或者都需要在链表/树中添加新节点）。
- 由于
put操作内部的多个步骤（如检查键是否存在、创建新节点、链接节点、更新size和modCount等）并非原子性的，一个线程的操作可能会被另一个线程的操作打断或覆盖。 - 最直接的结果就是，后完成
put操作的线程可能会覆盖掉先完成线程写入的数据，导致前一个键值对丢失。
- 读取到脏数据或中间状态：一个线程正在修改
HashMap（比如执行put或remove，尤其是涉及到扩容resize时），另一个线程同时执行get操作，可能会读取到HashMap内部数据结构在修改过程中的一个不一致的、甚至是损坏的中间状态，导致返回错误的结果（比如返回null但实际上键存在，或者返回了错误的值）。 size和modCount不准确：并发修改可能导致HashMap内部记录元素数量的size变量和记录结构修改次数的modCount（用于迭代器的 fail-fast 机制）变得不准确。
- 数据覆盖/丢失：正如您指出的，这是 JDK 1.7 和 JDK 1.8 中都存在的问题。当多个线程同时执行
- JDK 1.7 特有的风险：扩容时链表成环导致死循环：
- 在 JDK 1.7 及更早版本中，
HashMap在扩容（resize）并将元素从旧表迁移到新表时，对于链表中的节点采用的是头插法。 - 当多个线程同时检测到需要扩容并都参与到扩容过程中时，它们可能会并发地修改同一个链表的指针。在特定的执行序列下（例如，线程A读取了节点X和Y的next指针，然后线程B也操作了这些节点并改变了它们的next指针，之后线程A再继续执行），这可能导致链表形成一个环形结构。
- 一旦链表成环，后续的
get操作如果访问到这个环形链表，就会陷入无限循环，导致 CPU 占用率飙升，应用程序卡死。
- 在 JDK 1.7 及更早版本中，
- JDK 1.8 的改进与依然存在的问题：
- JDK 1.8 对
HashMap做了重要改进：- 在扩容时，链表迁移改用了尾插法。这能保持元素在链表中的相对顺序，从而有效地避免了 JDK 1.7 中因头插法导致的链表成环死循环问题。
- 引入了红黑树来优化哈希冲突严重时链表的性能。
- 但
HashMap在 JDK 1.8 中仍然是非线程安全的。前面提到的数据覆盖/丢失问题、读取到脏数据或中间状态的问题，在 JDK 1.8 的并发put或put与get并发等场景下依然存在，因为其核心操作仍然不是原子性的，也没有内部的并发控制机制。
- JDK 1.8 对
ConcurrentModificationException(CME) 的风险：- 虽然不是直接由并发
put/get引起，但如果一个线程正在通过迭代器（Iterator）遍历HashMap，而另一个线程同时对HashMap进行了结构性修改（添加、删除元素，或者触发了扩容），那么迭代器在下一次调用next()或hasNext()时，很可能会抛出ConcurrentModificationException。这是HashMapfail-fast 机制的表现。
- 虽然不是直接由并发
总结来说，在多线程环境下，HashMap可能出现的主要问题包括：
- 数据丢失或覆盖。
- 读取到不一致或错误的数据。
- 在 JDK 1.7 中，扩容时可能导致链表成环，引发死循环。 (JDK 1.8 已解决此特定问题)
- 迭代时可能抛出
ConcurrentModificationException。
因此，在并发场景下，必须使用线程安全的 Map 实现，例如 java.util.concurrent.ConcurrentHashMap，或者对 HashMap 的访问进行严格的外部同步（如使用 Collections.synchronizedMap 或显式锁），但后者通常性能较差。
HashMap的扩容机制介绍一下
面试官您好，HashMap 的扩容机制是其保证性能和空间利用率平衡的关键部分，这个过程主要在内部的 resize() 方法中实现。
1. 触发扩容的条件：
HashMap 的扩容主要由两个因素决定：当前存储的键值对数量 (size) 和 加载因子 (loadFactor)。
- 阈值 (
threshold)：HashMap内部有一个threshold成员变量，它的值等于capacity * loadFactor。其中capacity是当前哈希表的容量（即内部Node[] table数组的长度），loadFactor是加载因子（默认为0.75）。 - 触发时机：
- 主要时机：在每次成功调用
putVal()方法（即成功插入一个新的键值对后，size会加1）之后，HashMap会检查++size > threshold。如果条件成立，就会调用resize()方法进行扩容。 - 初始化时机：如果通过构造函数创建
HashMap时指定了初始容量initialCapacity，但在内部table数组实际被分配之前（例如，首次调用put时），也会调用resize()来根据这个initialCapacity初始化table并计算相应的threshold。如果构造时未指定容量，则使用默认初始容量（16）和默认加载因子（0.75）在首次put时进行初始化扩容。
- 主要时机：在每次成功调用
2. resize() 方法的核心步骤：
当 resize() 方法被调用时，它会执行以下操作（以 JDK 1.8+ 为例）：
- 保存旧数据：保存旧的
table数组引用 (oldTab)、旧的容量 (oldCap) 和旧的阈值 (oldThr)。 - 计算新容量和新阈值：
- 新容量 (
newCap)：- 如果
oldCap > 0（即不是初始化，而是扩容）：newCap通常会是oldCap << 1，即旧容量的两倍。 - 但是，如果旧容量已经达到了
MAXIMUM_CAPACITY（通常是1 << 30，即2的30次方），则newCap会保持为MAXIMUM_CAPACITY，并且newThr会被设置为Integer.MAX_VALUE，表示不再扩容。 - 如果
oldCap == 0且oldThr > 0（即通过带参构造函数指定了初始容量，但尚未初始化table）：newCap会被设置为oldThr（此时oldThr存储的是初始容量）。 - 如果
oldCap == 0且oldThr == 0（即使用无参构造函数，完全初始化）：newCap会被设置为DEFAULT_INITIAL_CAPACITY（16），newThr会被设置为(float)DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR。
- 如果
- 新阈值 (
newThr)：- 在容量成功翻倍后，如果
newCap < MAXIMUM_CAPACITY并且newCap大于等于DEFAULT_INITIAL_CAPACITY，newThr通常也会是oldThr << 1（旧阈值的两倍），或者根据新的容量和加载因子重新计算newThr = (int)(newCap * loadFactor)。 - 如果
newCap是通过oldThr（初始容量）设置的，那么newThr会根据newCap和loadFactor计算。
- 在容量成功翻倍后，如果
- 新容量 (
- 创建新的
table数组：根据计算得到的newCap，创建一个新的Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]。HashMap内部的table引用会指向这个newTab。 - 数据迁移 (Rehashing)：这是扩容中最核心且耗时的部分。需要遍历旧的
oldTab中的所有元素，并将它们重新计算哈希位置后放入新的newTab中。- 遍历
oldTab的每个哈希桶。 - 如果桶不为空（即
oldTab[j] != null）：- 令
e = oldTab[j]。将oldTab[j]置为null以帮助 GC。 - 如果桶中只有一个元素（即
e.next == null）：直接计算e在newTab中的新索引(newCap - 1) & e.hash，并将其放入对应位置。 - 如果桶中是红黑树 (
TreeNode)：调用树节点的split()方法。这个方法会根据节点哈希值与oldCap的关系，将原来的红黑树拆分成两个子树（一个低位树，一个高位树）。如果拆分后树中节点数少于UNTREEIFY_THRESHOLD（默认为6），则可能会将红黑树退化回链表。然后将这两个（可能退化后的）结构分别放到newTab的j和j + oldCap位置。 - 如果桶中是链表：JDK 1.8 在这里做了一个非常巧妙的优化。由于新容量是旧容量的2倍，元素在新表中的位置要么保持在**原索引
j，要么移动到原索引 **j + oldCap。- 具体判断依据是
(e.hash & oldCap) == 0。如果为true，则元素在新表中的索引仍然是j；如果为false，则新索引是j + oldCap。 - 遍历原链表，根据这个判断条件，将原链表拆分成两个新的子链表：一个“低位”链表（
loHead,loTail）和一个“高位”链表（hiHead,hiTail）。 - 最后，将低位链表放在
newTab[j]，高位链表放在newTab[j + oldCap]。这个过程保持了原链表中元素的相对顺序（因为是尾插法构建新链表）。
- 具体判断依据是
- 令
- 遍历
5. 更新threshold：将 HashMap 内部的 threshold 成员变量更新为计算得到的 newThr。
扩容机制的意义和影响：
- 性能与空间的平衡：通过扩容，
HashMap可以在元素数量增加时，动态调整其内部数组的大小，以期将平均每个哈希桶中的元素数量（链表长度或树的规模）控制在一个较小的范围内，从而维持get和put操作的平均 O(1) 时间复杂度（对于树化的情况是 O(logN)）。 - 加载因子的作用：
loadFactor控制了扩容的“积极性”。- 较小的
loadFactor（如0.5）意味着HashMap会在内部数组填充较少时就进行扩容，导致空间利用率较低，但哈希冲突的概率也较小，查找性能可能更好。 - 较大的
loadFactor（如0.9）意味着空间利用率较高，但哈希冲突的概率也较大，可能导致链表更长或更早树化，查找性能可能下降。默认的0.75被认为是时间和空间成本之间的一个较好折中。
- 较小的
- 性能开销：
resize()操作本身是比较耗时的，因为它需要创建新数组并遍历所有旧元素进行重新哈希和迁移。因此，如果能预估到HashMap将要存储的元素数量，在创建HashMap时通过构造函数new HashMap<>(initialCapacity)指定一个合适的初始容量，可以有效地减少不必要的自动扩容次数，从而提升性能。
总结来说，HashMap 的扩容机制是一个动态调整内部哈希表大小的过程，通过将容量翻倍并在 JDK 1.8 中优化数据迁移逻辑，来应对元素数量的增长，以维持其高效的性能。
HashMap的大小为什么是2的次幂呢？
HashMap 的容量（即内部 table 数组的大小）设计为2的n次方，主要是为了以下几个核心原因：
- 优化哈希值到数组索引的计算，提高效率 (最主要原因)：
- 当
HashMap需要将一个键的哈希值映射到table数组的某个索引位置时，它使用的计算公式是index = hash & (length - 1)，其中length是table数组的长度。 - 如果
length是2的n次方，那么length - 1的二进制表示就会是n个连续的1（例如，如果length是16 (二进制10000)，那么length - 1就是15 (二进制01111)）。 - 在这种情况下，
hash & (length - 1)这个位与运算就等价于hash % length(取模运算)。 - 关键在于，位与运算 (
&) 的效率通常比取模运算 (%) 要高得多。CPU 执行位运算指令通常比执行除法和取模指令更快。通过将容量设计为2的n次方，HashMap可以用更高效的位运算来代替取模运算，从而在每次put、get、remove等操作中定位哈希桶时都能获得性能提升。
- 当
- 方便扩容时元素的重新分配 (Rehashing Optimization)：
- 当
HashMap扩容时，新的容量通常是旧容量的两倍（仍然是2的n次方）。 - 例如，旧容量
oldCap，新容量newCap = oldCap * 2。 - 对于一个元素，它在旧表中的索引是
hash & (oldCap - 1)。 - 在 JDK 1.8 中，扩容时元素在新表中的位置只有两种可能：
- 要么在原索引位置。
- 要么在原索引位置 +
oldCap的位置。
- 这个判断可以通过
(hash & oldCap) == 0来高效地完成：- 如果
(hash & oldCap) == 0，则元素在新表中的索引不变。 - 如果
(hash & oldCap) != 0(即为1，因为oldCap是2的幂，其二进制只有一个1)，则元素在新表中的索引是原索引 + oldCap。
- 如果
- 这种优化之所以能成立，正是因为容量是2的n次方。
oldCap的二进制表示中只有一个位是1（比如16是00010000）。hash & oldCap实际上是在检查hash值在对应oldCap的那个“1”位上的值是0还是1。这个位在扩容后newCap - 1的掩码中会被包含进来，从而决定了元素是留在低位桶还是移动到高位桶。 - 这种方式避免了对每个元素都重新进行完整的
hash & (newCap - 1)计算，简化了数据迁移逻辑，提高了扩容效率。
- 当
- 保证哈希值的均匀分布：
- 当使用
hash & (length - 1)计算索引时，如果length是2的n次方，那么length - 1的低n位都是1。这意味着hash值的所有低n位都会参与到索引的计算中。 HashMap内部还会对key.hashCode()的结果进行一个扰动函数（如(h = key.hashCode()) ^ (h >>> 16)）处理，目的是让哈希值的高位也能影响到低位的计算结果，进一步增加哈希值的随机性和均匀性。- 结合扰动函数和2的n次方容量，
HashMap致力于将元素尽可能均匀地分布到各个哈希桶中，以减少哈希冲突，提高整体性能。如果容量不是2的n次方，某些哈希桶被选中的概率可能会不均匀，导致冲突增多。
- 当使用
总结来说，HashMap的大小（容量）设计为2的n次方，主要是为了：
- 使用高效的位与运算
&代替取模运算%来计算数组索引，提升性能。 - 在扩容时能够利用这一特性进行优化的数据迁移，提高扩容效率。
- 有助于哈希值的均匀分布，减少哈希冲突。
往HashMap存20个元素，会扩容几次？
面试官您好，如果往一个使用默认参数创建的 HashMap 中存入20个元素，它会发生1次扩容。我们可以详细分析一下这个过程：
- 初始状态与阈值计算：
- 当我们创建一个不指定初始容量的
HashMap时，它会使用默认的初始容量，即DEFAULT_INITIAL_CAPACITY = 16。 - 默认的加载因子
DEFAULT_LOAD_FACTOR是0.75f。 - 因此，
HashMap初始的扩容阈值threshold计算为capacity * loadFactor = 16 * 0.75 = 12。这意味着当HashMap中存储的元素数量（size）超过12时，就会触发扩容。
- 当我们创建一个不指定初始容量的
- 第一次达到阈值前的插入过程：
- 当我们依次存入第1个到第12个元素时，
HashMap的size会从1增长到12。 - 在每次
put操作成功插入一个新元素后，size会自增，并检查size > threshold。在这个阶段，size不会大于12，所以不会触发扩容。
- 当我们依次存入第1个到第12个元素时，
- 触发第一次扩容：
- 当我们尝试存入第13个元素时，假设这个键不存在，
HashMap会准备插入它。在插入成功后，size将变为13。 - 此时，
HashMap会检查size(13) 是否大于当前的阈值 (12)。因为13 > 12成立，所以会触发resize()操作，进行第一次扩容。 - 扩容时，
HashMap的容量会翻倍，从16变为16 * 2 = 32。 - 新的阈值也会随之更新，变为
newCapacity * loadFactor = 32 * 0.75 = 24。
- 当我们尝试存入第13个元素时，假设这个键不存在，
- 第一次扩容后继续插入：
- 此时，
HashMap中已经有13个元素了，容量是32，新的扩容阈值是24。 - 我们还需要继续存入剩下的
20 - 13 = 7个元素（即从第14个到第20个元素）。 - 当我们存入第14个元素时，
size变为14。因为14 <= 24(新阈值)，所以不扩容。 - 以此类推，直到我们存入第20个元素，
size变为20。由于20 <= 24，仍然不会触发新的扩容。
- 此时，
- 结论：
- 因此，在向一个默认设置的
HashMap中存入20个元素的过程中，总共会发生1次扩容操作（在存入第13个元素之后触发）。
- 因此，在向一个默认设置的
说说HashMap的负载因子
面试官您好，关于 HashMap 的负载因子（loadFactor），我的理解是这样的：
1. 什么是负载因子？
- 负载因子是
HashMap中一个非常重要的参数，它衡量的是HashMap在其内部哈希表（Node[] table数组）被填满到什么程度时应该进行扩容（resize）。 - 具体来说，当
HashMap中存储的键值对数量（size）超过了capacity * loadFactor这个乘积时，HashMap就会认为自己“太满了”，需要进行扩容以维持其性能。这个乘积capacity * loadFactor通常就是HashMap内部的threshold（阈值）的值。
2. 默认值及其选择原因：
HashMap的默认负载因子是 0.75f。这个值是在HashMap的源码中定义的 (static final float DEFAULT_LOAD_FACTOR = 0.75f;)。- 选择0.75作为默认值，是基于对空间利用率和时间性能（主要是查找、插入、删除的效率）之间的一个经验性的权衡和折中。
- 如果负载因子设置得太低（比如0.5）：
HashMap会在内部数组还有很多空闲空间时就进行扩容。- 优点：哈希冲突的概率会相对较低，链表/红黑树的长度会较短，从而使得查找等操作的平均时间性能可能更好。
- 缺点：会导致更频繁的扩容操作（因为
threshold会更早达到），并且空间利用率较低，浪费了更多的内存来存储哈希桶。
- 如果负载因子设置得太高（比如0.9甚至1.0）：
HashMap会等到内部数组几乎被填满时才进行扩容。- 优点：空间利用率较高，扩容次数可能会减少。
- 缺点：哈希冲突的概率会显著增加，导致哈希桶中的链表变得很长或者过早地需要树化。这会使得查找、插入、删除等操作的平均时间性能恶化，极端情况下可能退化到O(N)（对于长链表）。
- 0.75被认为是泊松分布（Poisson distribution）下，哈希冲突概率和空间利用率之间的一个比较理想的平衡点。在这个负载因子下，可以期望哈希冲突不会过于频繁，同时空间也不会被过度浪费。官方文档和大量的实践表明，0.75通常能提供良好的综合性能。
- 如果负载因子设置得太低（比如0.5）：
3. 是否可以自定义负载因子？
- 是的，
HashMap提供了带有initialCapacity和loadFactor参数的构造函数，例如public HashMap(int initialCapacity, float loadFactor)。这意味着开发者可以根据应用的具体需求来调整负载因子。 - 何时考虑调整：
- 如果应用对内存使用非常敏感，且能容忍略高的查找时间，可以考虑适当调高负载因子（比如到0.8或0.85），但需要谨慎评估其对性能的影响。
- 如果应用对查找性能要求极高，且内存资源充足，可以考虑适当调低负载因子（比如到0.6或0.65），以减少哈希冲突。
总结：
HashMap 的负载因子是一个关键的调优参数，它决定了扩容的时机。默认值0.75是在时间和空间效率之间取得的一个良好平衡。理解负载因子的作用，有助于我们在特定场景下通过调整它（以及初始容量）来优化 HashMap 的性能表现。
HashMap和HashTable有什么不一样的？HashMap一般怎么用？
面试官您好，HashMap 和 Hashtable 都是 Java 集合框架中 Map 接口的实现，用于存储键值对，但它们之间存在一些关键的区别：
一、HashMap与 Hashtable 的主要区别：
- 线程安全性：
HashMap：非线程安全。如果在多线程环境下不加外部同步直接操作HashMap，可能会导致数据不一致、丢失，甚至在 JDK 1.7 及之前版本因扩容引发死循环等问题。Hashtable：线程安全。它的几乎所有公开方法（如get,put,remove）都使用了synchronized关键字进行修饰，锁的是整个Hashtable对象。这意味着在任何时刻只有一个线程能访问其同步方法。
- 性能：
HashMap：由于没有线程同步的开销，在单线程环境下或者正确进行了外部同步的多线程环境中，其效率通常比Hashtable高。Hashtable：因为方法级别的同步锁粒度较大，导致其并发性能较差，在高并发场景下会成为瓶颈，效率相对较低。
- 对
null键和null值的支持：HashMap：允许null作为键（key），也允许null作为值（value）。null键只能有一个（因为键的唯一性）。null值可以有多个。
Hashtable：不允许null作为键或值。如果尝试存入null键或null值，都会抛出NullPointerException。
- 初始容量和扩容机制：
HashMap(以 JDK 1.8+ 为例)：- 默认初始容量：16。
- 扩容机制：当元素数量超过
capacity * loadFactor(默认loadFactor为 0.75) 时触发扩容，通常容量变为原来的2倍。 - 容量调整：如果创建时指定了初始容量，
HashMap内部会将其调整为不小于该值的、最接近的2的幂次方大小。
Hashtable：- 默认初始容量：11。
- 扩容机制：当元素数量超过
capacity * loadFactor(默认loadFactor为 0.75) 时触发扩容，容量通常变为原来的2 * oldCapacity + 1。 - 容量调整：如果创建时指定了初始容量，它会直接使用这个给定的容量（不需要是2的幂次方）。
- 底层数据结构 (JDK 1.8+ 对比)：
HashMap：底层数据结构是数组 + 链表 + 红黑树。当链表长度超过阈值（默认为8）并且哈希表总容量也达到一定阈值（默认为64）时，链表会转换为红黑树，以优化查找性能。Hashtable：底层数据结构主要是数组 + 链表。它没有引入红黑树这样的优化。
- 父类和迭代器：
HashMap：继承自AbstractMap类。Hashtable：继承自Dictionary类（一个较早的抽象类，现已基本被Map接口取代）。- 迭代器：
HashMap的迭代器 (如通过entrySet().iterator()) 是 fail-fast 的。Hashtable也支持Iterator和一个较早的Enumeration接口，其迭代器通常也是 fail-fast 的。
- 推荐使用：
- 由于性能和设计上的优势，
HashMap是目前非并发场景下Map的首选。 Hashtable基本已被弃用。如果需要在线程安全的环境下使用Map，强烈推荐使用java.util.concurrent.ConcurrentHashMap，它提供了远优于Hashtable的并发性能。
- 由于性能和设计上的优势，
二、HashMap的一般使用方法：
HashMap 主要用于存储和操作键值对数据，其常见用法包括：
- 创建
HashMap实例：
Map<String, Integer> map = new HashMap<>(); // 使用默认参数
Map<String, Integer> mapWithCapacity = new HashMap<>(32); // 指定初始容量
Map<String, Integer> mapWithCapacityAndLoadFactor = new HashMap<>(32, 0.8f); // 指定初始容量和加载因子
- 添加或更新键值对 (put)：
map.put("Apple", 10);
map.put("Banana", 20);
Integer oldValue = map.put("Apple", 15); // oldValue 会是 10
- 使用 `put(K key, V value)` 方法。如果 `key` 已存在，则更新其对应的 `value`，并返回旧的 `value`；如果 `key` 不存在，则插入新的键值对，并返回 `null`。
- 获取键对应的值 (get)：
Integer applePrice = map.get("Apple"); // applePrice 会是 15
Integer orangePrice = map.get("Orange"); // orangePrice 会是 null (如果 "Orange" 不存在)
- 使用 `get(Object key)` 方法。如果 `key` 存在，返回其对应的 `value`；如果 `key` 不存在，返回 `null`。
- 检查是否包含指定的键 (containsKey)：
boolean hasApple = map.containsKey("Apple"); // true
- 使用 `containsKey(Object key)` 方法，返回 `boolean` 值。
- 检查是否包含指定的值 (containsValue)：
boolean hasPrice15 = map.containsValue(15); // true
- 使用 `containsValue(Object value)` 方法，返回 `boolean` 值。这个操作通常比 `containsKey` 效率低，因为它可能需要遍历整个 `Map`。
- 移除键值对 (remove)：
Integer removedValue = map.remove("Banana"); // removedValue 会是 20
- 使用 `remove(Object key)` 方法。如果 `key` 存在，移除该键值对并返回其对应的 `value`；如果 `key` 不存在，返回 `null`。
- 获取
Map的大小 (size)：
int numberOfEntries = map.size();
- 使用 `size()` 方法，返回键值对的数量。
- 判断
Map是否为空 (isEmpty)：
boolean isEmpty = map.isEmpty();
- 使用 `isEmpty()` 方法。
- 遍历
Map：
// 遍历 entrySet
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// JDK 8+ forEach
map.forEach((key, value) -> System.out.println("Key: " + key + ", Value: " + value));
- 常用的方式有遍历 `entrySet()`、`keySet()` 或 `values()`。
- 使用 `forEach` (JDK 8+) 方法。
- 使用 Stream API。
这些是 HashMap 最基本和常用的操作。在实际使用中，还需要注意 Key 对象的 hashCode() 和 equals() 方法的正确实现，以及在多线程环境下的线程安全问题。
HashMap 和 TreeMap 区别
面试官您好，HashMap 和 TreeMap 都是 Java 集合框架中 Map 接口的重要实现，它们都继承自 AbstractMap 类，用于存储键值对。但它们在底层数据结构、元素顺序、性能特性以及因此提供的功能上有显著的区别。
一、核心区别：
- 底层数据结构：
HashMap：基于哈希表 (Hash Table) 实现。在 JDK 1.8 及以后，具体是数组 + 链表 + 红黑树。它通过计算键的哈希码来快速定位存储位置。TreeMap：基于红黑树 (Red-Black Tree) 实现。红黑树是一种自平衡的二叉搜索树，保证了键的有序性。
- 元素顺序 (Key Order)：
HashMap：不保证键的任何特定顺序。元素的存储和迭代顺序与插入顺序无关，并且可能随时间变化（如扩容后）。TreeMap：保证键按照某种顺序排列。这是TreeMap最核心的特性之一。- 默认按键的自然顺序升序排列（要求键的类实现
Comparable接口）。 - 或者，可以在创建
TreeMap时提供一个**自定义的 **Comparator来指定键的排序规则。
- 默认按键的自然顺序升序排列（要求键的类实现
- 性能特性：
HashMap：- 对于
put,get,remove,containsKey等基本操作，平均时间复杂度是 O(1)（假设哈希函数分布良好）。 - 最坏情况下（哈希冲突严重导致链表过长），JDK 1.7 及以前是 O(N)，JDK 1.8+ 由于红黑树的引入，最坏情况是 O(log N)。
- 对于
TreeMap：- 对于
put,get,remove,containsKey等操作，由于其基于红黑树，时间复杂度稳定在 O(log N)，其中 N 是Map中键值对的数量。
- 对于
- 对
null键的支持：HashMap：允许一个null键和多个null值。TreeMap：- 默认情况下不允许
null键，因为null无法进行自然的比较（调用compareTo()会抛NullPointerException）。 - 如果创建
TreeMap时提供了**能处理null键的 **Comparator，则可以支持null键（但通常不推荐，因为null的比较逻辑可能比较复杂和不直观）。 - 允许
null值。
- 默认情况下不允许
- 实现的接口与提供的额外功能：
HashMap：主要实现Map接口。TreeMap：除了实现Map接口，它还实现了SortedMap接口 和NavigableMap接口。- 实现
SortedMap接口：这赋予了TreeMap保持键排序的能力，并提供了一些与排序相关的方法，如：comparator(): 返回用于排序键的比较器，如果使用自然顺序则返回null。firstKey(): 返回第一个（最小的）键。lastKey(): 返回最后一个（最大的）键。headMap(toKey): 返回键小于toKey的子映射。tailMap(fromKey): 返回键大于等于fromKey的子映射。subMap(fromKey, toKey): 返回键在[fromKey, toKey)范围内的子映射。
- 实现
NavigableMap接口 (JDK 1.6+)：这是SortedMap的扩展，提供了更强大的导航和搜索功能：- 定向搜索：如
ceilingEntry(key)(大于等于key的最小项),floorEntry(key)(小于等于key的最大项),higherEntry(key)(严格大于key的最小项),lowerEntry(key)(严格小于key的最大项) 等。这些方法使得可以非常方便地查找邻近元素。 - 边界操作：如
firstEntry(),lastEntry(), 以及它们的移除版本pollFirstEntry(),pollLastEntry()。 - 逆序视图：
descendingMap()方法返回一个键按降序排列的NavigableMap视图，无需重新构建。 - 更灵活的子集操作：
subMap(),headMap(),tailMap()方法都增加了可以控制边界是否包含的布尔参数。 - 这些强大的导航功能都是基于红黑树的有序性和结构特性高效实现的，时间复杂度通常是 O(log N)。
- 定向搜索：如
- 实现
二、总结与选择：
| 特性 | HashMap |
TreeMap |
|---|---|---|
| 底层结构 | 哈希表 (数组+链表+红黑树) | 红黑树 |
| 键顺序 | 无序 | 有序 (自然顺序或自定义比较器) |
| 性能 (平均) | O(1) (put, get, remove) | O(log N) (put, get, remove) |
null键 |
允许一个 | 默认不允许 (除非 Comparator 支持) |
| 主要接口 | Map |
Map, SortedMap, NavigableMap |
| 额外功能 | 无特殊顺序或导航功能 | 排序、范围查询、邻近查找、逆序视图等导航功能 |
| 适用场景 | 追求快速存取，对顺序无要求 | 需要按键排序，或需要利用其丰富的导航/范围查询功能 |
简单来说：
- 如果你的主要需求是快速的键值对存取，并且不关心键的顺序，那么
HashMap通常是更好的选择，因为它平均情况下提供 O(1) 的性能。 - 如果你需要一个键始终保持有序的
Map，或者需要执行基于键顺序的复杂查询操作（如查找某个范围内的条目、查找大于或小于某个键的最近条目等），那么TreeMap是不二之选。
ConcurrentHashMap怎么实现的？
面试官您好，ConcurrentHashMap 是 JUC (java.util.concurrent) 包下的一个高效的线程安全 Map 实现。它的核心目标是在保证线程安全的前提下，尽可能地提高并发访问的性能。其具体实现方式在 JDK 版本间有所演进：
一、JDK 1.7 及以前版本的 ConcurrentHashMap (基于 Segment 分段锁)
在 JDK 1.7 中，ConcurrentHashMap 的设计核心是分段锁 (Segment-based locking)。
- 核心数据结构：
ConcurrentHashMap内部维护一个Segment<K,V>[] segments数组。每个Segment对象本身类似于一个小的、线程安全的HashMap（或者说更像一个Hashtable，因为它继承自ReentrantLock并持有自己的HashEntry<K,V>[] table数组）。Segment继承了ReentrantLock，所以每个Segment都有自己的锁。HashEntry是存储键值对的节点，类似于HashMap中的Entry，包含key,value,hash和指向下一个节点的next指针，用于构成链表解决哈希冲突。
- 工作原理：
- 初始化：在创建
ConcurrentHashMap时，会初始化segments数组。segments数组的长度（即分段的数量）由concurrencyLevel参数决定，默认为16。这个concurrencyLevel决定了理论上可以同时有多少个线程并发地修改ConcurrentHashMap的不同部分。 - 定位
Segment：当进行put,remove等写操作时，ConcurrentHashMap会首先根据键key的哈希值来确定这个键值对应该属于哪个Segment。通常是通过(hash >>> segmentShift) & segmentMask来计算Segment的索引。 - 加锁与操作：
- 一旦定位到目标
Segment，线程会尝试获取该Segment对象的锁（segment.lock()）。 - 获取锁成功后，线程就可以安全地对该
Segment内部的HashEntry数组进行操作了（比如查找、插入、删除节点，或者在需要时对该Segment的HashEntry数组进行扩容）。 - 由于每个
Segment有独立的锁，不同Segment上的写操作可以完全并发执行，互不干扰。这就是分段锁提高并发性能的关键。
- 一旦定位到目标
get操作：get操作通常是非阻塞的，大部分情况下不需要加锁。- 它会先定位到
Segment，然后直接访问该Segment内的HashEntry数组。 HashEntry节点的value字段和next字段通常使用volatile修饰，以保证多线程间的可见性。- 只有在某些特定情况下（例如，当读取到的
value为null，需要进一步确认是否真的不存在，或者某个节点正在被修改时），get操作可能会短暂地获取一下Segment的锁。
- 它会先定位到
size()操作：计算整个ConcurrentHashMap的大小是一个相对复杂的操作。它不能简单地对所有Segment的size求和，因为在求和过程中，其他线程可能正在修改某些Segment的大小。JDK 1.7 的size()方法通常会尝试多次不加锁地累加各个Segment的count字段（volatile修饰），如果在此期间modCount（记录Segment结构修改次数）没有变化，则认为结果是准确的；否则，会退化为对所有Segment依次加锁再求和，以保证结果的准确性。
- 初始化：在创建
- 优点：通过分段锁，将锁的粒度从整个
Map降低到了每个Segment，显著提高了并发写入的吞吐量。 - 缺点：
- 在某些操作（如
size()）上仍然有性能瓶颈。 Segment数组一旦初始化，其数量就固定了，如果哈希分布极端不均，可能导致某些Segment成为热点。- 代码实现相对复杂。
- 在某些操作（如
二、JDK 1.8 及以后版本的 ConcurrentHashMap (基于 CAS + synchronized + Node/TreeNode)
JDK 1.8 对 ConcurrentHashMap 的实现进行了重大的重构，摒弃了 Segment 分段锁的设计，采用了更细粒度的锁机制和无锁操作。
- 核心数据结构：
- 底层数据结构与 JDK 1.8 的
HashMap非常相似：一个**Node<K,V>[] table**数组（volatile修饰）。 - 每个数组元素（哈希桶）的头节点可以是普通的
Node（构成链表），也可以是TreeNode（构成红黑树，当链表长度达到阈值时转换）。 Node节点的val和next指针通常使用volatile修饰，以保证可见性。
- 底层数据结构与 JDK 1.8 的
- 工作原理：
get操作：通常是完全无锁的。它直接通过volatile读来访问table数组和链表/树中的节点。volatile保证了读取到的是最新的值。put操作 (核心)：- 计算哈希值和索引：与
HashMap类似。 - 无锁尝试 (CAS)：
- 如果目标哈希桶
table[i]为null，则会尝试使用 CAS (Compare-And-Swap) 操作原子性地将新节点设置到table[i]。如果 CAS 成功，则插入完成。 - 如果 CAS 失败（说明有其他线程同时操作了这个桶），则进入下一步。
- 如果目标哈希桶
- 加锁 (
synchronized)：- 如果
table[i]不为null（即桶中已有节点），或者 CAS 初始化桶失败，此时会使用synchronized关键字来锁定table[i]的头节点（f = tabAt(tab, i)，然后synchronized(f)）。 - 锁的粒度非常小，只锁住当前操作的这个哈希桶的头节点。不同哈希桶的操作可以完全并发执行。
- 获取锁之后，线程会再次检查头节点是否改变（防止ABA问题等，虽然
synchronized本身解决了可见性和原子性）。 - 然后在同步块内部，安全地在链表或红黑树中进行插入或更新操作（逻辑与
HashMap类似，包括链表转红黑树的判断）。
- 如果
- 特殊标记节点
ForwardingNode：在扩容（transfer）过程中，如果一个桶的迁移已经完成，该桶的头节点会被设置成一个特殊的ForwardingNode。当其他线程访问到ForwardingNode时，它们知道需要去帮助完成扩容或者等待扩容完成，然后在新表中操作。
- 计算哈希值和索引：与
- 扩容 (
transfer操作)：- 扩容操作是并发进行的。当某个线程触发了扩容（比如
put后检查到size超过阈值），它会开始迁移数据。 - 其他线程在
put或其他写操作时，如果发现ConcurrentHashMap正在扩容，它们也可以加入到帮助扩容的行列中，每个线程负责迁移一部分哈希桶的数据。 - 数据迁移的逻辑与
HashMap类似，利用容量是2的幂次方的特性，将原桶中的节点拆分到新表的两个桶中（原索引或原索引 + 旧容量）。 volatile保证了table引用、nextTable引用以及sizeCtl控制变量的可见性。sizeCtl是一个多功能的控制字段，用于协调扩容状态（如：-1 表示正在初始化，-(1 + nThreads) 表示有n个线程正在扩容）。
- 扩容操作是并发进行的。当某个线程触发了扩容（比如
size()操作：JDK 1.8 的size()操作不再像 JDK 1.7 那样复杂。它通过一个baseCount(long 型，volatile修饰) 和一个CounterCell[]数组来高效地、近似地统计大小。- 大部分情况下，线程通过 CAS 更新
baseCount。 - 如果 CAS
baseCount失败（并发竞争激烈），线程会尝试将增量更新到CounterCell数组中的某个随机槽位。 - 计算总
size时，累加baseCount和所有CounterCell中的值。这种方式类似于LongAdder，在高并发下表现很好。
- 大部分情况下，线程通过 CAS 更新
- 优点：
- 锁的粒度进一步减小到了哈希桶的头节点（或者在某些情况下完全无锁），并发性能更高。
- 扩容操作可以并发执行，减少了扩容期间对整体性能的影响。
- 代码结构相对 JDK 1.7 的
Segment更简洁一些（虽然内部逻辑依然复杂）。 size()等聚合操作的性能也得到了优化。
总结来说：
- JDK 1.7 的
ConcurrentHashMap通过分段锁实现并发，每个Segment拥有独立的锁。 - JDK 1.8 的
ConcurrentHashMap则采用更细粒度的锁（synchronized** 锁哈希桶头节点）和 CAS 操作**相结合的方式，并支持并发扩容，性能和可伸缩性都得到了显著提升。
目前我们谈论 ConcurrentHashMap 通常指的是 JDK 1.8 及以后的实现，因为它在性能和设计上更为先进。
已经用了synchronized，为什么还要用CAS呢？
面试官您好，ConcurrentHashMap 在 JDK 1.8 及以后的版本中，确实巧妙地结合了 synchronized 和 CAS (Compare-And-Swap) 这两种同步机制。这种设计并不是冗余，而是为了在不同并发场景下，尽可能地提高性能和减少锁的开销，是一种精巧的权衡。
为什么不只用一种？
- 只用
synchronized：如果所有操作都用synchronized（即使是锁住哈希桶的头节点这种细粒度锁），在并发度不高或者没有竞争的情况下，synchronized仍然会涉及到用户态到内核态的切换、线程阻塞、唤醒等开销（尤其是在锁竞争不激烈时，轻量级锁和偏向锁可以优化，但仍有一定成本）。 - 只用 CAS：CAS 是一种乐观锁机制，它假设冲突很少。在无竞争或低竞争情况下，CAS 非常高效，因为它不需要将线程挂起。但是，如果并发竞争非常激烈，CAS 操作会频繁失败，导致线程需要不断自旋重试。过多的自旋会消耗大量 CPU 资源，反而降低性能。此外，CAS 通常只能保证单个共享变量的原子操作，对于复杂的复合操作（如初始化一个节点并链接，或者进行红黑树的调整）直接用 CAS 实现会非常复杂且容易出错。
ConcurrentHashMap如何结合使用它们？
ConcurrentHashMap 的策略是：在大概率无竞争或低竞争的路径上优先使用开销更低的 CAS；在预计竞争会比较激烈或操作比较复杂的路径上，则退回到使用 synchronized 来保证原子性和互斥性。
正如您提到的，在 putVal 方法中体现得非常明显：
- 尝试 CAS 进行无锁或低冲突插入 (乐观路径)：
- 情况一：哈希桶为空 (
tab[i] == null)：- 当计算出的哈希桶位置是空的，
ConcurrentHashMap会首先尝试使用 CAS 操作来原子性地将新节点放入该空桶。 - 原因：这是最理想的情况，表明没有其他线程同时操作这个桶。正如您所说，由于哈希函数的扰动和良好的分布，一个新元素映射到一个完全空的桶的概率是相对较高的，尤其是在
Map负载不高的时候。此时，如果 CAS 成功，就避免了任何锁的开销，性能极高。
- 当计算出的哈希桶位置是空的，
- CAS 自旋：即使第一次 CAS 失败（可能刚好有另一个线程也在初始化这个桶），它也可能会进行少量自旋重试 CAS，因为冲突可能只是暂时的。
- 情况一：哈希桶为空 (
- 退化到
synchronized进行有锁操作 (悲观路径/高冲突或复杂操作)：- 情况二：哈希桶不为空，或 CAS 初始化失败：
- 当哈希桶已经有节点（即发生了哈希冲突），或者 CAS 初始化空桶失败（说明有并发竞争），此时
ConcurrentHashMap会切换到使用synchronized关键字来锁定该哈希桶的头节点 (synchronized(f)，其中f是桶的头节点)。 - 原因：
- 处理哈希冲突：正如您所说，如果发生了哈希冲突，意味着这个桶已经有数据，或者多个线程正在争抢这个桶。此时，后续的操作（如遍历链表、在链表末尾添加节点、判断是否需要树化、进行树化操作、在红黑树中插入节点）通常是比较复杂的复合操作，难以用简单的 CAS 直接高效且正确地实现。
- 预计竞争激烈：发生哈希冲突或 CAS 初始化失败本身就暗示了该桶可能是一个热点，后续的并发访问概率较高。在这种情况下，直接使用
synchronized来确保互斥和原子性，避免了 CAS 大量失败和无效自旋带来的 CPU 浪费，反而可能是更稳妥和高效的选择。synchronized在 JDK 1.6 之后有锁升级优化，对于锁定的代码块，它能提供可靠的互斥保障。 - 简化复杂逻辑：对于链表操作和红黑树操作，
synchronized块内的代码可以像单线程那样编写，逻辑更清晰，不易出错。
- 当哈希桶已经有节点（即发生了哈希冲突），或者 CAS 初始化空桶失败（说明有并发竞争），此时
- 情况二：哈希桶不为空，或 CAS 初始化失败：
总结来说，ConcurrentHashMap采用这种混合策略是为了：
- 最大化无锁/低锁路径的性能：对于最常见的、冲突概率较低的场景（如插入到空桶），通过 CAS 实现极高的吞吐量。
- 在冲突不可避免或操作复杂时保证正确性和合理性能：当冲突发生或需要执行复杂原子操作时，利用
synchronized的强大互斥能力和相对成熟的锁优化机制，来保证数据一致性和避免过度消耗 CPU。 - 动态适应：这种设计实际上是一种基于对典型使用模式和并发行为的预测，动态地选择同步策略。
这体现了 ConcurrentHashMap 设计者在性能、复杂度和可靠性之间做出的精妙权衡，是并发数据结构设计中的一个经典范例。
ConcurrentHashMap用了悲观锁还是乐观锁?
面试官您好，关于 ConcurrentHashMap (特指 JDK 1.8 及以后的版本) 使用的是悲观锁还是乐观锁，我认为它巧妙地结合了这两种锁的思想，并在不同操作路径上有所侧重，以实现最佳的并发性能和线程安全性。
可以这样理解：
- 乐观锁思想的体现 (主要通过 CAS 操作)：
ConcurrentHashMap在很多情况下会优先尝试非阻塞的、基于 CAS (Compare-And-Swap) 的原子操作。CAS 本身就是一种乐观锁的典型实现：它假设在操作期间不会有其他线程修改共享数据，因此先进行计算，然后在提交更新时通过比较期望值和内存中的当前值来判断是否有冲突。如果没有冲突，则更新成功；如果发生冲突（值已被其他线程修改），则操作失败，通常需要重试或采取其他策略。- 具体应用场景（正如您所描述的，在
putVal等写操作中）：- 初始化哈希桶：当一个哈希桶（
table[i]）为null时，ConcurrentHashMap会尝试使用 CAS 操作来原子性地将新节点设置到这个空桶。这是典型的乐观尝试，如果成功，就避免了任何加锁的开销。 - 更新某些计数器：例如，在
size()的实现中，baseCount的更新以及CounterCell数组中槽位的更新，很多时候都是通过 CAS 来完成的，以支持高并发的计数。 - 某些状态转换：内部的一些状态标记（如
sizeCtl的某些变化）也可能利用 CAS。
- 初始化哈希桶：当一个哈希桶（
- 优点：在低冲突或无冲突的情况下，CAS 非常高效，因为它避免了线程上下文切换和阻塞的开销。
- 悲观锁思想的体现 (主要通过
synchronized关键字)：- 当乐观的 CAS 尝试失败（意味着存在并发竞争），或者操作本身比较复杂不适合用 CAS 直接实现时，
ConcurrentHashMap就会退回到使用synchronized这种更传统的悲观锁机制。悲观锁假设冲突总是会发生，所以在访问共享资源前总是先获取锁。 - 具体应用场景（在
putVal等写操作中）：- 处理哈希冲突：当计算出的哈希桶位置已经有节点存在（即
table[i]不为null），或者 CAS 初始化空桶失败时，线程会使用synchronized(f)（其中f是该哈希桶的头节点）来锁定这个桶。 - 复杂节点操作：在获取到
synchronized锁之后，线程才能安全地进行链表的遍历、节点的插入/更新、链表转换为红黑树、红黑树节点的插入/更新等复杂操作。这些操作如果用 CAS 来实现会非常复杂且容易出错。
- 处理哈希冲突：当计算出的哈希桶位置已经有节点存在（即
- 锁的粒度：需要强调的是，即使使用了
synchronized，其锁的粒度也非常小，仅仅是哈希桶的头节点。这意味着不同哈希桶上的操作仍然可以完全并发执行。 - 优点：
synchronized提供了强有力的互斥保证，能够可靠地处理高并发冲突和复杂的临界区代码，避免了 CAS 在高冲突下大量自旋的性能问题。
- 当乐观的 CAS 尝试失败（意味着存在并发竞争），或者操作本身比较复杂不适合用 CAS 直接实现时，
总结来说：
ConcurrentHashMap不是单纯地只使用一种锁策略，而是混合使用了乐观锁（CAS）和悲观锁（synchronized）的思想。- 它优先尝试乐观的、开销较低的 CAS 操作，尤其是在初始化空桶这类大概率无冲突的场景。
- 当 CAS 无法解决问题（如发生冲突或操作复杂）时，它会优雅地退化到使用悲观的、但更稳健的
synchronized锁（锁住哈希桶头节点），以确保数据一致性和操作的原子性。 - 这种设计体现了对不同并发场景下性能和复杂度的精妙权衡，使得
ConcurrentHashMap能够在各种负载下都表现出优秀的并发性能。
所以，如果非要给它贴一个标签，可以说它是一个以乐观锁尝试为先导，以细粒度悲观锁为后盾的并发数据结构。
HashTable 底层实现原理是什么？
面试官您好，Hashtable 是 Java 早期提供的一个线程安全的 Map 实现，它的底层实现原理主要包含以下几个方面：
- 核心数据结构：
- 正如您所说，
Hashtable的底层主要是一个数组（Entry<K,V>[] table），这个数组的每个元素可以看作是一个哈希桶（bucket）。 - 为了解决哈希冲突（即多个不同的键经过哈希计算后映射到同一个数组索引），
Hashtable采用的是链接法 (Chaining)。每个哈希桶中存储的是一个单向链表的头节点（Entry<K,V>）。当发生冲突时，新的键值对会被添加到对应链表的头部或尾部（具体取决于实现，早期版本可能是头插）。 Entry<K,V>是Hashtable内部定义的一个静态内部类，用于封装键值对以及指向链表中下一个节点的引用。它通常包含hash、key、value和next四个字段。- 与 JDK 1.8 及以后版本的
HashMap不同，Hashtable没有引入红黑树来优化长链表的查询性能。
- 正如您所说，
- 哈希与索引计算：
- 当进行
put或get操作时，Hashtable会首先计算键key的hashCode()。 - 然后，它会将这个哈希码通过一个内部的哈希函数（通常是取模运算）映射到
table数组的索引上，公式一般是index = (hash & 0x7FFFFFFF) % table.length。hash & 0x7FFFFFFF这一步是为了确保哈希值是正数（因为数组索引不能为负）。0x7FFFFFFF是一个除了符号位全为1的掩码。% table.length是取模操作，得到最终的数组下标。
- 当进行
- 线程安全机制：
Hashtable是线程安全的，这是它与HashMap最显著的区别之一。- 它实现线程安全的方式比较“简单粗暴”：几乎所有公开的、可能修改
Hashtable状态或读取其状态的方法（如put(),get(),remove(),size(),containsKey(),elements(),keys()等）都使用了synchronized关键字进行修饰。 - 这意味着在任何时刻，只有一个线程能够执行
Hashtable的这些同步方法。这个锁是施加在Hashtable对象实例本身 (this) 上的。 - 当一个线程进入了某个同步方法后，其他线程如果尝试调用
Hashtable的任何其他同步方法，都必须等待，直到第一个线程退出同步方法并释放锁。正如您所说，这会导致其他线程陷入阻塞或轮询（取决于JVM的锁实现细节）的状态。
- 对
null键和null值的限制：Hashtable不允许null作为键（key）或值（value）。如果尝试put(null, ...)或put(..., null)，都会抛出NullPointerException。这是因为在其方法内部，通常会直接对key或value调用方法（如hashCode()或equals()），或者有显式的null检查并抛出异常。
- 初始容量和扩容机制：
- 默认初始容量：11。
- 加载因子 (Load Factor)：默认为0.75。
- 扩容机制：当
Hashtable中的元素数量超过capacity * loadFactor时，会触发扩容。新的容量通常是原来的2 * oldCapacity + 1。例如，从11扩容到2*11 + 1 = 23。 - 扩容过程涉及到创建一个新的、更大的
Entry数组，并将旧数组中的所有元素重新哈希并迁移到新数组中。
- 历史与现状：
Hashtable是 Java 1.0 版本就引入的集合类，属于早期 JDK 的一部分。- 由于其方法级别的全局同步导致并发性能低下，在高并发场景下会成为严重的瓶颈，因此现在基本不推荐使用
Hashtable。 - 如果需要线程安全的
Map，Java 提供了更现代且性能更优的选择，即java.util.concurrent.ConcurrentHashMap。
总结来说，Hashtable的底层实现依赖于数组和链表来存储键值对，并通过在所有公共方法上使用synchronized关键字来实现线程安全。这种全局锁的机制虽然保证了线程安全，但也牺牲了并发性能，使其在现代 Java 应用中已逐渐被ConcurrentHashMap所取代。
HashTable线程安全是怎么实现的？
面试官您好，Hashtable 实现线程安全的方式相对直接和“经典”，它主要通过以下机制：
synchronized关键字修饰方法：Hashtable的几乎所有公开的、涉及到数据读取或修改的方法，例如put(K key, V value)、get(Object key)、remove(Object key)、size()、isEmpty()、containsKey(Object key)、containsValue(Object value)、elements()(返回Enumeration)、keys()(返回Enumeration) 等，都在其方法签名上使用了synchronized关键字。
- 锁对象 (Monitor)：
- 当一个方法被
synchronized修饰时，它在执行前会尝试获取一个锁。对于Hashtable中的这些实例方法，它们获取的是当前Hashtable对象实例本身的锁（即this对象作为锁监视器）。
- 当一个方法被
- 互斥访问：
- 由于所有这些关键方法都同步在同一个锁对象（
Hashtable实例）上，这意味着在任何一个时间点，只有一个线程能够执行Hashtable实例中任何一个被synchronized修饰的方法。 - 如果一个线程（比如线程A）正在执行
hashtable.put(...)，那么在线程A完成put操作并释放锁之前，其他任何线程（比如线程B）如果尝试调用hashtable.get(...)、hashtable.remove(...)或甚至是另一个hashtable.put(...)，都必须等待，直到线程A释放锁。
- 由于所有这些关键方法都同步在同一个锁对象（
- 保证原子性和可见性：
synchronized关键字不仅保证了互斥性（同一时间只有一个线程访问），它还具有内存可见性的保证。当一个线程退出synchronized代码块时，它对共享变量所做的所有修改，对于后续获取同一个锁的线程来说都是可见的。- 同时，
synchronized也能保证被其保护的代码块作为一个原子操作执行完毕，中间状态不会被其他线程观察到或干扰。
举例说明：
假设有两个线程，线程1想执行 hashtable.put("A", 1)，线程2想执行 hashtable.get("B")。
- 如果线程1先获得了
hashtable对象的锁并开始执行put方法，那么线程2在尝试执行get方法时，会发现锁已被占用，于是线程2会进入阻塞状态。 - 直到线程1完成了
put操作（包括可能的内部数据结构调整，如哈希冲突处理或扩容），并从put方法返回，释放了锁。 - 之后，线程2才可能被唤醒，获取到锁，并开始执行
get方法。
总结与评价：
Hashtable通过在其所有关键公共方法上同步整个对象实例，实现了简单而粗粒度的线程安全。- 优点：实现简单直接，能够有效防止并发访问导致的数据不一致、死锁（虽然不是这里的死锁，而是指数据损坏）等问题。
- 缺点：这种全局锁（锁整个对象） 的机制，使得
Hashtable的并发性能非常低下。因为无论线程是读操作还是写操作，都需要竞争同一个锁。在高并发场景下，这会导致大量的线程等待，吞吐量急剧下降，Hashtable实例本身会成为一个严重的性能瓶颈。
因此，虽然 Hashtable 是线程安全的，但由于其性能问题，在现代 Java 开发中，如果需要线程安全的 Map，通常会选择使用 java.util.concurrent.ConcurrentHashMap，后者采用了更细粒度的锁机制（如分段锁或 CAS + synchronized 锁桶头节点），提供了远超 Hashtable 的并发性能。
Hashtable 和ConcurrentHashMap有什么区别
面试官您好，Hashtable 和 ConcurrentHashMap 都是线程安全的 Map 实现，但它们在设计思想、实现机制、性能表现以及一些特性支持上有着显著的区别。ConcurrentHashMap 是对 Hashtable 在并发性能上的巨大改进。
主要区别可以从以下几个方面来看：
1. 底层数据结构：
Hashtable：- 其底层数据结构主要是数组（
Entry[] table） + 链表。数组是哈希表的主体，链表用于解决哈希冲突。 - 它没有引入红黑树这样的优化结构来处理过长的链表。
- 其底层数据结构主要是数组（
ConcurrentHashMap：- JDK 1.7 及以前：底层采用的是分段的数组 + 链表。即一个
Segment数组，每个Segment内部持有一个HashEntry数组（类似于一个小的Hashtable）。 - JDK 1.8 及以后：底层数据结构与 JDK 1.8 的
HashMap类似，是数组（Node[] table） + 链表 / 红黑树。当链表长度达到一定阈值（默认为8）并且哈希表总容量也足够大时，链表会转换为红黑树，以优化查找和插入性能。
- JDK 1.7 及以前：底层采用的是分段的数组 + 链表。即一个
2. 实现线程安全的方式（核心区别）：
Hashtable：- 通过在几乎所有公开的、可能修改或读取状态的方法上使用
synchronized关键字来实现线程安全。 - 这个
synchronized锁的是整个Hashtable对象实例 (this)。 - 这意味着在任何时刻，只有一个线程能执行
Hashtable的任何一个同步方法。这种全局锁的方式导致其并发性能非常低下，因为所有操作都需要竞争同一个锁。
- 通过在几乎所有公开的、可能修改或读取状态的方法上使用
ConcurrentHashMap：- JDK 1.7 及以前 (分段锁)：
- 它将数据分成多个段 (Segment)，每个
Segment都有自己独立的锁（ReentrantLock）。 - 写操作（如
put,remove）只需要获取对应Segment的锁，而不需要锁定整个Map。 - 不同
Segment上的写操作可以并发执行，从而大大提高了并发写入的吞吐量。get操作大部分情况下是无锁的。
- 它将数据分成多个段 (Segment)，每个
- JDK 1.8 及以后 (CAS +
synchronized锁桶头节点)：- 摒弃了
Segment的设计，采用了更细粒度的锁机制。 - 对于写操作，首先会尝试使用 CAS (Compare-And-Swap) 操作进行无锁或低冲突的原子更新（例如，在空桶中插入节点）。
- 如果 CAS 失败或需要进行复杂操作（如处理哈希冲突、链表/红黑树操作），则会使用
synchronized关键字来锁定当前操作的那个哈希桶的头节点。 - 这种锁的粒度非常小，只影响当前哈希桶，不同哈希桶的操作可以完全并发。
get操作通常是完全无锁的，依赖volatile保证可见性。- 扩容操作也支持并发进行。
- 摒弃了
- JDK 1.7 及以前 (分段锁)：
3. 性能表现：
Hashtable：由于全局锁的限制，其并发性能非常差，在高并发场景下会成为严重的瓶颈。ConcurrentHashMap：- 无论是 JDK 1.7 的分段锁，还是 JDK 1.8 的 CAS +
synchronized锁桶头节点，都提供了远优于Hashtable的并发性能和吞吐量。 - JDK 1.8 的实现在大多数情况下比 JDK 1.7 的性能更好，尤其是在高并发和需要动态扩容的场景下。
- 无论是 JDK 1.7 的分段锁，还是 JDK 1.8 的 CAS +
4. 对 null 键和 null 值的支持：
Hashtable：不允许null作为键或值。尝试存入会抛出NullPointerException。ConcurrentHashMap：也不允许null作为键或值。这是为了避免在并发环境下，get(key)返回null时产生歧义（即无法判断是键不存在，还是键存在但其值为null）。如果允许null值，那么containsKey(key)就变得非常必要，这会增加并发控制的复杂性。
5. 迭代器的行为：
Hashtable：其keys()和elements()方法返回的是Enumeration对象，这些迭代器通常是 fail-fast 的。通过entrySet().iterator()等方式获取的Iterator也是 fail-fast 的。ConcurrentHashMap：它返回的迭代器（如通过entrySet().iterator(),keySet().iterator(),values().iterator()）是弱一致性 (weakly consistent) 的，而不是 fail-fast 的。- 这意味着迭代器在创建后，可以容忍并发修改（其他线程的
put,remove操作）。 - 迭代器不会抛出
ConcurrentModificationException。 - 迭代器反映的是创建迭代器时或创建后某个时间点的状态，可能不会反映迭代器创建之后的所有修改。
- 这意味着迭代器在创建后，可以容忍并发修改（其他线程的
6. 继承关系：
Hashtable：继承自Dictionary类。ConcurrentHashMap：继承自AbstractMap类，和HashMap类似。
总结来说：
ConcurrentHashMap 是对 Hashtable 的一个巨大飞跃，它通过更先进和细粒度的并发控制机制，在保证线程安全的同时，提供了高得多的并发性能。而 Hashtable 由于其全局锁的实现方式，性能低下，在现代 Java 开发中已基本被 ConcurrentHashMap 所取代。在需要线程安全的 Map 时，ConcurrentHashMap 是首选。
说一下HashMap和Hashtable、ConcurrentMap的区别
面试官您好，HashMap, Hashtable, 和 ConcurrentHashMap 都是 Java 中 Map 接口的重要实现，它们在线程安全性、性能、对 null 值的支持以及底层实现细节上有着显著的区别。
1. HashMap (非线程安全，高性能)
- 线程安全性：非线程安全。在多线程环境下并发修改
HashMap会导致数据不一致、丢失，甚至在 JDK 1.7 及以前可能因扩容引发死循环。它设计用于单线程环境或者在多线程环境中由外部进行同步控制。 - 性能：由于没有线程同步的开销，其效率在单线程或正确同步的多线程环境下是最高的。
null值支持：允许一个null键和多个null值。- 初始容量与扩容 (以 JDK 1.8+ 为例)：
- 默认初始容量为16。
- 扩容时容量通常变为原来的2倍。
- 容量总是2的幂次方。
- 底层数据结构 (JDK 1.8+)：数组 + 链表 + 红黑树。当链表长度超过阈值（默认为8）且总容量足够大（默认为64）时，链表会转换为红黑树以优化性能。
- 适用场景：单线程环境，或多线程环境下能保证外部同步控制的场景。
2. Hashtable (线程安全，性能较低)
- 线程安全性：线程安全。它通过在几乎所有公开方法上使用
synchronized关键字来实现，锁的是整个Hashtable对象实例。 - 性能：由于这种全局锁的机制，其并发性能非常低下，在高并发场景下会成为瓶颈。
null值支持：不允许null键和null值。尝试存入会抛出NullPointerException。- 初始容量与扩容：
- 默认初始容量为11。
- 扩容时容量通常变为
2 * oldCapacity + 1。
- 底层数据结构：数组 + 链表。没有红黑树优化。
- 现状：由于性能问题，
Hashtable基本已被弃用。
3. ConcurrentHashMap (线程安全，高性能并发)
ConcurrentHashMap 专为高并发场景设计，旨在提供比 Hashtable 更好的并发性能。其实现方式在 JDK 版本间有所不同：
- 线程安全性：线程安全。
- 性能：通过更细粒度的锁机制（或无锁操作），提供了远高于
Hashtable的并发性能。 null值支持：与Hashtable类似，不允许null键和null值，以避免并发歧义。- 底层数据结构与线程安全实现：
- JDK 1.7 及以前 (分段锁)：
- 正如您所描述，它将整个哈希表分成多个
Segment(段)，每个Segment拥有独立的锁 (ReentrantLock) 并管理一部分数据（一个小的HashEntry数组）。 - 写操作只锁定对应的
Segment，不同Segment上的操作可以并发。 - 读操作大部分情况下无锁。
- 底层是 分段的数组 + 链表。
- 正如您所描述，它将整个哈希表分成多个
- JDK 1.8 及以后 (CAS +
synchronized锁桶头节点)：- 摒弃了
Segment，采用了与HashMap类似的数组 (Node[]) + 链表 / 红黑树结构。 - 并发控制主要通过 CAS (Compare-And-Swap) 操作进行乐观的无锁或低冲突更新。
- 当 CAS 失败或需要进行复杂操作时，会使用
synchronized关键字锁定当前操作的哈希桶的头节点，锁的粒度非常小。 - 扩容操作也支持并发进行。
- 摒弃了
- JDK 1.7 及以前 (分段锁)：
- 迭代器：其迭代器是弱一致性 (weakly consistent) 的，不会抛出
ConcurrentModificationException。 - 适用场景：高并发环境下需要线程安全的
Map时的首选。
总结对比：
| 特性 | HashMap |
Hashtable |
ConcurrentHashMap (JDK 1.8+) |
|---|---|---|---|
| 线程安全 | 否 | 是 (全局锁 synchronized 方法) |
是 (CAS + synchronized 锁桶头节点) |
| 性能 | 高 (单线程) | 低 (高并发瓶颈) | 高 (高并发设计) |
null键/值 |
允许一个 null 键，多个 null 值 |
均不允许 | 均不允许 |
| 底层结构 | 数组+链表+红黑树 (JDK 1.8+) | 数组+链表 | 数组+链表+红黑树 (JDK 1.8+) |
| 扩容机制 | 容量x2 | 容量x2+1 | 容量x2 |
| 迭代器 | Fail-fast | Fail-fast (通常) | Weakly consistent (不抛 CME) |
| 推荐使用 | 单线程或外部同步 | 不推荐，已过时 | 高并发线程安全场景首选 |
简单来说，如果不需要线程安全，用 HashMap；如果需要线程安全且追求高并发性能，用 ConcurrentHashMap；Hashtable 则尽量避免使用。
参考小林coding和JavaGuide