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

　　￡￡(Hash)函数:在记录的存储位置和它的关键字之间建立的一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。称这个对应关系f为哈希函数。均匀的(Uniform)哈希函数:对于关键字集合中的任一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等的,则称此类哈希函数为均匀的哈希函数。哈希表:根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为哈希表,这一映像过程称为哈希造表或散列,所得存储位置称哈希地址或散列地址。冲突(collision):不同的关键字可能得到同一哈希地址的现象。同义词(synonym):在一个哈希函数中,具有相同函数值的关键字,互称为同义词。例如,假设建立一张全国30个地区的各民族人口统计表,每个地区为一个记录,记录的各数据项为:编号地区名总人口汉族回族显然,可以用一个一维数组C(1:30)来存放这张表,其中C[i]是编号为i的地区的人口情况。编号i便为记录的关键字,由它唯一确定记录的存储位置C[i]。假设北京市的编号为1,则若要查看北京市的各民族人口,只要取出C[1]的记录即可。若把这个数组看成是哈希表,则哈希函数f(key)=key。又,若取关键字中第一个字母在字母表中的序号作为哈希函数。如,BEIJING的哈希函数值为字母“B”在字母表中的序号等于02。关键字HEBEI和HENAN不等,但f(HEBEI)=f(HENAN),这种现象即为冲突。HEBEI和HENAN相对于该哈希函数称为同义词。￡,通常有: (包括硬件指令的因素); ; ; ; 。(1)。即: H(key)=key或H(key)=a*key+b其中a和b为常数(这种哈希函数叫做自身函数)。直接定址所得地址集合和关键字集合的大小相同。对于不同的关键字不会发生冲突。,有一个从1岁到100岁的人口数字统计表。地址01 0203 …252627… 100年龄1 23 …252627… …人数300 20005000…1050……… … 直接定址哈希函数例子一其中,年龄作为关键字,哈希函数取关键字自身。若要询问25岁的人有多少,则只要查表的第25项即可。例二:有一个解放后出生的人口调查表。地址010203…22…年份1…1970…人数…………15000…其中,关键字是年份,哈希函数取关键字加一常数:H(key)=key+(-1948)。若要查1970年出生的人,则只要查第(1970-1948)=22项即可。 直接定址哈希函数例子二(2)数字分析法主要思想:假设关键字是以r为基的数(如:以10为基的十进制数),并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干位组成哈希地址。例如,有80个记录,其关键字为8位十进制数。假设哈希表的表长为10010,则可取两位十进制数组成哈希地址。这两位的取法,原则是使得到的哈希地址尽量避免产生冲突。假设这80个关键字中的一部分如下所列:5对关键字全体的分析:第①②位都是“81”,第③位只可能取1、2、3或4,第⑧位只可能取2、5或7,因此这4位都不可取。由于中间4位可看成是近乎随机的,因此可取其中任意两位,或取其中两位与另两位的叠加求和后舍去进位作为哈希地址。(3)。取的位数由表长决定。,为BASIC源程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母,或一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字,(a)所示。取表示符在计算机中的八进制数为它的关键字。假设表长为512=29,则可取关键字平方后的中间9位二进制数为哈希地址。例如,(b)列出了一些标识符及它们的哈希地址。ABC…Z012…9010203…32606162…71(a) 字符的八进制表示对照表A 0100 0010000 010I 1100 1210000 210J 1200 1440000 440I0 1160 1370400 370P1 2061 4310541 310P2 2062 4314704 314Q1 2161 4734741 734Q2 2162 4741