《计算思维与算法入门》 —2.9 哈希表

2.9    哈希表

哈希表是一种保存记录或数据的连续存储空间，通过使用哈希函数可以快速存取与查找数据，如图2-75所示。所谓哈希函数（Hashing Function），就是将记录或数据本身的键值经由特定数学函数的运算或使用其他的方法转换成对应记录或数据的存储地址。

图2-75  哈希表

下面我们来介绍哈希函数的相关名词。

      bucket（桶）：哈希表中存储数据的位置，每一个位置对应一个唯一的地址（bucket address）。桶就好比一个记录或数据。

      slot（槽）：每一个记录中可能包含好几个字段，而槽指的就是“桶”中的字段。

      collision（碰撞）：如果两个不同的数据经过哈希函数运算后对应相同的地址，就称为碰撞。

      溢出：如果数据经过哈希函数运算后，所对应的桶已满，就会使桶发生溢出。

      哈希表：保存记录的连续存储空间。哈希表是一种类似数据表的索引表，其中可分为n个桶，每个桶又可分为m个槽，如表2-4所示。

表2-4  索引表

      同义词（Synonym）：若两个标识符I1和I2经哈希函数运算后所得的数值相同，即f(I1) = f(I2)，则称I1与I2对于哈希函数f是同义词。

      加载密度（Loading Factor）：所谓加载密度，是指标识符的使用数目除以哈希表内槽的总数：

α值越大，表示哈希存储空间的使用率越高，碰撞或溢出的概率也会越高。

      完美哈希（perfect hashing）：指既没有碰撞又没有溢出的哈希函数。

在此建议大家，在设计哈希函数时应该遵循以下几个原则：

（1）降低碰撞和溢出的产生。

（2）哈希函数不宜过于复杂，越容易计算越佳。

（3）尽量把文字的键值转换成数字的键值，以利于哈希函数的运算。

（4）所设计的哈希函数计算得到的值尽可能均匀地分布在每一桶中，不要太过于集中在某些桶内，这样就可以降低碰撞并减少溢出的处理。