第二大脑

主题

2026-08-25
3560
13.7m

集合之 Map ​

面试题 Java 集合 Map

HashMap 和 HashTable 有什么区别？ ​

  • HashMap 允许键和值是 null，而 Hashtable 不允许键或者值是 null。
  • Hashtable 是同步的，而 HashMap 不是。因此，HashMap 更适合于单线程环境，而 Hashtable 适合于多线程环境。
  • HashMap 提供了可供应用迭代的键的集合，因此，HashMap 是快速失败的。另一方面，Hashtable 提供了对键的列举 (Enumeration)。
  • 由于 Hashtable 继承自 Dictionary 类。而这个类已经基本上废弃了，所以一般认为 Hashtable 是一个遗留的类。

Java 中 HashMap 的 key 值要是为类对象， ​

则该类需要满足什么条件？

需要重写 equals() 和 hashCode() 方法。

谈一下 HashMap 的特性？ ​

1.HashMap 存储键值对实现快速存取，允许为 null。key 值不可重复，若 key 值重复则覆盖。

2.非同步，线程不安全。

3.底层是 hash 表，不保证有序 (比如插入的顺序)；

谈一下 HashMap 的存储结构？ ​

1.7 版本：数组 + 链表

1.8 版本：数组 + 链表 + 红黑树

1601014772919-0eeebe2b-48fa-433d-8826-22da064bcfcf.jpeg

图中，紫色部分即代表哈希表，也称为哈希数组（默认数组大小是 16，每对 key-value 键值对其实是存在 map 的内部类 entry 里的），数组的每个元素都是一个单链表的头节点，跟着的绿色链表是用来解决冲突的，如果不同的 key 映射到了数组的同一位置处，就会采用头插法将其放入单链表中。

HashMap 在 JDK1.7 和 JDK1.8 中有哪些不同？ ​

1601014772888-d0815eff-1832-4b91-94c6-eb3fce9992e1.webp

说一下 HashMap 扩容机制？何时进行扩容？ ​

HashMap 使用的是懒加载，构造完 HashMap 对象后，只要不进行 put 方法插入元素之前，HashMap 并不会去初始化或者扩容 table。
当首次调用 put 方法时，HashMap 会发现 table 为空然后调用 resize 方法进行初始化，当添加完元素后，如果 HashMap 发现 size（元素总数）大于 threshold（阈值），则会调用 resize 方法进行扩容。

扩容过程：

若 threshold（阈值）不为空，table 的首次初始化大小为阈值，否则初始化为缺省值大小 16 默认的负载因子大小为 0.75，当一个 map 填满了 75% 的 bucket 时候（即达到了默认负载因子 0.75），就会扩容，扩容后的 table 大小变为原来的两倍（扩容后自动计算每个键值对位置，且长度必须为 16 或者 2 的整数次幂）

若不是 16 或者 2 的幂次，位运算的结果不够均匀分布，显然不符合 Hash 算法均匀分布的原则。

反观长度 16 或者其他 2 的幂，Length-1 的值是所有二进制位全为 1，这种情况下，index 的结果等同于 HashCode 后几位的值。只要输入的 HashCode 本身分布均匀，Hash 算法的结果就是均匀的。

假设扩容前的 table 大小为 2 的 N 次方，元素的 table 索引为其 hash 值的后 N 位确定扩容后的 table 大小即为 2 的 N+1 次方，则其中元素的 table 索引为其 hash 值的后 N+1 位确定，比原来多了一位重新调整 map 的大小，并将原来的对象放入新的 bucket 数组中。这个过程叫作 rehashing

因此，table 中的元素只有两种情况：
元素 hash 值第 N+1 位为 0：不需要进行位置调整
元素 hash 值第 N+1 位为 1：将当前位置移动到 原索引 + 未扩容前的数组长度  的位置
扩容或初始化完成后，resize 方法返回新的 table

遍历 map 集合的三种方式？ ​

java
public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    //添加方法
    map.put("我的昵称", "小红");
    map.put("我的名字", "Fcant");
    map.put("我的简书", "js_hcx");
    map.put("我的网站", "www.yuque.com/fcant");

    //map集合中遍历方式一： 使用keySet方法进行遍历       缺点：keySet方法只是返回了所有的键，没有值。
    Set<String> keys = map.keySet();  //keySet() 把Map集合中的所有键都保存到一个Set类型 的集合对象中返回。
    Iterator<String> it = keys.iterator();
    while (it.hasNext()) {
        String key = it.next();
        System.out.println("键：" + key + " 值：" + map.get(key));
    }

    //map集合的遍历方式二： 使用values方法进行 遍历。    缺点：values方法只能返回所有 的值，没有键。
    Collection<String> c = map.values(); //values() 把所有的值存储到一个Collection集合中返回。
    Iterator<String> it2 = c.iterator();
    while (it2.hasNext()) {
        System.out.println("值：" + it2.next());
    }

    //map集合的遍历方式三：entrySet方法遍历。
    Set<Map.Entry<String, String>> entrys = map.entrySet();
    //因为Iterator遍历的是每一个entry，所以也用泛型：<Map.Entry<String,String>>
    Iterator<Map.Entry<String, String>> it3 = entrys.iterator();

    while (it3.hasNext()) {
        Map.Entry<String, String> entry = it3.next();
        System.out.println("键：" + entry.getKey() + " 值：" + entry.getValue());
    }
}

