散列表(hash table) - webdancer's Blog

散列表(hash table)

webdancer posted @ 2012年4月29日 18:58 in 算法 , 1283 阅读

  1.散列表概念

     散列表(hash table ,hash map)是一种使用散列函数将“键”映射到“值”的数据结构,这样散列表实现了字典结构。示意图如下:

     散列函数(hash function)将“键”转为bucket的索引,正如在上一篇介绍散列函数是说的,一般情况下散列表不是理想散列,会发生“碰撞”(即不同的键映射到了相同的的值)。

    使用散列解决的一个核心问题就是查找(search)。散列的思想是是把键的某些内容打乱,使用这种部分的信息作为查找的开始。为了使用散列表,我们需要解决两个问题:寻找散列函数(hash function)和解决“碰撞”。

2.散列函数

一个良好的散列函数要满足两个条件:

  1. 容易计算。
  2. 最小化“碰撞”。概率的角度看,就是要求散列函数应该让散列值服从一个均匀分布,一个非均匀的分布,在概率大的地方,显然容易发生“碰撞”。设计一个散列函数,让散列值服从均匀分布是困难的。

设计良好的散列函数一直是一个有挑战性的工作。通常有两种:基于除法和基于乘法。

  1. 取余法。h(k)=k%M 。M的取值对于散列函数影响较大,通常M取一个素数,使得r^k <> a ,其中r为键字符集合级数,k,a是较小的数。
  2. 乘法方法。

image其中:w是计算机字数目,A是一个w互素的常数。

3.解决“碰撞”

1.独立拉链。这种解决方法思路很简单,就是将发生“碰撞”的<键,值>对用链表连接起来。如下图:

2.开放寻址。这种方法是确定某种规则,通过它,某个键K来确定一个“探查序列”,即表中的某些位置,每当查找或是插入K时,这些位置就会被探查。最简单的方法是:线性开放寻址散列,即当发生“碰撞”时,把<键,值>对存到下一个可用的bucket中去。如下图:

两种方法比较:

评价准则:负载因子(loading factor): a= n / b 其中:n为元素数目;b为bucket的数目。

更多的信息,大家可以参考wikipedia或是taop。

参考:wikipedia ,taop


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee