hash-table

文档摘要

id: 哈希表 title: 编码面试中的哈希表速查表 description: 编码面试中的哈希表学习指南，包括练习题、技巧、时间复杂度及推荐资源 keywords: [ 哈希表编码面试学习指南, 哈希表编码面试技巧, 哈希表练习题, 哈希表实用技巧, 哈希表时间复杂度, 哈希表推荐学习资源, ] sidebarlabel: 哈希表 tocmaxheadinglevel: 2 引言哈希表（通常称为哈希映射）是一种实现关联数组抽象数据类型的结构，这种结构可以将键映射到值。哈希表通过使用哈希函数对元素进行计算，得到一个索引，也称为哈希码，用于定位存储在桶或槽中的数据，从而找到所需的值。在查找过程中，先对键进行哈希运算，生成的哈希码指示了对应值的存储位置。


id: 哈希表  
title: 编码面试中的哈希表速查表  
description: 编码面试中的哈希表学习指南，包括练习题、技巧、时间复杂度及推荐资源  
keywords:  
  [
    哈希表编码面试学习指南,  
    哈希表编码面试技巧,  
    哈希表练习题,  
    哈希表实用技巧,  
    哈希表时间复杂度,  
    哈希表推荐学习资源,  
  ]  
sidebar_label: 哈希表  
toc_max_heading_level: 2

引言

哈希表（通常称为哈希映射）是一种实现关联数组抽象数据类型的结构，这种结构可以将键映射到值。哈希表通过使用哈希函数对元素进行计算，得到一个索引，也称为哈希码，用于定位存储在桶或槽中的数据，从而找到所需的值。在查找过程中，先对键进行哈希运算，生成的哈希码指示了对应值的存储位置。

哈希是空间与时间权衡的最常见例子之一。与其每次线性搜索数组以确定某个元素是否存在（这需要 O(n) 时间），不如先遍历一次数组，将所有元素哈希到哈希表中。判断元素是否存在只需简单地对元素进行哈希运算，然后查看该元素是否存在于哈希表中——平均情况下，这一操作的时间复杂度为 O(1)。

对于哈希冲突的情况，有多种冲突解决技术可供选择。在面试中，你不太可能被问及冲突解决技术的细节：

分离链式 —— 每个值都用一个链表来存储，以便保存所有发生冲突的项。
开放定址 —— 所有条目记录都直接存储在桶数组中。当需要插入新条目时，从哈希后的槽位开始，按照某种探测序列依次检查各个槽位，直到找到一个未被占用的槽位为止。

学习资源

阅读材料
- 把哈希表从货架上拿下来, basecs
- 剖析哈希函数, basecs
视频
- 核心：哈希表, 加州大学圣地亚哥分校
- (幻灯片), 塞缪尔·阿尔巴尼，剑桥大学

实现方式

语言	API
C++	`std::unordered_map`
Java	`java.util.Map`。使用 `java.util.HashMap`
Python	`dict`
JavaScript	`Object` 或 `Map`

时间复杂度

操作	大O	注释
访问	N/A	因为不知道哈希码，无法访问
查找	O(1)*
插入	O(1)*
删除	O(1)*

* 这是平均情况下的时间复杂度，但在面试中，我们只关注哈希表的平均情况。

示例题目

描述一种最少使用缓存的实现方式，并给出其大O表示法。
一道涉及API与哈希映射集成的题目，其中哈希映射的桶由链表构成。

必备题目

如果你正在备考这个主题，这些题目是必须练习的。