什么是哈希表（HashTable）？

哈希表简介

哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做 哈希表（散列表）。 哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分：

• 向哈希表中插入一个关键字：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中
• 在哈希表中搜索一个关键字：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值

哈希表的原理示例图如下所示：

• 插入关键字：哈希函数对关键字进行哈希，得到哈希值后插入到哈希表对应的地方
• 搜索关键字：哈希函数对关键字进行哈希，基于哈希值去哈希表中进行查询

哈希表的应用举例：

哈希表在生活中的应用也很广泛，其中一个常见例子就是「查字典」。 比如为了查找赞这个字的具体意思，我们在字典中根据这个字的拼音索引 zan，查找到对应的页码为 599。然后我们就可以翻到字典的第 599 页查看赞字相关的解释了。

查找索引这一过程可以看作是哈希函数操作