哈希表

Mike大约 2 分钟

哈希表的理论知识

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数。

对不同的关键字可能得到同一散列地址，即k1 != k2，而f(k1) = f(k2)，这种现象称为冲突（Collision）。

散列表的载荷因子定义为：a = 填入表中的元素个数 / 散列表的长度

a是散列表装满程度的标志因子。由于表长是定值，a与"填入表中的元素个数"成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，a越小，表明填入表中的元素越少，产生冲突的可能性就越小。

对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。