TL：DR

他们将键映射到值。

哈希映射可能是映射概念最常用的实现。 它们允许将任意对象与其他任意对象关联。

这对于执行诸如通过某些公共属性将数据分组或连接在一起之类的工作非常有用。

基础结构执行以下操作：

· 计算密钥的哈希

· 修改散列以给出0到存储桶数组大小之间的整数

· 遍历所选存储桶中的链表，比较键的相等性

· 当/如果键匹配，则返回与该键关联的值。

基本结构

命名

我称这些为哈希图，但根据语言或上下文的不同，它们可以具有不同的名称。

在C＃或Python中，粗略的等效项是一个Dictionary。

在JAVAscript中，可以使用内置的Map类，但是可以以类似于哈希图的方式使用JavaScript对象。 在后台，Javascript不使用哈希图，因为它可以进行一些优化。

Java有一个名为HashMap的类，它也有HashTable，这基本上是相同的。 但是，通常建议在HashTable上使用HashMap。

如果看到称为Dictionary / hashmap / hashtable的内容，则可以将它们视为此故事中描述的数据结构（主要是）。

哈希函数

顾名思义，哈希图会执行"哈希"操作。 此操作需要一个任意对象并返回一个整数。 哈希函数的工作方式可能会填满自己的故事，甚至可能更多。

出于本故事的目的，可以将哈希函数视为执行以下操作的黑盒：

Integer hash = hashFunction(someArbitraryObject);

那为什么有用呢？ 好吧，如果您可以将任何对象转换为整数，则可以使用该整数导航到数组的索引。 这就是hashmap的作用，基本步骤如下：

· 把握关键和价值

· 计算密钥的哈希

· 使用散列查找数组的索引

· 将键和值存储在数组中

这里有一点复杂。 哈希函数可以返回哈希值，该哈希值的范围介于整数的最大负值和正值之间。 我们不希望数组中包含数十亿个元素，因为这将占用太多空间。 我们也没有数组中负索引的概念。

理想情况下，我们希望索引介于0到某个数组的合理大小之间，例如100。

undefined

为此，我们需要两个函数，绝对函数和模数。

绝对函数将使任何负数成为正数，因此-34671变为+34671。

模函数用于计算数字相对于另一个的余数。 例如，如果我们使用100作为要模数的数字，则：

· 0模量100 = 0

· 1模数100 = 1

· 2模数100 = 2

· 3模数100 = 3

· …

· 47模数100 = 47

· …

· 99模数100 = 99

直到达到100。在100处，模数导致返回值循环回到0。

所以，

· 100模量100 = 0

· 101模数100 = 1

· 102模数100 = 2

· …

· 147模数100 = 47

· …

· 199模量100 = 99

依此类推，直到达到200。在200处，返回值循环回到0，并开始向上计数回到99，直到我们要模数的值达到300，然后返回值回到0，然后重复并重复，然后 重复。

因此，模数函数可用于将任何（正）整数映射到介于0和我们要模数的值之间的范围内。

给定一个绝对函数和一个模函数，我们可以将我们的散列整数转换为和整数，该范围是我们想要的：

Integer sizeOfArray = array.size();
// hashedInteger is somewhere between -BigNumber -> +BigNumberInteger 
hashedInteger = hashFunction(key);
// absInteger is somewhere between 0 -> +BigNumberInteger 
absInteger = absolute(hashedInteger);
// modInteger is somewhere between 0 -> sizeOfArrayInteger 
modInteger = modulus(absInteger, sizeOfArray);

一旦我们的整数处于数组大小的范围内，就需要将键和值存储在该数组中。

一系列的水桶

因此，哈希表的另一部分是"存储桶数组"。 这是一个包含其他列表的数组。 这些其他列表通常是链接列表，您可以在我的故事中找到有关链接列表的更多信息。

我们采用哈希的，绝对的，模整数，并使用该整数来选择存储桶数组的索引。 然后，我们获取我们的密钥和价值，并将其存储在存储桶中。 存储桶是一个链接列表，我们将键和值存储在此列表的末尾。

