先把信息放上来，然后我们再讨论。

02-Java核心技术面试讲座-资源分享

Map 是通用 Java 集合框架的另一部分，也是该框架中最常用的类型之一。

首先，它本身及相关类型自然是采访、考察的热点。

今天我想问你的问题是， 和 之间有什么区别？谈谈你

掌握。

典型答案

, , 是一些最常见的Map实现，它们以键值对的形式存储。

以及操作数据的容器类型。

它是早期Java类库提供的哈希表实现。 它是同步的，不支持空键和

值，但由于同步带来的性能开销，很少推荐使用它。

它是一种应用较为广泛的哈希表实现，其行为与

它不是同步的，并且支持空键和值。通常，执行 put 或

get操作可以达到恒定时间的性能，因此是大多数key-value访问场景的首选。

例如，实现用户ID和用户信息对应的运行时存储结构。

它是一个基于红黑树的Map，提供顺序访问。 与它不同的是，它得到，

put等操作的时间复杂度为O(log(n))。 具体顺序可以通过指定

来决定，或者基于键的自然顺序。

测试点分析

上面的答案只是一些基本功能的简单总结。 Map相关的问题还有很多可以拓展。

数据结构、典型应用场景以及程序设计和实现的技术考虑，特别是Java 8，

其本身发生了非常大的变化，这些都是经常被审视的方面。

很多朋友向我反映，面试官似乎很喜欢他们正在检查的设计和实现细节，所以今天我将补充一下

添加相应的源码解读，主要关注以下几个方面：

除了典型的代码分析之外，还有一些经常被提及的有趣的并发相关问题，例如

在并发环境下，可能会出现无限循环占用CPU、大小不准确等奇怪的问题。

我认为这是显式声明非线程安全的数据结构时的典型使用错误，例如

如果忽略这一点，单纯在多线程场景下使用，必然会出现问题。

了解导致此错误的原因也是深入了解并发程序如何运行的好方法。至于到底发生了什么，你

你可以参考这个很久以前的分析，甚至还提供了示意图。 别人写过的我就不重复了。

了解Map相关整体结构，尤其是有序数据结构的一些要点。

从源码分析设计和实现点，了解容量、负载系数等，以及为什么需要这些

参数，它们如何影响Map性能，如何在实践中进行权衡等等。

了解树改造的相关原理以及改进的原因。

知识扩展

1.地图整体结构

首先我们对Map相关类型有一个整体的了解。 虽然Map通常包含在Java集合框架中，

但它本身并不是狭义上的集合类型()。 具体可以参考下面的简单类图。

更具体地说，作为一种类似于 Stack 的早期集合相关类型，它是以下类型的扩展

类，类结构明显不同于类。

其他 Map 实现已扩展为包含通用方法抽象。否

同一个Map的目的可以从类图结构中体现出来，而设计目的则在不同的接口中得到了体现。

大多数使用Map的场景通常是插入、访问或删除，对顺序没有特殊要求。

在这种情况下它基本上是最好的选择。性能

有效性，请务必掌握and的一些基本约定，例如：

平等，必须平等。

即使重写，也必须重写。

关于这个话题网上有很多资料，这里不再赘述。

对于有序Map的分析内容比较有限，我会补充一些，虽然和

两者都能保证一定的顺序，但还是有很大不同的。

这种行为适用于一些特定的应用场景。 比如我们建立一个空间敏感的资源池，希望

自动释放最不常访问的对象，这可以通过使用提供的机制来实现。

考虑以下示例：

需要保持一致性，状态改变返回的哈希值仍然必须一致。

对称性、反射、透射等特性。

通常提供的是遍历顺序符合插入顺序，这是通过提供条目（键值

右）维护一个双向链表。 请注意，使用特定的构造函数，我们可以创建反映访问顺序的实例，

所谓的put、get等都算作“访问”。

上一讲我给大家留下的问题提到，构建优先级调度系统的问题本质上是一个

对于典型的优先级队列场景，Java标准库提供了基于二叉堆的实现。 他们都依靠

依赖相同的分类机制，当然也包括背心。

与and的约定类似，为了避免歧义，自然顺序也需要符合一个

一个约定是返回值需要与 一致，否则会出现歧义。

我们可以分析一下put方法的实现：

因为，它的整体顺序是由按键的顺序关系决定的，通过或

（自然顺序）来决定。

从代码中你能看出什么？当我不遵循约定时，有两个不满足 () 要求

这些对象被视为相同的对象（因为返回 0），这可能会导致不明确的行为。

2. 源码分析

前面提到，设计和实现是一个非常高频的面试问题，所以我在这里提供一个相对详细的来源。

代码解读主要集中在：

首先我们看一下内部结构，可以看成是一个数组（Node[]

由表）和链表组成的复合结构。 数组被划分为()，由hash值决定。

该数组中键值对的寻址； 具有相同哈希值的键值对以链表的形式存储。 您可以参考以下示例。

这里需要注意的是，如果链表大小超过阈值（，8），

链表将转变为树结构。

内部实行基点分析。

容量（）和负载系数（负载）。

树。

从非拷贝构造函数的实现来看，这个表（数组）似乎一开始就没有初始化。 只设定了

只是一些初始值。

因此，我们深深怀疑，可能是根据惰性加载原理，在第一次使用时就进行了初始化（复制）。

除了shell构造函数之外，这里我只介绍最常见的场景）。 既然这样，我们来看看put方法的实现，

似乎只有一个调用：

看来主密码似乎就藏在里面了。 有什么秘密吗？为了节省篇幅，我只在这里截取

以下是一些更关键的部分。

从该方法的前几行，我们可以发现几个有趣的事情：

如果表为null，则该方法负责初始化它，从tab=()可以看出。

该方法兼顾了两种职责，创建初始存储表，或者在容量不满足需求时对其进行扩展。

允许（）。

在放置新的键值对的过程中，如果出现以下情况，就会发生扩容。

哈希表（数组索引）中特定键值对的位置取决于以下位操作：

仔细观察哈希值的来源，我们会发现它并不是密钥本身，而是来自于

另一种内部哈希方法。注意这里为什么需要将高位数据移至低位。

那么异或运算呢？这是因为有些数据计算出的哈希值的差异主要在高位，而

寻址会忽略容量以上的高位，因此这种处理可以有效避免类似情况下的哈希冲突。

可以看到方法本身的逻辑非常集中，从初始化、扩展到树的形成，一切都与之相关。

建议大家在阅读源码时参考上面的主要逻辑。

下面我再进一步分析一下身兼多职的方法。 很多朋友反映，面试官经常问到源码设计的问题。

数数。

我前面提到的链表结构（这里称为bin）当达到一定的阈值时就会变成一棵树。 我稍后会解释。

分析一下为什么要对bin进行处理。

根据源代码，不考虑极端情况（理论最大容量限制由下式指定）

值为 1