月度归档:2016年08月

散列表

作者:余俊峰 tobecontinued.cn

散列表(Hash table,也叫哈希表),是根据键而直接访问存储位置的数据结构。

它通过一个计算键值的函数,将所需查询的数据映射到表中一个位置来访问记录。这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

基本概念

1、若关键字为k,则其值存放在f(k)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系为散列函数,按这个思想建立的表为散列表。
2、对不同的关键字可能得到同一散列地址,即k1 ≠ k2,而f(k1) = f(k2)。这种现象称为冲突(Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。
3、若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function)。这样就导致关键字经过散列函数得到一个“随机的地址”,从而减少冲突。