键和值对称为"条目"。 条目是一个简单的包装对象，其中包含键和值。

插入东西

现在，我们有很多事情：

· 我们可以采用任意对象并将其哈希/吸收/修改为适合我们数组的整数

· 我们知道数组存储条目的链接列表。

· 条目包含键-值对。

我们可以结合使用它们来描述键值对如何存储在哈希图中：

· 给定键-值对

· 计算密钥的哈希

· 将哈希值转换为介于0和数组大小之间的值

· 在转换后的哈希的索引处找到链接列表

· 将键-值对作为条目添加到链接列表的末尾

就完成了。

键值已存储，然后可以查询。 在继续进行哈希表查询之前，有必要讨论在哈希表中存储元素的时间复杂性。

简短的答案是它是O（1）或恒定时间。 也就是说，随着哈希图变大，存储键值对的时间不会改变。 这是因为组成哈希表中事物存储的各种操作都是O（1）时间复杂度：

· 计算哈希为O（1）（或者至少它应该是一个复杂的主题，这里不再赘述）。

· Abs / Mod为O（1）

· 从数组中获取元素是O（1）。 我在数组列表上还有另一个故事。 数组和数组列表不是一回事，但是它们具有许多时间复杂度特征。

· 向链接列表的末尾添加元素是O（1）。 我在链接列表上的故事对此进行了讨论。

随着这些操作的变大，哈希表的增长都不会变慢，因此插入哈希表的总体操作也不会随着哈希表的增长而变慢。

拿东西

现在，我们的哈希图充满了键-值对，如果提供键就可以得到我们的值，这将非常有用。 其工作方式如下：

· 给定键（但无值）

· 计算密钥的哈希

· 将哈希值转换为介于0和数组大小之间的值

· 在转换后的哈希的索引处找到链接列表

· 开始浏览链接列表中的每个条目

· 对于每个条目，请询问输入键和条目中保持的键是否相等

· 如果它们不相等，则转到下一个条目

· 如果它们相等，则从条目中返回值

通过这些步骤，我们可以获取我们的密钥，并将其映射为一个值。 密钥的约束是您需要能够询问两个密钥是否相等。 在Java中，这不是问题，因为每个对象都实现一个.equals（）方法。

此操作的时间复杂度是多少？ 与插入地图的情况相比，这是一个更复杂的问题。 时间复杂度非常取决于您在找到具有匹配键的条目之前必须在链接列表中迭代多少个条目。

有2种极端情况：

· 所有条目都放在一个桶中

· 所有条目均已完美均匀地分布在所有可用存储桶中

所有条目都放在一个存储桶中

一种可能的情况是，所有键都被散列/ abs /修改为相同的数组索引。 在这种情况下，所有条目都将添加到同一链接列表中，并且找到与我们的键匹配的条目将花费O（N）（或线性）时间。 在此讨论在链表中找到元素的原因是O（N）。

线性时间复杂度意味着，随着哈希图变大，在其中查找元素所花费的时间也与哈希图的大小成比例地变大。 如果哈希图增长了100倍，那么花费的时间也将增长约100倍。

这种情况并不理想，那么我们如何到达这里呢？

undefined

理想情况下，我们需要一个"好的"哈希函数，该函数返回均匀分布的哈希整数，这些整数将全部转换为数组中均匀分布的索引。

所有条目均已完美均匀地分配

从哈希映射中获取数据时，理想的情况是每个条目均已均匀分布在存储桶中。 这导致每个链接列表包含相同数量的条目的情况。

对于哈希映射，这是最好的情况，因为可以在大致相等的时间内检索每个条目，并且该时间段是最小的。

从具有均匀分布的条目的哈希图中检索项目的时间复杂度为O（N / k），其中，N是哈希图所保存的条目数，而k是该图具有的存储桶数。

什么哈希图适合

映射任意值

顾名思义，它们擅长映射事物。 您可以将数组视为将整数0到N映射到任意值的一种方式。 如果您要处理整数，这很好，但否则就没有用。

映射允许您从任意对象映射到另一个任意对象。 它可以是字符串，整数或具有多个字段的对象。

