哈希表是什么?

一、哈希表是什么

哈希表（Hash table）又叫散列表，是一种可以根据键值（Key value）直接访问的数据结构。哈希表会通过某种哈希算法计算一个键值的函数（这个函数也叫哈希函数或散列函数），并将所查询的数据映射到某个位置以供访问，借此加快查找特定键值的速度。

哈希表的工作原理可以用这样一个直观的例子来说明：

字典中收录了大量汉字的信息。为了便于快速找到某个字，可以首先创建一个按照每个字的拼音字母顺序排列的表（也就是字典开头部分的“拼音检字表”），这就类似于在每个字和拼音字母之间建立了一种函数关系。要查找某个字时，只需在这个表中依次定位首字母、第二个字母、第三个字母…… 以此类推，大部分时候甚至不需要完整查找该字拼音的每个字母，就能确定这个字在字典中对应的准确位置。

在上述例子中，“查找拼音的第n的字母”就是哈希函数的函数法则，而“拼音检字表”就可以理解为一种哈希表（或散列表）。

延伸阅读：

二、什么是哈希值（hash code）

哈希值是一个int类型的整数。每个元素都应该有自己的哈希值，并且这个值是少数的。即满足：

A.如果元素a与元素b相等，则元素a的哈希值与元素b的哈希值相等。

B.如果元素a与元素b不相等，则元素a的哈希值与元素b的哈希值不相等。

通常情况下，对于int,bool,double,string等语言自带的类型都有自己的哈希值，可以用它们的哈希函数来获取，不同语言的哈希函数可能会不同。

如果是用户自己新建的类型，则需要提供计算此类型元素哈希值的哈希函数。

在哈希表中，我们是通过某元素的哈希值来查找、添加或删除元素的。