Java Map常见面试题

你好，面试官 | 你拿Java Map考验老干部？

面试官：请说下对理解HashMap及LinkedHashMap的理解（八股文） (qq.com)

你用过哪些Map？

HashMap、 LinkedHashMap、TreeMap、ConCurrentHashMap

• 一般涉及到键值对的存取，我们第一时间想到的就是HashMap
• 如果需要根据Key顺序实现存储键值对，TreeMap较为合适，TreeMap底层基于红黑树实现，键值都不能为null，时间复杂度O(logn)。
• LinkedHashMap是通过为键值对维护一个双向链表，可以用在模拟LRU缓存淘汰策略上。
• ConCurrentHashMap是基于分段锁和CAS实现的支持并发的线程安全Map。

对 Hash 算法的理解？

简单来说，其实它就是一种将任意长度的输入转为为固定长度的输出的映射规则。

比如说我用过的有md5、sha、sm3。

由于任意长度—>固定长度，随着 hash 次数增加，后面必定出现 哈希冲突。

HashMap的Hash函数的实现？

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

以上可以看到key==null时，直接返回0，所以HashMap中键为NULL的键值对，一定在第一个桶中。

h >>> 16是用来取出h的高16位(>>>是无符号右移) 如下展示：

HashMap是用(length - 1) & hash来计算数组下标的。绝大多数情况下length一般都小于2^16即小于65536。所以hash & (length-1)；结果始终是hash的低16位与（length-1）进行&运算。要是能让hash的高16位也参与运算，会让得到的下标更加散列。

如何让高16也参与运算呢。方法就是让hashCode()和自己的高16位进行^运算。由于与运单和或运单都会使得结果偏向0或者1，并不是均匀的概念，所以用异或。

为什么HashMap的底层数组长度总是2的n次方

当底层数组的length为2的n次方时， hash & (length - 1) 就相当于hash % length，其效率要比直接取模高得多，这是HashMap在效率上的一个优化。

有哪些办法解决Hash冲突呢？

HashMap中采用的是 链地址法 。

解决Hash冲突方法有:开放定址法、再哈希法、链地址法（拉链法）、建立公共溢出区。

• 开放定址法：也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。
• 再哈希法(双重散列，多重散列)：提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做增加了计算的时间。
• 链地址法(拉链法)：将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
• 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

HashMap 的底层数据结构？

JDK1.7的数据结构是数组+链表

JDK1.8的数据结构是数组+链表+红黑树。

数据结构示意图如下，Node为HashMap的内部类，实现了Map.Entry接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果 链表长度>8 且 数组大小>=64，链表转为红黑树
• 如果红黑树节点个数<6 ，转为链表

JDK8 HashMap 为什么引入红黑树？解决什么问题？

引入红黑树我认为是这样 当产生 hash 冲突时会形成链表 当数据多了冲突多了 链表越来越长 造成链化 此时查询将特别耗时 本来时间复杂度为O(1) 结构可能达到 O(n)，引入红黑树可以优化查询。

为什么使用红黑树而不是AVL树呢？

JDK 1.8中为什么HashMap使用红黑树而不是普通的AVL树

1. 平衡性要求相对较低：在HashMap中，我们更关注插入和查找操作的性能，而不是绝对的平衡性。红黑树相对于AVL树来说，需要更少的旋转操作，因此插入和删除操作的性能更好。
2. 实现简单：红黑树的实现相对较为简单，而AVL树的实现相对较复杂。在Java的HashMap实现中，为了保持代码的简洁性和可读性，选择了红黑树作为链表的替代结构。
3. 性能优化：在实际的使用场景中，链表转换为红黑树的阈值是经过一系列测试和优化得出的。红黑树相对于AVL树来说，可以提供更好的性能，因此在HashMap中选择了红黑树。

HashMap的扩容过程？

Hashmap的初始容量是16。这个在代码中定义如下：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

负载因子loadFactor为 0.75。

Map 在使用过程中不断的往里面存放数据，当数量超过了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

HashMap的快速存取

hashMap中最常用的两个操作就是put(Key,Value)和get(Key)。

当我们调用put方法存值时，HashMap首先会调用Key的hashCode方法，然后基于此值获取Key的哈希码，通过哈希码快速找到某个位置，这个位置可以被称之为 bucketIndex。

根据equals方法与hashCode的协定可以知道，如果两个对象的hashCode不同，那么equals一定为 false；如果其hashCode相同，equals也不一定为true。所以，理论上，hashCode 可能存在碰撞的情况

