Skip to content

用于编码面试的散列表清单

原文:https://www.techinterviewhandbook.org/algorithms/hash-table/

简介

哈希表(通常称为哈希映射)是一种实现关联数组抽象数据类型的数据结构,这种结构可以将键映射到值。哈希表使用元素上的哈希函数来计算桶或槽数组中的索引,也称为哈希代码,从中可以找到所需的值。在查找过程中,对键进行哈希运算,得到的哈希表示相应值的存储位置。

哈希是时空权衡最常见的例子。我们可以遍历数组一次,将所有元素散列到一个散列表中,而不是每次都线性搜索数组来确定元素是否存在,这需要 O(n)时间。确定元素是否存在是一个简单的问题,即散列元素并查看它是否存在于哈希表中,这平均为 O(1)。

在哈希冲突的情况下,有许多冲突解决技术可以使用。在面试中,你不太可能被问到冲突解决技术的细节:

  • 独立链接 -每个值使用一个链表,这样它就存储了所有冲突的条目。
  • 开放寻址 -所有条目记录都存储在桶数组本身中。当需要插入一个新条目时,将检查存储桶,从散列到的槽开始,按某种探测序列进行,直到找到一个未被占用的槽。

学习资源

实现

语言 应用程序接口
C++ T2std::unordered_map
Java 语言(一种计算机语言,尤用于创建网站) java.util.Map 。使用 java.util.HashMapjava.util.TreeMap (首选)
计算机编程语言 T2dict
Java Script 语言 ObjectMap

时间复杂度

操作 大 O 注意
接近 不适用的 由于哈希码未知,无法访问
搜索 o(1)*
插入 o(1)*
去除 o(1)*

** 这是平均情况,但是在采访中我们只关心哈希表的平均情况。*

样题

  • 描述一个最少使用的缓存的实现,以及它的 big-O 符号。
  • 一个涉及 API 与 hash map 集成的问题,其中 hash map 的桶由链表组成。

基本问题

如果你在学习这个话题,这些是需要练习的基本问题。

推荐练习题

这些是在你为题目学习并练习了基本问题后推荐练习的问题。

推荐课程

AlgoMonsterT3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式,并有内容帮助你快速修改基本的数据结构和算法。最重要的是,AlgoMonster 不是基于订阅的——支付一次性费用,就可以获得终身访问今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题,但从问题模式的角度来进行练习,这是一种我也同意的学习方法,我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题,并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式,而不是背答案! 现在获得终身使用权→

掌握编码面试:数据结构+算法

这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星,21.5k 评分,135k 学生),包含了价值 19 个小时的内容。像技术面试手册一样,它超越了编码面试,涵盖了简历,非技术面试,谈判。是一个全包!请注意,JavaScript 用于编码演示。 结账→



回到顶部