哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　7、负载因子 我们把 h(key)的值域所对应到的地址空间称为“基本区域” ，发生碰撞时，同义词可以存放在 基本区域还没有被占用的单元里，也可以放到基本区域以外另开辟的区域中（称为“溢出区”。 ） 下面引入散列的一个重要参数“负载因子或装填因子(Load Factor)” ，它定义为： а = 基本区域能容纳的结点 数 负载因子的大小对于碰撞的发生频率影响很大。直观上容易想象，а 越大，散列表装得越满， 则再要载入新的结点时碰上已有结点的可能性越大，冲突的机会也越大。特别当а ＞1 时碰撞是不 可避免的。一般总是取а ＜1，即分配给散列表的基本区域大于所有结点所需要的空间。当然分配 的基本区域太大了也是浪费。例如，某校学生干部的登记表，每个学生干部是一个结点，用学号 做关键码，每个学号用 7 位数字表示，如果分配给这个散列表的基本区域为 10 个存储单元，那么 散列函数就可以是个恒等变换，学号为 7801050 的学生结点就存入相对地址为 7801050 的单元， 这样一次碰撞也不会发生，但学校仅几百个学生干部，实际仅需要几百个单元的空间，如果占用 了 10 个存储单元，显然太浪费了，所以这是不可取的。负载因子的大小要取得适当，使得既不过 多地增加碰撞，有较快的检索速度，也不浪费存储空间。 下面结合引例说明一下上面的思想和方法。 【例 1】用散列存储线） 。 分析： 假定选取的散列函数为：h(K)=K mod m，K 为元素的关键字，m 为散列表的长度，用余数作为 存储该元素的散列地址。这里假定 K 和 m 均为正整数，并且 m 要大于等于线性表的长度 n。此例 n=7，故假定取 m=13，则得到的每个元素的散列地址为： h(18)=18 mod 13=5 h(43)=43 mod 13=4 h(46)=46 mod 13=7 根据散列地址按顺序把元素存储到散列表 H（0：m-1）中，存储映象为：

　　图 1 形象地表示了哈希表处理的各个要素，具体概念如下： 1、两个集合：U 是所有可能出现的关键字集合；K 是实际存储的关键字集合。 2、函数 h 将 U 映射到表 T[0..m-1]的下标上，可以表示成 h：U→{0，1，2，...，m-1}，通常称 h 为“哈希函数(Hash Function)” ，其作用是压缩待处理的下标范围，使待处理的U个值减少到 m 个值，从而降低空间开销（注：U表示 U 中关键字的个数，下同） 。 3、将结点按其关键字的散列地址存储到哈希表（散列表）中的过程称为“散列(Hashing)” 。方法 称为“散列法” 。 4、h(Ki)(Ki∈U)是关键字为 Ki 的结点的“存储地址” ，亦称散列值、散列地址、哈希地址。 5、用散列法存储的线性表称为“哈希表（Hash Table），又称散列表。图中 T 即为哈希表。在散 ” 列表里可以对结点进行快速检索（查找） 。 6、对于关键字为 key 的结点，按照哈希函数 h 计算出地址 h(key)，若发现此地址已被别的结点占 用，也就是说有两个不同的关键码值 key1 和 key2 对应到同一个地址，即 h(key1)=h(key2)，这个 现象叫做“冲突（碰撞）。碰撞的两个（或多个）关键码称为“同义词” ” （相对于函数 h 而言） 。 如图 1 中的关键字 k2 和 k5，h(k2)=h(k5)，即发生了“冲突” ，所以 k2 和 k5 称为“同义词” 。假 如先存了 k2，则对于 k5，我们可以存储在 h(k2)1 中，当然 h(k2)1 要为空，否则可以逐个往后 找一个空位存放。这是另外一种简单的解决冲突的方法。 发生了碰撞就要想办法解决，必须想办法找到另外一个新地址，这当然要降低处理效率，因 此我们希望尽量减少碰撞的发生。这就需要分析关键码集合的特性，找适当的哈希函数 h 使得计 算出的地址尽可能“均匀分布”在地址空间中。同时，为了提高关键码到地址转换的速度，也希 望哈希函数“尽量简单” 。然而对于各种取值的关键码而言，一个好的哈希函数通常只能减少碰撞 发生的次数，无法保证绝对不产生碰撞。因此散列除去要选择适当的哈希函数以外，还要研究发 生碰撞时如何解决，即用什么方法存储同义词。