这时会取出bucketIndex桶内已存储的元素（如果该桶next引用不空，即有了链表也要遍历链表），并通过hashCode()和equals()来逐个比较以判断Key是否已存在。

如果已存在，则使用新Value值替换旧Value值，并返回旧Value值；如果不存在，则存放新的键值对<Key, Value>到链表中。

get(Key)时候算出哈希值，定位到桶，获得第一个元素。如果第一个元素与目标值相等，返回。如果桶中不止一个节点，看看是不是TreeNode（判断是树还是链表），分别调用各自的查找方法。

HashMap 多线程操作导致死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。

• 比如线程1、2同时进行put操作，并且发生了hash冲突。不同的线程在不同的时间片获得CPU执行的机会，当线程1执行完hash冲突判断后，由于时间片耗尽挂起，线程2先完成了插入操作。随后，线程1获得时间片，由于之前已经进行过hash碰撞的判断，于是线程1会直接插入，导致<u>线程2插入的数据被线程1覆盖</u>了。
• 还有一种情况，线程 1 执行 if(++size > threshold) 判断时，假设获得 size 的值为 10，由于时间片耗尽挂起。线程 2 也执行 if(++size > threshold) 判断，获得 size 的值也为 10，并将元素插入到该桶位中，并将 size 的值更新为 11。随后，线程 1 获得时间片，它也将元素放入桶位中，并将 size 的值更新为 11。线程 1、2 都执行了一次 put 操作，但是 <u>size 的值只增加了 1</u>，也就导致实际上只有一个元素被添加到了 HashMap 中。

并发环境下，可以使用 Hashtable，因为它的方法加了synchronized，可以做到线程安全。

不过，由于它锁的是整个表，导致效率低下。因此，我们一般使用的是 ConcurrentHashMap 。

散列表是new HashMap()时创建的么？

不是在new HashMap()创建的，它使用懒加载，是当第一次调用 put() 方法时 执行putVal() 时才创建散列表。

LinkedHashMap概述

HashMap是无序的，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。

HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。

<img src="https://img.tucang.cc/api/image/show/bf8928fc5942e7c392138f8d7a92ac95" alt="LinkedHashMap 逻辑结构" style="zoom: 67%;" />

该迭代顺序可以是插入顺序，也可以是访问顺序(accessOrder=true)。其中LinkedHashMap的默认实现是按插入顺序排序的。

LinkedHashMap的get方法

get 方法是 LinkedHashMap 增删改查操作中唯一一个重写的方法， accessOrder 为 true 的情况下， 它会在元素查询完成之后，将当前访问的元素移到链表的末尾。

LinkedHashMap 和 HashMap 遍历性能比较

LinkedHashMap 维护了一个双向链表来记录数据插入的顺序，因此在迭代遍历生成的迭代器的时候，是按照双向链表的路径进行遍历的。这一点相比于 HashMap 那种遍历整个 bucket 的方式来说，高效需多。

LinkedHashMap 如何实现 LRU 缓存？

将 accessOrder 设置为 true 并重写 removeEldestEntry 方法。

当链表大小超过容量时返回 true，使得每次访问一个元素时，该元素会被移动到链表的末尾。一旦插入操作让 removeEldestEntry 返回 true 时，视为缓存已满，LinkedHashMap 就会将链表首元素移除，由此我们就能实现一个 LRU 缓存。

ConcurrentHashMap概述

ConcurrentHashMap JDK1.7 引入了分段锁，数据结构采用Segment数组+HashEntry数组+链表。Segment 继承了 ReentrantLock，一个 Segment[i] 就是一把分段锁。比起 Hashtable 锁粒度更细，性能更高。

JDK1.8 后，它做出了很大改变，数据结构采用Node数组+链表+红黑树，抛弃Segment分段锁，采用CAS+synchronized，锁粒度更细，只锁住链表头节点（红黑树根结点），不影响其他哈希桶数组元素的读写，提高并发度。

ConcurrentHashMap为什么不支持 null value

vaule 为 null，有两种情况，可能是存的值为 null 或则是没有映射到值 返回null；

HashMap 用于单线程下可以通过 ContainsKey() 区分这两种情况；

但是 ConcurrentHashMap用于多线程场景，本来是没有映射 ContainsKey() 返回fasle，但是可能在你调用 ContainsKey() 检查时新线程插入null值，返回ture，存在二义性