HASH GAME - Online Skill Game GET 300

　　目录什么是哈希表如何构造哈希函数处理冲突的方式 HashMap 2017-4-9 2 哈希表哈希表哈希表又称哈希表又称散列表散列表。。哈希表存储的基本思想是哈希表存储的基本思想是:以数据表中的每个记录的关:以数据表中的每个记录的关键字键字 k k 为自变量,通过一种函数为自变量,通过一种函数 H(k) H(k) 计算出函数值。把这个值计算出函数值。把这个值解释为一块连续存储空间(即数组空间)的单元地址(即下解释为一块连续存储空间(即数组空间)的单元地址(即下标),将该记录存储到这个单元中。在此称该函数标),将该记录存储到这个单元中。在此称该函数 H H为为哈希函哈希函数数或或散列函数散列函数。按这种方法建立的表称为。按这种方法建立的表称为哈希表哈希表或或散列表散列表。。 2017-4-9 3 例如,要将关键字值序列( 3,15,22,24 ),存储到编号为 0到4 的表长为 5的哈希表中。计算存储地址的哈希函数可取除 5 的取余数算法 H(k)=k % 5 。则构造好的哈希表如图所示。哈希表哈希表 2017-4-9 4 理想情况下,哈希函数在关键字和地址之间建立了一个一一对应关系, 从而使得查找只需一次计算即可完成。由于关键字值的某种随机性,使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即 k1≠k2,但H(k1)=H(k2 ),这种现象称为冲突。把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。在大多数情况下,冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大,而对应的地址数则可能比较少。对于哈希技术,主要研究两个问题: (1)如何设计哈希函数以使冲突尽可能少地发生。(2)发生冲突后如何解决。哈希表哈希表 2017-4-9 5 构造好的哈希函数的方法,应能使冲突尽可能地少,因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同,可构造出许多不同的哈希函数。 k 本身或关键字加上某个数值常量 c 作为哈希地址的方法。该哈希函数 H(k) 为: H(k)=k+c (c ≥0) 这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时,可使用直接定址法的哈希函数。否则, 若关键字分布不连续将造成内存单元的大量浪费。哈希函数的构造方法 2017-4-9 6 例:统计某地区从 1949 年到 1995 年每年出生的人数,列在一张表中。年份为关键字,因共有 47年,所以表中位置范围是 1~47。设置 H(k)=k-1948 即可,其中 k为年份数。这样的哈希表示意如下: 12... 47 年份人数 1949 19501995 ... ... ... ... 若要查 1970 年的出生人数,则根据( 1970-1948=22 ) 计算,在表的第 22个位置即可找到。哈希函数的构造方法 2017-4-9 7 k 除以哈希表长度 m 所得余数作为哈希函数地址的方法。即: H(k)=k %m 这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度 m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明,在 m 取值为素数(质数)时,冲突可能性相对较少。哈希函数的构造方法 2017-4-9 8 (若超出范围时,可再取模)。设有一组关键字 ABC ,BCD,CDE ,DEF , ……其对应的机内码如表所示。假定地址空间的大小为 1000 ,编号为 0-999 。现按平方取中法构造哈希函数,则可取关键字机内码平方后的中间三位作为存储位置。计算过程如下表所示: 关键字机内码机内码的平方数哈希地址 ABC BCD CDE DEF ... 010203 020304 030405 040506 ... 0104 101 209 0412 252 416 0924 464 025 1640 739 036 ... 101 252 464 739 ... 哈希函数的构造方法 2017-4-9 9 ,而地址区间较小的情况。将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址(若超出范围,可再取模)。例如, 假设关键字为某人身份证号码 ,则可以用 4 位为一组进行叠加。即有 5355+8101+1046+430=14932 ,舍去高位。则有 H()=4932 为该身份证关键字的哈希函数地址。哈希函数的构造方法 2017-4-9 10