并发集合和普通集合区别？ ​

并发集合常见的有 ConcurrentHashMap、ConcurrentLinkedQueue、ConcurrentLinkedDeque 等。并发集合位于 java.util.concurrent 包下,是 jdk1.5 之后才有的。
在 java 中有普通集合、同步（线程安全）的集合、并发集合。
普通集合通常性能最高，但是不保证多线程的安全性和并发的可靠性。
线程安全集合仅仅是给集合添加了 synchronized 同步锁，严重牺牲了性能，而且对并发的效率就更低了，并发集合则通过复杂的策略不仅保证了多线程的安全又提高的并发时的效率。

HashMap 的 put() 和 get() 原理？ ​

put() 原理： ​

1.根据 key 获取对应 hash 值：int hash = hash（key.hash.hashcode（））

2.根据 hash 值和数组长度确定对应数组引 int i = indexFor(hash, table.length);
简单理解就是 i = hash 值% 模以 数组长度（其实是按位与运算）。如果不同的 key 都映射到了数组的同一位置处，就将其放入单链表中。且新来的是放在头节点。

get() 原理： ​

通过 hash 获得对应数组位置，遍历该数组所在链表（key.equals（））

HashCode 相同，冲突怎么办？ ​

采用“头插法”，放到对应的链表的头部。
因为 HashMap 的发明者认为，后插入的 Entry 被查找的可能性更大，所以放在头部。（因为 get() 查询的时候会遍历整个链表）。

HashMap 是线程安全的吗？为什么？在并发时会导致什么问题？ ​

不是，因为没加锁。

hashmap 在接近临界点时，若此时两个或者多个线程进行 put 操作，都会进行 resize（扩容）和 ReHash（为 key 重新计算所在位置），而 ReHash 在并发的情况下可能会形成链表环。在执行 get 的时候，会触发死循环，引起 CPU 的 100% 问题。

注：jdk8 已经修复 hashmap 这个问题了，jdk8 中扩容时保持了原来链表中的顺序。但是 HashMap 仍是非并发安全，在并发下，还是要使用 ConcurrentHashMap。

HashMap 如何判断有环形表？ ​

创建两个指针 A 和 B（在 java 里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针 A 每次向下移动一个节点，让指针 B 每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
通俗易懂一点：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。

介绍一下 ConcurrentHashMap？ ​

结构如下：

1601014772954-d6a49655-0584-42c0-8a5b-a942b5217309.webp

hashmap 是由 entry 数组组成，而 ConcurrentHashMap 则是 Segment 数组组成。
Segment 本身就相当于一个 HashMap。
同 HashMap 一样，Segment 包含一个 HashEntry 数组，数组中的每一个 HashEntry 既是一个键值对，也是一个链表的头节点。
单一的 Segment 结构如下：

1601014772911-7e75c819-d5d7-4416-890b-f60a73f621bb.webp

Segment 对象在 ConcurrentHashMap 集合中有 2 的 N 次方个，共同保存在一个名为 segments 的数组当中。

可以说，ConcurrentHashMap 是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。（这样类比理解多个 hashmap 组成一个 cmap）

ConcurrentHashMap 的 put() 和 get() 原理？ ​

put() 原理： ​

1.为输入的 Key 做 Hash 运算，得到 hash 值。

2.通过 hash 值，定位到对应的 Segment 对象

3.获取可重入锁

4.再次通过 hash 值，定位到 Segment 当中数组的具体位置。

5.插入或覆盖 HashEntry 对象。

6.释放锁。

get() 原理： ​

1.为输入的 Key 做 Hash 运算，得到 hash 值。

2.通过 hash 值，定位到对应的 Segment 对象

3.再次通过 hash 值，定位到 Segment 当中数组的具体位置。

由此可见，和 hashmap 相比，ConcurrentHashMap 在读写的时候都需要进行二次定位。先定位到 Segment，再定位到 Segment 内的具体数组下标。

