定义

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

一句话说：散列的实质就是在元素的存储位置和它的关键码（key）之间建立一种函数映射关系。使得关键码和存储位置一一对应：

               Address=hash(key)

散列函数

  • 取余法（或者叫除留余数法），常用
  • 数字分析法
  • 平方取中法(mid-square)
  • 折叠法

取余法的散列函数表示为：
hash ( key ) = key % p p<=m

除数选择：设散列表允许的地址数为m，取一个不大于m，但是最接近或等于m的质数p作为除数。

冲突解决技术

因为不同的key，可能散列之后映射到相同的地址，所以冲突解决是很有必要的。冲突解决可以分为两类：

  • 开散列方法 ( open hashing，拉链法，separate chaining，链地址法)
  • 闭散列方法 ( closed hashing，开地址方法，open addressing )。
    • 线性探查法 (linaer probing）
    • 二次探查法 (quadratic probing)
    • 双散列法

区别：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

  • 搜索成功的平均搜索长度ASL： 是指搜索到表中已有元素的平均探查次数；
  • 搜索不成功的平均搜索长度ASL：是指在表中搜索不到待查的元素，但找到插入位置的平均探查次数。即从每个位置起到第一个为空的位置时的探查次数的和的平均数。

注：内容大部分是对《数据结构 / 殷人昆》散列表的总结。