地图和字典面试必备代码

基本的

搜寻和移除

迭代

全地图操作

多图

不同类型的

学习并编写一份速查表

映射（Map）是编程中基础数据结构之一。除了列表（List）之外，映射也是面试题中常用的数据结构。掌握映射的使用方法能帮助你避免很多面试题的难题。

许多算法的解决方案都在于正确使用地图。你越了解地图的用法，就越容易应用它。任何时候你需要组织数据或跟踪项目，地图都是首选工具之一。我将在后续文章中举例说明。

术语

关于地图的术语比较混乱。

Python 和 C# 更倾向于使用“字典”。字典是一种特定的一对一映射，其中键对应一个值。PHP 使用“关联数组”。C++ 使用“map”，并且还有“unordered_map”。在 Java 中，“HashMap”是其“Map”接口的常见实现。

最抽象的类型应该被称为“映射”。但除非你应聘的是语言设计职位，否则最好不要纠结于这些细节。面试时千万不要争论名称。学习你所应聘语言中使用的名称，并熟悉相关的术语。

参考

准备面试时，请参考这份资料。不要想当然地认为自己能完成每一项；花时间实际编写代码。你会惊讶地发现，一些看似简单的事情其实很难，或者一个瞬间的疏忽就可能让你功亏一篑。说实话，我觉得没有任何一种语言能让我凭记忆完成所有这些操作。面试前，我需要做好准备，温习一下相关知识。将这些操作融入到你的日常编程词汇中，在压力环境下会大有帮助。

💭 有些语言将映射（map）实现为不可变数据结构。然而，本文的措辞假设你使用的是可变映射。你仍然需要所有这些操作，但代码结构会有很大不同。请关注最终目标，而不是具体的措辞。

基本的

学习执行这些操作最常用的方法。每种语言都有其特殊语法，但在面试中最好还是专注于通用功能。对于不断发展的语言，务必不断更新知识，并留意不断变化的惯用法。

• 创建映射：使用最常用或通用的语言映射。对于静态类型语言，您需要指定键和值的类型。
• 添加带有键和值的元素：将键值对添加到映射中的基本方法。
• 按键检查元素是否存在：检查存在性是我们使用映射的主要原因。
• 按键获取元素：这在不同的语言之间差异很大，而且周围的代码通常也会发生变化。
• 获取地图的长度：几乎所有语言的语法都不同。
• 从地图上“查看并获取物品”的语言习语：这种组合很常见，许多语言都有特定的方式来组合这两个步骤。

搜寻和移除

一旦地图上的元素被标记出来，我们就需要有办法再次获取它们。

• 按键替换项目：添加值和替换值的语法可能有所不同。
• 按值查找项目：虽然这不是地图的主要用途，但有时按值查找项目也很有帮助，即使效率不高。
• 按键或默认值获取：一种常见的做法是查找键并返回其值，但如果键不存在，则返回默认值。大多数编程语言都提供了专门的实现方式。
• 按键删除元素：这将删除该元素的值及其对应的键。这与将键赋值为 null 不同。删除后，该键将不再存在。
• 清除地图：移除地图上的所有元素。

迭代

我们可能需要对映射中的所有元素执行某些操作。这可以使用语言的循环机制，也可以使用映射本身的特殊 for-each 函数。

• 遍历映射中的所有键值对：每次迭代都应该访问键和值。
• 遍历映射的键：你只想访问映射中存在的键，而不是值。
• 遍历映射中的值：你只想访问映射中存在的值，而不是键。
• 按排序顺序迭代：如果顺序不同，则按排序顺序迭代键值对。这可能需要使用不同的排序映射类型。

全地图操作

我们并不总是想使用完整的地图，或者可能希望单独查看某些项目。

• 生成地图的浅克隆：新地图将包含相同的实例。
• 将映射的值映射到新映射：对于静态类型语言，确保可以映射到新类型。
• 合并两个地图的内容：确定哪些值优先级最高。
• 按键筛选项目：创建地图或其视图，其中仅显示与某些键匹配的元素。
• 按值筛选项目：创建地图或其视图，其中仅显示与某些值匹配的元素。

多图

多重映射允许将多个值与同一个键关联起来。这些是 1:N 映射。它们不如 1:1 映射常见，但在某些算法问题中非常有用。

• 创建多重映射：如果你的语言不支持多重映射，请学习如何在普通映射中使用数组。
• 按键添加项目：如果键已存在，则最终会有两个值与同一个键关联。
• 遍历与某个键匹配的项：一个键可以有多个值。
• 删除与某个键匹配的项：删除与某个键匹配的单个项，但保留其他值。这可能会删除第一个或最后一个项，或者需要对该值进行额外的匹配。
• 替换所有与键匹配的项：确保多重映射中不再有具有该键的项。

不同类型的

使用多种数据类型作为键和值。不要只使用字符串作为键！熟练掌握映射的多种用法非常重要。

并非所有编程语言都支持所有类型作为键。它可能仅限于可哈希类型或具有自然顺序的类型。请务必了解您所使用的编程语言支持哪些类型。

学习并编写一份速查表

我已大致按常用程度从高到低排列了这些操作。请花些时间逐一了解。仅仅了解这些高级操作的存在，就能让你在解决算法问题时更加灵活。

如果你记不住所有语法点，那就为你的编程语言制作一份速查表。这对于电话面试非常有用。有些现场面试也允许携带参考资料。这样可以避免你浪费时间在网上搜索语法——对于一些基本操作来说，这可能很麻烦。