C++程序设计之哈希表

1、       哈希法又名散列法，因其英文单词Hash而得名，是一种特殊的查找方法。

       在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结构中一个惟一的存储位置相对应，这样查找时只需对节点的关键字进行某种运算就能确定节点在表中的位置。

2、哈希表把数据的存放地址A定义为记录关键字K的函数，称为哈希（hash）函数。

A=H(k)

一个哈希表包括3个内容

1、确定表的空间范围，即确定哈希函数值域。

2、构造合适的哈希函数。

3、选择处理冲突的方法，即避免出现相同的哈希函数值。

3、构造哈希表首先要选择合适的哈希函数。

4、自身函数：

       关键字自身作为哈希函数，即H(k)=k，也可自身加上一个常数作为哈希函数，即H(k)=k+c。

5、数字分析法

       设元素是以r为基的数，且表中元素的可能值已知，从中任意取出相当多的元素进行分析，取其中位置分布比较均匀的若干位组成哈希函数值。

6、平方取中法

       把元素值平方后有目的地选取中间的若干位作为哈希地址。

7、叠加法

       把元素值分割成位数相同的部分（最后一部分的位数如果不够，不足位可空缺），然后把这几个部分的叠加和（舍去进位）作为哈希地址。

8、除余法

       选择一个适当的正整数m，用m去除关键字，取其余数作为散列地址，即H(key)=key%m。

注：m应取小于存储区容量的素数。