为什么 ConcurrentHashMap 和 hashtable 都是线程安全的，但是前者性能更高呢？ ​

因为前者是用的分段锁，根据 hash 值锁住对应 Segment 对象，当 hash 值不同时，使其能实现并行插入，效率更高，而 hashtable 则会锁住整个 map。

并行插入：当 cmap 需要 put 元素的时候，并不是对整个 map 进行加锁，而是先通过 hashcode 来知道他要放在那一个分段（Segment 对象）中，然后对这个分段进行加锁，所以当多线程 put 的时候，只要不是放在同一个分段中，就实现了真正的并行的插入。

注意：在统计 size 的时候，就是获取 ConcurrentHashMap 全局信息的时候，就需要获取所有的分段锁才能统计（即效率稍低）。

分段锁设计解决的问题：

目的是细化锁的粒度，当操作不需要更新整个数组的时候，就仅仅针对数组中的一部分行加锁操作。

ConcurrentHashMap 为何不支持 null 键和 null 值？ ​

HashMap 是支持 null 键和 null 值，而 ConcurrentHashMap 却不支持
查看源码如下：
HashMap:

java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

ConcurrentHashMap:

java
/** Implementation for put and putIfAbsent */
final V putVal (K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int   hash = spread(key.hashCode());
    int   binCount = 0;
    ......
}

原因：通过 get(k) 获取对应的 value 时，如果获取到的是 null，此时无法判断它是 put（k,v）的时候 value 为 null，还是这个 key 从来没有做过映射（即没有找到这个 key）。而 HashMap 是非并发的，可以通过 contains(key) 来做这个判断。而支持并发的 Map 在调用 m.contains（key）和 m.get(key),m 可能已经不同了。

HashMap1.7 和 1.8 的区别？ ​

1.为了加快查询效率，java8 的 HashMap 引入了红黑树结构，当数组长度大于默认阈值 64 时，且当某一链表的元素>8 时，该链表就会转成红黑树结构，查询效率更高。
2.优化扩容方法，在扩容时保持了原来链表中的顺序，避免出现死循环

红黑树: 一种自平衡二叉树，拥有优秀的查询和插入/删除性能，广泛应用于关联数组。对比 AVL 树，AVL 要求每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1，而红黑树通过适当的放低该条件（红黑树限制从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，结果是这个树大致上是平衡的），以此来减少插入/删除时的平衡调整耗时，从而获取更好的性能，而这虽然会导致红黑树的查询会比 AVL 稍慢，但相比插入/删除时获取的时间，这个付出在大多数情况下显然是值得的。

ConcurrentHashMap1.7 和 1.8 的区别？ ​

1.8 的实现已经抛弃了 Segment 分段锁机制，利用 Node 数组 +CAS+Synchronized 来保证并发更新的安全，底层采用数组 + 链表 + 红黑树的存储结构。

1601014773042-2dcf6f20-71ff-4ea9-b5e1-c20f4e20b2a9.jpeg

CAS ​

CAS，全称 Compare And Swap（比较与交换），解决多线程并行情况下使用锁造成性能损耗的一种机制。java.util.concurrent 包中大量使用了 CAS 原理。

JDK1.8 中的 CAS ​

Unsafe 类，在 sun.misc 包下，不属于 Java 标准。Unsafe 类提供一系列增加 Java 语言能力的操作，如内存管理、操作类/对象/变量、多线程同步等。其中与 CAS 相关的方法有以下几个：

java
1//var1为CAS操作的对象，offset为var1某个属性的地址偏移值，expected为期望值，var2为要设置的值，利用JNI来完成CPU指令的操作
2public final native boolean compareAndSwapObject(Object var1, long offset, Object expected, Object var2);
3public final native boolean compareAndSwapInt(Object var1, long offset, int expected, int var2);
4public final native boolean compareAndSwapLong(Object var1, long offset, long expected, long var2);

CAS 缺点 ​

  • ABA 问题。当第一个线程执行 CAS 操作，尚未修改为新值之前，内存中的值已经被其他线程连续修改了两次，使得变量值经历 A->B->A 的过程。
    解决方案：添加版本号作为标识，每次修改变量值时，对应增加版本号；做 CAS 操作前需要校验版本号。JDK1.5 之后，新增 AtomicStampedReference 类来处理这种情况。
  • 循环时间长开销大。如果有很多个线程并发，CAS 自旋可能会长时间不成功，会增大 CPU 的执行开销。
  • 只能对一个变量进原子操作。JDK1.5 之后，新增 AtomicReference 类来处理这种情况，可以将多个变量放到一个对象中。

更新: 2020-09-25 14:26:45
原文: <https://www.yuque.com/fcant/notes/rcz883&gt;

最近更新