数据结构-哈希函数

数据结构-哈希函数

哈希查找

之前的查找算法，时间复杂度为O(n)，或者O(㏒2n)，其效率取决于“比较”的次数。

   即使对于采取排序树结构的查找表，由于每一次比较的结果，如果关键字与数据元素不相等，则有“大于”或者“小于”两个结果，所以下一步会有两种可能的方向，因此O(㏒2n)已经是最优了。

哈希表（Hash Table）采取另一种算法，其查找的时间复杂度最快可以达到O(1)，即只要给出关键字，立刻就可以查找到该元素。

实际应用中大量采取哈希表的方式，很多编程语言中内置了哈希查找的方式，如java中的HashTable，HashSet等。

基本思想
将记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。

  1. 哈希函数(Hash函数)
 f : 关键字 → 存储位置。即，hash函数是指关键字与存储位置（哈希地址）的对应关系，只要给出关键字，就可以通过这个函数得到存储位置。

如：给定一个保存了10个元素的数组
[ 0 1 2 3 4 5 6 7 8 9 ]

如果给定Hash函数f(K)=K mod 10，就可以立刻得到该键值对应元素的数组下标

如果给定Hash函数f(K)=K mod 2，则虽然也缩小了查找范围，但达不到上面函数的效果

哈希函数的冲突

如果不同的键值，被Hash函数映射到同样的一个哈希地址，则称为冲突（ki?kj，H(ki)=H(kj)）

同义词：具有相同函数值的两个不同的关键字，称为该哈希函数的同义词。

   Hash函数不可能完全避免冲突，只可能尽量减少冲突，或者说，好的Hash函数能将关键字映射后得到的哈希地址，尽量均匀地分布

设计Hash表的时候，除了采用好的Hash函数之外，如何有效地处理冲突，也是很重要的一方面

哈希表：

 根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址区间上，并以关键字的映像作为记录在表中的存储位置。

映射过程称为哈希造表，或者散列（哈希表有时也叫散列表）
所得的存储位置值称为哈希地址或者散列地址

哈希函数的构造

   哈希函数是一种映象，其设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。哈希函数“好坏”的主要评价因素有：

◆ 散列函数的构造简单；
◆ 关键字经哈希函数映射后，得到的地址是等概率的，即“均匀”的，这样的Hash函数称为“均匀的哈希函数”

好的Hash函数，可以减少关键字的冲突。

直接定址法：取关键字或者关键字的某个线性函数作为Hash地址，即：
    H(key) = key
    H(key) = a×key + b，a、b为常数
特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突，但实际中很少使用，因为需事先知道关键字的分布情况。
数字分析法：取关键字的若干位或组合作为哈希地址
平方取中法：将关键字平方后取中间几位作为哈希地址
折叠法：将关键字分割成位数相同的几部分(最后一部分可以不同)，然后取这几部分的叠加和作为哈希地址

除留余数法（取模）
    把关键字对某个数p（不大于哈希表的表长m）取模，所得到的数作为哈希地址
     H(key) = key MOD p, p≤m

    利用这种方法的关键是p的选取，p选的不好，容易产生同义词。
     根据经验：若散列表表长为m，通常p为小于或等于表长（最好接近表长m）的 质数；或不包含小于20质因子的合数（如：23*29）。

随机数法
    H(key) = random(key)，把产生的随机数做为哈希地址。
     当散列表中关键字长度不等时，该方法比较合适。

哈希函数只能使哈希地址均匀分布，但不能避免冲突，因此冲突处理是不可避免的

    构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。即：Hi=RHi(key)     i=1, 2, …, k
    RHi ：一组不同的哈希函数。第一次发生冲突时，用RH1计算，第二次发生冲突时，用RH2计算…依此类推知道得到某个Hi不再冲突为止。