我在一次面试中被问到：“请告诉我你所知道的关于哈希表的所有内容。” 我简单地回答说：哈希表是一个数据结构, 它由键值对组成，使用哈希函数来定位元素, 并可以解决哈希冲突等问题。后来他们问我：“好的，现在请以5岁孩子听得懂的方式解释刚才说的所有内容，不要使用任何技术术语，特别是哈希和映射。” 这让我有些意外，我并没有给出好的答案。你会怎样回答呢？
面试问题：什么是哈希表？
32
- 999999
11
20我认为在面试中询问此类问题很愚蠢，除非这份工作是教授五岁孩子数据结构。 - WW.
5认真的说，即使是λ演算，也只适合八岁的孩子。 - Josh Lee
5我很抱歉没有意识到我在你的面前。 - Gnomo
24我们可以假设这个5岁的孩子有5年的算法经验吗？ - Woot4Moo
6@WW 我认为这有一定道理；过去我曾惊讶于有多少程序员并不真正了解哈希的概念。 - NullUserException
显示剩余6条评论
5个回答
50
规则。孩子们知道规则。他们知道某些物品应该放在特定的地方。HashMap就像一套规则，它告诉我们，对于一个物品（你的鞋子、最喜欢的书或衣服），有一个具体的地方是它们所属的地方（鞋架、书架或壁橱）。
因此，如果你想知道鞋子放在哪里，你知道要看鞋架上有没有鞋子。
但是等等：如果鞋架已经满了怎么办？有几个选项。
1）对于每个物品，有一系列可以尝试的位置。试着把它们放在门旁边。但是，那里已经有东西了：还能放哪里呢？试试衣柜。如果我们需要找到我们的鞋子，我们按照相同的列表进行搜索，直到找到它们。（探查序列）
2）买一个更大的房子，带一个更大的鞋架。（动态调整大小）
3）把鞋子堆叠在鞋架顶部，忽略这会使找到正确的鞋子很困难，因为我们必须浏览整个鞋堆才能找到它们。（链式存储）
- James
1
2我谷歌了哈希映射以弄清它们是什么。这实际上是我找到的迄今为止最好的、最通用的解释。非常棒。 - samuel
41
让我们拿起大型词典，试着找到单词斑马。我们可以轻易猜到斑马会在词典的最后面，就像字母“Z”在字母表的最后面一样。现在假设我们总能在大型词典中找到斑马的位置。这是我们可以快速找到斑马、大象或者其他任何东西在词典中的方法。有时候两个单词会出现在同一页上，比如苹果和蚂蚁。我们知道要找哪一页，但不确定苹果和蚂蚁离彼此有多近，直到我们找到那一页为止。有时候苹果和蚂蚁会出现在同一页上，有时候它们可能不在同一页上，因为有些大型词典里的词很多。
那就是我会这么做的。
那就是我会这么做的。
- Woot4Moo
8
10你正在描述一个排序索引，而不是哈希映射表。 - James
3你知道地图其实就是一本字典吗？现实中使用字典的目的是向5岁的孩子解释数据结构。 - Woot4Moo
1词典类比是错误的，即使对于一个5岁的孩子来说也是如此。ZEBRA在“书的末尾附近”，需要扫描，最好的情况是O（LogN），但对于一个5岁的孩子来说可能更接近于线性。页面453上的ZEBRA是O（1）。我会使用解码器环的类比来说明哈希函数。你把ZEBRA放进你的解码器环里，然后数字453就出来了——好吧，那么孩子，单词ZEBRA在第453页。 - Adisak
1虽然从技术上讲，HashMap是一个字典，但你的应用程序有缺陷，因为它太抽象了，无法回答问题。字典可以使用与HashMap没有任何相似之处的数据结构来实现（如树甚至只是数组）。这就像通过谈论矩形来描述正方形。 - nsfyn55
1做得很好。我很喜欢阅读它。 :) - Farhad
显示剩余3条评论
6
作为一个家长，如果我要向一个5岁的孩子解释哈希映射表，我会拿着一块巧克力纸杯蛋糕说出你所说的话。
说真的，像这样的问题应该意味着“你能用简单易懂的英语解释这个概念吗”，这是衡量你对它的理解程度的好启发式方法。既然你似乎明白了这一点，那么这个问题似乎有点傻。
- Steve B.
1
我必须点赞，因为我确实曾经向孩子们解释过复杂的技术概念（当一连串的“为什么？”问题到达某个程度时），只是给出了与我的技术同行相同的答案（甚至可能增加了复杂性），但是会跳跃兴奋地讲解。这通常能够满足他们的好奇心。 - Jon Hanna
5
地图保存的数据可以通过一些相关信息进行查找，就像书籍索引中的单词可以被用来查找页面一样。
使用HashMap的主要优点在于，就像书籍索引中的页码可以快速地查找到某个单词所在的页面，而不是一页一页地搜索该单词，HashMap也能够更快速地查找到需要的数据。
（我给你一个认真的答案，因为面试官可能想看看你能否向项目经理和客户等非技术人员解释技术概念的能力。也许直接使用HashMap并不是很有用，但它可能是翻译技能的公平指标之一。）
使用HashMap的主要优点在于，就像书籍索引中的页码可以快速地查找到某个单词所在的页面，而不是一页一页地搜索该单词，HashMap也能够更快速地查找到需要的数据。
（我给你一个认真的答案，因为面试官可能想看看你能否向项目经理和客户等非技术人员解释技术概念的能力。也许直接使用HashMap并不是很有用，但它可能是翻译技能的公平指标之一。）
- brabster
3
您有一本空白但编号的书和一个特殊的解码器环，只要在里面输入什么东西，就会生成一个页面编号。
要赋值：
您获得一个ID（键）和一个消息（值）。
将ID放入特殊的解码器环中，它会输出页面编号。
打开您的书到该页。如果ID在页面上，请划掉ID/消息。
现在在页面上写下ID和消息。如果已经有一个或多个其他带有消息的ID，请在其下方写下新的ID和消息。
要检索值：
您只获得一个ID（键）。
将ID放入特殊的解码器环中，它会输出页面编号。
打开您的书到该页。如果ID在页面上，请阅读跟随其后的消息（值）。
要赋值：
您获得一个ID（键）和一个消息（值）。
将ID放入特殊的解码器环中，它会输出页面编号。
打开您的书到该页。如果ID在页面上，请划掉ID/消息。
现在在页面上写下ID和消息。如果已经有一个或多个其他带有消息的ID，请在其下方写下新的ID和消息。
要检索值：
您只获得一个ID（键）。
将ID放入特殊的解码器环中，它会输出页面编号。
打开您的书到该页。如果ID在页面上，请阅读跟随其后的消息（值）。
- Adisak
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接