数据结构哈希查找

数据结构之查找

• 哈希查找
• • 哈希函数构造方法
  • 冲突解决办法
  • 哈希查找分析

哈希查找

哈希查找是通过设定的哈希函数H(key)和处理冲突的办法将关键字映射的一个地址集（区间），并将关键字在地址集中的“像”作为在表中的存储地址，这个表就是哈希表，对应的这个影响过程就是哈希造表或者散列。

哈希函数构造方法

• 直接定址法

  H(key)=a*key+b

• 除数求余法

  H(key)=key mod p;(p<m)

• 数字分析法

  观察关键字的数字分布，取其中几位作为哈希地址。

• 随机数法

  H(key)=randm(key)

• 平方取中法
• 折叠法

冲突解决办法

• 开放定址法：

  Hi=（H(key)+di）mod m；

  m为哈希表长。

  其中di为增量序列有下面两类探测方法：

• 再链接法：

将所有经过哈希函数映射后的相同地址存储在同一线性表中。

哈希查找分析