直接定址法

直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k或 H（k）=a×k+b ； (其中a,b为常数)
例 有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图：

可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。

如果我们要统计的是80后出生的人口数，如上表所示，那么我们队出生年份这个关键字可以用年份减去1980来作为地址，此时f(key)=key-1980

这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。

适用：地址集合的大小与关键字集合的大小相同情况下，其中a和b为常数。

数字分析法

假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

例 要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：

分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。

适用：能预先估计出全体关键字的每一位上各种数字出现的频度。

折叠法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。两种叠加处理的方法：
移位叠加：将分 割后的几部分低位对齐相加；
边界叠加：从一端沿分割界来回折叠，然后对齐相加。

所谓折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位），这方法称为折叠法。这种方法适用于关键字位数较多，而且关键字中每一位上数字分布大致均匀的情况。
折叠法中数位折叠又分为移位叠加和边界叠加两种方法，移位叠加是将分割后是每一部分的最低位对齐，然后相加；边界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

例 当哈希表长为1000时，关键字key=110108331119891，允许的地址空间为三位十进制数，则这两种叠加情况如图：
由折叠法求哈希地址：

用移位叠加得到的哈希地址是559，而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串，则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。

适用：关键字的数字位数特别多。

平方取中法

平方取中法是一种常用的哈希函数构造方法。这个方法是先取关键字的平方，然后根据可使用空间的大小，选取平方数是中间几位为哈希地址。

哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。
例 若设哈希表长为1000则可取关键字平方值的中间三位，如图所示：

下面给出平方取中法的哈希函数

1
2
3
4
5
6
7
8
9
10

//平方取中法哈希函数，结设关键字值32位的整数
//哈希函数将返回key * key的中间10位
Int  Hash (int key){
    //计算key的平方
    Key * = key ;
    //去掉低11位
    Key>>=11;
    // 返回低10位（即key * key的中间10位）
    Return key %1024;
}

适用：关键字中的每一位都有某些数字重复出现频度很高的现象。

减去法

减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

例 公司有一百个员工，而员工的编号介于1001到1100，减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息，因为编号1000以前并没有数据，所有员工编号都从1001开始编号。

基数转换法

将十进制数X看作其他进制，比如十三进制，再按照十三进制数转换成十进制数，提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数，并且两个基数应该是互素的。
例 Hash(80127429)=(80127429)13=8137+0136+1135+2134+7133+4132+2*131+9=(502432641)10如果取中间三位作为哈希值，得Hash（80127429）=432

为了获得良好的哈希函数，可以将几种方法联合起来使用，比如先变基，再折叠或平方取中等等，只要散列均匀，就可以随意拼凑。

除留余数法

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为
h（k）=k % p ，其中%为模p取余运算。
例 已知待散列元素为（18，75，60，43，54，90，46），表长m=10，p=7，则有

h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4
h(43)=43 % 7=1 h(54)=54 % 7=5 h(90)=90 % 7=6
h(46)=46 % 7=4

此时冲突较多。为减少冲突，可取较大的m值和p值，如m=p=13，结果如下：

h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8
h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12
h(46)=46 % 13=7

此时没有冲突，如图所示。

理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。

随机数法

设定哈希函数为:H(key) = Random(key)其中，Random 为伪随机函数

实际构造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，以及哈希表长度（哈希地址范围），总的原则是使产生冲突的可能性降到尽可能地小。

适用：对长度不等的关键字构造哈希函数。

随机乘数法

也称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积fk的分数部分在0～1之间，用这个分数部分的值与n（哈希表的长度）相乘，乘积的整数部分就是对应的哈希值，显然这个哈希值落在0～n-1之间。其表达公式为：Hash(k)=「n(fk%1)」其中“fk%1”表示fk 的小数部分，即fk%1=fk-「fk」

例 对下列关键字值集合采用随机乘数法计算哈希值，随机数f=0.103149002 哈希表长度n=100得图：

此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究，他认为f取任何值都可以，但某些值效果更好。(如f=（-1）/2=0.6180329…比较理想)

字符串数值哈希法

在很都情况下关键字是字符串，因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数

1
2
3
4
5
6
7
8

Int Hash _ char (char *X)
{
  int I ,sum
  i=0;
  while (i 10 && X[i])
  Sum +=X[i++];
  sum%=N;      //N是记录的条数
  }

这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址，只要N较小，Hash地址将较均匀分布[0，N]区间内，因此这个函数还是可用的。对于N很大的情形，可使用下列函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int ELFhash (char *key )
{
 Unsigned long h=0,g;
whie (*key)
{
h=(h<<4)+ *key;
key++;
g=h & 0 xF0000000L;
if (g) h^=g>>24;
h & =～g;
}
h=h % N
return （h）;
}

这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入，并通过一种方式把字符的十进制值结合起来，对长字符串和短字符串都有效，这种方式产生的位置不可能不均匀分布。

旋转法

旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上，而是搭配其他哈希函数使用。
例 某学校同一个系的新生（小于100人）的学号前5位数是相同的，只有最后2位数不同，我们将最后一位数，旋转放置到第一位，其余的往右移。

运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。