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

　　* 哈希表 由哈希函数的值组成的表。哈希查找是建立在哈希表的基础上，它是线性表的一种重要存储方式和检索方法。在哈希表中可以实现对数据元素的快速检索。 哈希函数 哈希表中的元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数）计算出的值，即为该元素的存储地址。表示为： Addr = H（key） 这个函数就是哈希函数 一、关于哈希函数 由于哈希函数是一个压缩映像，因此，在一般情况下，很容易产生“冲突”现象 在哈希元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1 ? K2， 但哈希函数值 H（K1）= H（K2）。 均匀的哈希函数可以减少冲突，但不能避免冲突。发生冲突后，必须解决；也即必须寻找下一个可用地址。 处理冲突是建立哈希表过程中不可缺少的一部分。 处理冲突主要有两种方法： 开放地址法（线性探测法、二次探测法） 链地址法 二、冲突及冲突处理 线性探测法：当发生地址冲突后，求解下一个地址用Hi =( H（key）+di） MOD m ， i=1,2,…,k(k ? m-1)其中: H(key)为哈希函数,m为哈希表长度,di为增量序列。增量序列的不同取法， 又构成不同的开放地址法。 1. 处理冲突 —— 开放地址法 二次探测法：如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k=m/2)称二次探测再散列，用公式表达如下： 例：在长度为11的哈希表中已填有关键字分别17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下： ? ? ? 29 17 60 ? ? ? ? ? 10 9 8 7 6 5 4 3 2 1 0 (a)插入前 ? ? 38 29 17 60 ? ? ? ? ? 10 9 8 7 6 5 4 3 2 1 0 (b)线性探测再散列 ? ? ? 29 17 60 ?38 ? ? ? ? 10 9 8 7 6 5 4 3 2 1 0 (c)二次探测再散列 ? ? ? 29 17 60 ? 38 ? ? ? 10 9 8 7 6 5 4 3 2 1 0 (d)伪随机探测再散列，伪随机数列为9,5,3,8,1... 2. 处理冲突 —— 链地址法 当发生地址冲突后,将所有函数值相同的记录连成一个单链表。 0 1 2 3 4 5 6 7 8 9 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ K1 K2 K3 ∧ K4 K5 K6 ∧ 同义链，同一散列地址。 同义链，同一散列地址。 (noip2009)16.设有一个含有13个元素的Hash表(0~12),Hash函数是:H(key)=key % 13,其中% 是求余数运算。用线性探查法解决冲突,则对于序列(2、8、31、20、19、18、53、27),18应放在第几号格中( ). A) 5 B) 9 C) 4 D) 0 解题思路：首先，明确一下几格概念：什么是hash表、什么是hash函数、什么是线性探查法、冲突在哪里；其次逐一求余；最后找出冲突，利用线性探查法解决问题。 *