只要可以将键用于生成哈希码，并且可以将其与其他键进行相等性检查，则可以在地图中使用该对象。

在Java中，每个对象都需要实现.hashcode（）和.equals（）方法，因此Java中的每个对象都可以在映射中使用。

一个常见的用例是在对象列表之间进行联接。 例如，假设我们有一个像这样的对象：

public BookDTO { private String id; private String name;}

假设我们有2个BookDTO列表："用户喜欢的图书"和"正在销售的图书"。 企业所遵循的逻辑是，他们希望向用户展示用户喜欢的，正在出售的书籍。 为此，我们需要找到两个列表都通用的所有书籍。

一种方法是浏览用户喜欢的每一本书，并浏览每本出售的所有书籍。 这将是不理想的，因为它涉及经历所有可能的组合。

一种替代方法是从2个列表中制作2个地图，每个地图ID到BookDTO。 然后，浏览用户喜欢的每本书，使用该ID从另一张地图中拉出所有正在出售的书。 使用这种方法，我们只需遍历地图即可加入任何相关书籍，而不必尝试每种组合。

分组信息

通过一些通用属性对信息进行分组是很常见的事情。 例如，假设我们要计算一个字符串在任意字符串列表中出现的次数。

表示其输出的一种方法是将String映射为Integer。 该代码可以编写如下：

public Map<String, Integer> countItems(List<String> items) { 
	Map<String, Integer> stringToCount = new HashMap<>(); 
  for (String item in items) { 
    if (!stringToCount.containsKey(item)) { 
      stringToCount.put(item, 0); 
    } 
  Integer currentCount = stringToCount.get(item); 
  Integer newCount = currentCount + 1; stringToCount.put(item, newCount); 
  } 
  return stringToCount;
}

因此对于输入：

["Foo", "Bar", "Foo", "Baz"]

输出为：

{ "Foo": 2, "Bar": 1, "Baz": 1}

这是一个相对简单的示例，但是如果您正在处理事务并决定要按用户对用户的所有事务进行分组，则将它们表示为用户ID到List [Transaction]的映射可能是实现该分组的一种有用方法 。

什么哈希图不好

存储订购的信息

如果您想以有序的方式存储信息，则哈希映射不是很好。 通常，哈希图不保证可以迭代其条目的顺序，因此您不能依赖于已将订单项添加到与迭代顺序有任何关系的哈希图中的顺序。

这里有一些反例。 在Java中，存在LinkedHashMap类，该类允许按插入顺序迭代条目。 还有一些排序的映射，可以按顺序迭代具有显式顺序的键。

存储重复信息

哈希图中的键定义值的身份。 如果您尝试为同一键存储多个值，则这些值将被覆盖。 这与可以多次重复添加同一对象的列表不同。

解决此问题的简单方法是将要存储的值更改为多次插入的对象的列表。

摘要

哈希图是一种非常有用的数据结构，用于将某些任意数据映射到其他任意数据。

他们依靠良好的哈希函数，模数函数和"存储桶"列表。

地图的一些标准用例是将2个数据集合结合在一起，或通过一些公用密钥将数据分组在一起。

关于作者

嗨，我是Doogal，我是一位技术主管，花了很多年的时间从几位非常有才华的人那里学习软件工程，而这些故事正是我努力使之付诸实践的方法。

在担任技术主管期间，我曾指导过许多新软件工程师，并且我发现经常存在工程师不知道自己不知道的情况的情况。 因此，"每个软件工程师应该知道的事情"系列是我在做软件的第一年里会给自己提供的信息的摘要。

软件是一个很大的主题，黄金法则是，任何问题的答案都可以以"取决于……"开头，因此，这些故事中的信息并不完整。 这是一种尝试提供基本信息的尝试，因此在阅读这些故事时，请记住，兔子洞比此处显示的主题要深。

我可以在Facebook，LinkedIn或Doodl.la上找到。

(本文翻译自Doogal Simpson的文章《Things every engineer should know: Hashmaps》，参考：https://medium.com/swlh/things-every-engineer-should-know-hashmaps-b354088206b5)