乘法散列法

作者：追风剑情发布于：2019-1-28 12:47 分类：Algorithms

下面介绍几种常用的构造哈希函数的方法

1.直接地址法
直接地址法的哈希函数H对于关键字是数值类型的数据，直接利用关键字求得哈希地址。
H(k_i)=ak_i+b（a、b 为常量）
在使用时，为了使哈希地址与存储空间吻合，可以调整 a和 b。例如，取 H(k_i)=3*k_i+5。直接地址法的特点是哈希函数简单，并且对于不同的关键字，不会产生冲突。但在实际问题中，由于关键字集合中的元素很少是连续的，用该方法产生的哈希表会造成空间的大量浪费。因此，这种方法很少使用。

2.数字分析法
数字分析法是假设有一组关键字，每个关键字由 n 位数字组成，如 k₁k₂...k_n。数字分析法是从中提取数字分布比较均匀的若干位作为哈希地址。
例如，对于一组关键字 k₁～k₈ 的序列{100011211,100011322,100011413,100011556,100011613,100011756,100011822,100011911}，可以取第 6 位和第 7 位作为哈希地址，即： H(k₁)=12,H(k₂)=13,H(k₃)=14, H(k₄)=15,H(k₅)=16, H(k₆)=17, H(k₇)=18, H(k₈)=19。

3.除留余数法
除留余数法是用关键字 k_i 除以一个合适的、不大于哈希表长m的正整数p所得余数作为哈希地址的方法。对应的哈希函数 H(k_i)为：
H(k_i) = k_i MOD p
其中，MOD 表示求余数运算符。用该方法产生的哈希函数的好坏取决于p值的选取。实践证明，当p取小于哈希表长m的某个素数时，产生的哈希函数较好。除留余数法是一种简单且行之有效的构造哈希函数的方法。

4.平方取中法
平方取中法是取关键字平方的中间几位作为散列地址的方法，具体取多少位根据实际情况而定。即：
H(k_i)=k_i;的平方的中间几位
这也是一种常用的较好的设计哈希函数的方法。关键字求平方后使得它的中间几位和组成关键字的各位值均有关，从而使哈希地址的分布更为均匀，减少了发生冲突的可能性。

s指头尾要截掉的位数，平方后不足4s（即8位）位的高位补0。

5.折叠法
折叠法是首先把关键字分割成位数相同的几段（最后一段的位数可少一些)，段的位数取决于哈希地址的位数，由实际情况而定，然后将它们的叠加和舍去最高进位作为哈希地址的方法。
与平方取中法类似，折叠法也使得关键字的各位值都对哈希地址产生影响。

在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与 3 个因素有关。

（1）与装填因子α有关。所谓装填因子是指哈希表中已存入的记录数 n 与哈希地址空间大小 m 的比值，即α=n/m，α越小，冲突的可能性就越小；α越大（最大可取 1)，冲突的可能性就越大，这很容易理解，因为a越小，哈希表中空闲单元的比例就越大，所以待插入记录同已插入存在的记录发生冲突的可能性就越小；反之，α越大，哈希表中空闲单元的比例就越小，所以待插入记录同已插入存在的记录冲突的可能性就越大；另一方面，α 越小，存储空间的利用率就越低；反之，存储空间的利用率也就越高。为了既兼顾减少冲突的发生，又兼顾提高存储空间的利用率这两个方面，通常使最终的α控制在 0.6～0.9 的范围内。

（2）与所采用的哈希函数有关。若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生；否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。

（3）与解决冲突的哈希冲突函数有关。哈希冲突函数选择得好坏也将减少或增加发生冲突的可能性。

解决哈希冲突的方法

1.开放地址法
开放地址法又分为线性探测再散列、二次探测再散列和随机探测再散列。
假设哈希表空间为A[0...m-1]，哈希函数为H(k_i)。
(1) 线性探测再散列
线性探测再散列解决冲突求“下一个”地址的公式是:
d₁=H(k_i)
d_j=(d_j-1+1) MOD m j=2,3,...

(2) 二次探测再散列
二次探测再散列解决冲突求"下一个"地址的公式是:
d₁=H(k_i)
d_j+1=(d₁+j²) MOD m
该方法的缺陷是不易探查到整个散列空间。

(3) 随机探测再散列
随机探测再散列解决冲突求"下一个"地址的公式是:
d₁=H(k_i)
d_j+1=(d₁+R) MOD m
其中:

2.链地址法
当存储结构是链表时，一般采用链地址法，用链地址法处理冲突的方法是：把具有相同散列地址的关键字值放在同一个链表中，称为同义词链表。通常把具有相同哈希地址的关键字都存放在一个同义词链表中，有m 个散列地址就有m个链表，同时用数组h[0..m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以 h[i]为结点的单链表中。

乘法散列公式

k: 关键字
A: 常数 (0 < A < 1)
kA mod 1: 取kA的小数部分
m: 一般选择它为2的某个幂次(m=2^p)

推导公式
假设某计算机的字长为w位，而k正好可用一个单字表示。限制A=s/2^w的一个分数，其中s是一个取自0<s<2^w的整数。那么s=A●2^w

h(k)=对r0取p个最高有效位(即，h(k)=r0>>(w-p))
A一般取下面的这个值比较理想

下面给出一个代码示例(C#版)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
/// <summary>
/// 乘法散列法 测试
/// </summary>
namespace HashTest
{
    class Program
    {
        static void Main(string[] args)
        {
            for(int i=123454; i< 123459; i++)
            {
                Console.WriteLine("hash1 ({0})={1}", i, CalHash1(i));
                Console.WriteLine("hash2 ({0})={1}", i, CalHash2(i));
            }

            //注: 由于方案一中的A值与方案二中选的s值存在精度差，所以部分数据计算的结果不相同。
            
            Console.Read();
        }

        //计算方案一
        public static double CalHash1(int k)
        {
            int p = 14;
            //选一个0-1之间的小数
            double A = 0.6180339887;//(Math.Sqrt(5) - 1) / 2;
            //选一个2的幂次方的m值
            double m = Math.Pow(2, p);
            //直接套用公式计算
            double hash = Math.Floor(m * (k * A % 1));
            return hash;
        }

        //计算方案二 (优化版) 推荐
        public static int CalHash2(int k)
        {
            double s = 2654435769;//推荐值
            double ks = k * s;
            int r0 = (int)(ks % int.MaxValue);//余数
            int hash = r0 >> 18;//取高14位 (可以根据实际的存储大小调整取高几位)
            return hash;
        }
    }
}

运行测试

//计算字符串Hash
public static int GetHashCode(string str)
{
	if (string.IsNullOrEmpty(str))
		return 0;
	//BKDR Hash
	ulong hash = 0;
	//也可以乘以31、131、1313、13131、131313..
	uint p = 131;
	for (int i = 0; i < str.Length; i++)
	{
		//当作p进制计算,参考2进制转10进制
		hash = hash * p + str[i];
	}
	return (int)hash;
}

标签: Algorithms