　　一、引入 义一个一维数组 A[1..n]，此处 n=7，将表中元素按先后顺序存储在 A[i]中，但这样给查找带来了 开销，尤其是 n 很大时，我们需要用 O(n)的时间去查找某个元素（当然也可采用二分查找提高效 率） ；反之，为了用 O(1)的时间实现查找，可以分析这个线性表的元素类型和范围，开一个一维数 组 A[1..1353], 使得 A[key]=key，即线性表的 key 这个元素存储在 A[key]中，这样一来，查找的 效率便为 O（1）了，但显然造成了空间上的很大浪费，尤其是数据范围分布很广时。为了使空间 开销减少，我们可以对第二种方法加以优化，设计一个函数 h(key)=key mod 13，然后把 key 存在 A[h(hey)]中， 这样一来定义一个一维数组 A[0..12]就已足够， 这种方法就是我们要学习的哈希表 （散列表） 。 哈希表是一种高效的数据结构。它的最大优点就是把数据存储和查找所消耗的时间大大降低， 几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多、 程序运行时间控制的越来越短的情况下，用空间换时间的做法还是值得的。另外，哈希表编码实 现起来比较容易也是它的优点之一。 二、基本原理 哈希表的基本原理是：使用一个下标范围比较大的数组 A 来存储元素，设计一个函数 h，对于 要存储的线性表的每个元素 node，取一个关键字 key，算出一个函数值 h(key)，把 h(key)作为数 组下标，用 A[h(key)]这个数组单元来存储 node。也可以简单的理解为，按照关键字为每一个元 素“分类” ，然后将这个元素存储在相应“类”所对应的地方（这一过程称为“直接定址”。 ） 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的 元素，却计算出了相同的函数值，这样就产生了“冲突” ，换句话说，就是把不同的元素分在了相 同的“类”之中。例如，假设一个结点的关键码值为 key，把它存入哈希表的过程是：根据确定的 函数 h 计算出 h(key)的值，如果以该值为地址的存储空间还没有被占用，那么就把结点存入该单 元；如果此值所指单元里已存了别的结点（即发生了冲突） ，那么就再用另一个函数 I 进行映象算 出 I(h(key)),再看用这个值作为地址的单元是否已被占用了，若已被占用，则再用 I 映象，„„， 直到找到一个空位置将结点存入为止。当然这只是解决“冲突”的一种简单方法，如何避免、减 少和处理“冲突”是使用哈希表的一个难题。 在哈希表中查找的过程与建立哈希表的过程相似，首先计算 h(key)的值，以该值为地址到基 本区域中去查找。如果该地址对应的空间未被占用，则说明查找失败，否则用该结点的关键码值 与要找的 key 比较，如果相等则检索成功，否则要继续用函数 I 计算 I(h(key))的值，„„。如此 反复到某步或者求出的某地址空间未被占用（查找失败）或者比较相等（查找成功）为止。

　　关键码是 9 位的，地址是 3 位的，需要经过数字分析丢掉 6 位。丢掉哪 6 位呢？显然前 3 位 是没有任何区分度，第 5 位 1 太多、第 6 位基本都是 8 和 9、第 7 位都是 3、4、5，这几位的区分 度都不好，而相对来说，第 4、8、9 位分布比较均匀，所以留下这 3 位作为地址（表中右边一列） 。 4、平方取中法 将关键码的值平方，然后取中间的几位作为散列地址。具体取多少位视实际要求而定，取哪 几位常常结合数字分析法。 【例 3】将一组关键字(0100，0110，1010，1001，0111)平方后得(0010000，0012100，1020100， 1002001，0012321)，若取表长为 1000，则可取中间的三位数作为散列地址集： (100，121，201，020，123)。 5、折叠法 如果关键码的位数比地址码的位数多，而且各位分布较均匀，不适于用数字分析法丢掉某些 数位，那么可以考虑用折叠法。折叠法是将关键码从某些地方断开，分关键码为几个部分，其中 有一部分的长度等于地址码的长度，然后将其余部分加到它的上面，如果最高位有进位，则把进 位丢掉。 一般是先将关键字分割成位数相同的几段（最后一段的位数可少一些） ，段的位数取决于散列 地址的位数，由实际需要而定，然后将它们的对应位叠加和（舍去最高位进位）作为散列地址。 【例 4】如关键码 Key=58422241，要求转换为 3 位的地址码。 分析：分如下 3 段：5 8 4 2 2 2 4 1，则相加： 5 8 4 2 2 2 4 1 8 4 7 h(Key)=847

　　四、哈希函数的构造方法 选择适当的哈希函数是实现散列的重中之重，构造哈希函数有两个标准：简单和均匀。简单 是指哈希函数的计算要简单快速；均匀是指对于关键字集合中的任一关键字，哈希函数能以等概 率将其映射到表空间的任何一个位置上。也就是说，哈希函数能将子集 K 随机均匀地分布在表的 地址集{0，1，...，m-1}上，以使冲突最小化。 为简单起见，假定关键码是定义在自然数集合上，常见的哈希函数构造方法有： 1、直接定址法 以关键字 Key 本身或关键字加上某个数值常量 C 作为散列地址的方法。散列函数为：h(Key)= KeyC，若 C 为 0，则散列地址就是关键字本身。 2、除余法 选择一个适当的正整数 m，用 m 去除关键码，取其余数作为地址，即：h(Key)= Key mod m， 这个方法应用的最多，其关键是 m 的选取,一般选 m 为小于某个区域长度 n 的最大素数（如例 1 中 取 m=13） ，为什么呢？就是为了尽力避免冲突。假设取 m=1000 ，则哈希函数分类的标准实际上就 变成了按照关键字末三位数分类，这样最多 1000 类，冲突会很多。一般地说，如果 m 的约数越 多，那么冲突的几率就越大。 简单的证明：假设 m 是一个有较多约数的数，同时在数据中存在 q 满足 gcd(m,q)=d 1 ，即 有 m=a*d,q=b*d,则有以下等式：q mod m= q – m* [q div m] =q – m*[b div a] 。 其中，[b div a]的取值范围是不会超过[0，b]的正整数。也就是说，[b div a]的值只有 b1 种可 能，而 m 是一个预先确定的数。因此上式的值就只有 b1 种可能了。这样，虽然 mod 运算之后 的余数仍然在[0，m-1]内，但是它的取值仅限于等式可能取到的那些值。也就是说余数的分布变得 不均匀了。容易看出，m 的约数越多，发生这种余数分布不均匀的情况就越频繁，冲突的几率越 高。而素数的约数是最少的，因此我们选用大素数。记住“素数是我们的得力助手” 。 3、数字分析法 常有这样的情况：关键码的位数比存储区域的地址的位数多，在这种情况下可以对关键码的 各位进行分析，丢掉分布不均匀的位留下分布均匀的位作为地址。 本方法适用于所有关键字已知，并对关键字中每一位的取值分布情况作出了分析。 【例 2】对下列关键码集合（表中左边一列）进行关键码到地址的转换，要求用三位地址。