字符串Hash散列表设计.docVIP

字符串Hash散列表设计 字符串Hash散列表设计 By WangFL 一、常见字符串hash函数 1、ASCII码相加 基本思想：将字符串的每一个字符的ASCII码相加，得出的值即为hash函数值。 代码举例： num:=0; for I:=1 to length(s) do inc(num,ord(s[I])); 冲突：例如’abc’与’bca’等元素相同而排列不同的字符串，显然会造成冲突。 改进：可以将字符的ASCII码乘上一个位权，然后再相加，这样可以避免一部分冲突。还可采取另外类似的附加权值方法。 代码举例： num:=0; for I:=1 to length(s) do inc(num,ord(s[I])*I); 2、ElfHash函数 基本思想：利用位运算，产生一个hash函数值。 代码举例： num:=0; for I:=1 to length(s) do begin num:=(num shl 4)+ord(s[I]); g:=num and ($f0000000); if g0 then num:=num xor (g shr 24); num:=num and (not g); end; 优点：压缩极为密集，是一个很好用的产生冲突极少的函数。 压缩方法 经过处理之后生成的hash函数可能比较零散，或者跨越区间比较大。此时可以采取生成整型数hash函数的经典方法。比如可以将生成的hash函数mod一个数而产生新的hash函数值。但这样会使产生冲突的概率增加。 冲突的解决 （1）二维数组静态拉链（自己第一次用，发明的垃圾算法） 基本思想： 生成hash：计算hash值后，将未被改变的hash赋为true，并将字符串存入list[对应hash值]中。 查找：读入关键字，如果对应的hash值为true，则在list[对应hash值]中进行查找。 代码举例： list:array[1..maxn,1..maxl] of string; hash:array[1..maxn] of boolean; （maxn为hash表长度，maxl为估计最大冲突个数） 缺点：浪费大量空间且紧缩时无法准确把握限度，效果不大。 2、动态链表拉链 基本思想： 对于每一个hash地址，产生一个链表存储冲突的字符串。 优点：可动态安排存储冲突的空间，防止空间浪费。 缺点：属于动态数据结构的操作，对于不熟悉的操作者容易造成失误。 3、静态一维数组模拟链表 基本思想：类似于动态链表拉链法。 代码举例： list:array[1..maxn] of string; next:array[1..maxn] of integer; hash:array[1..maxn] of integer; （maxn为hash表长度） 其中，list记录所有的字符串。Hash中存储的为每个hash函数值所对应的第一个字符串的存储地址。Next(i)表示字符串list(I)的后继字符串为next(I)。经过next连接的所有字符串均为冲突字符串。 二、程序举例 [文明的复兴（From TJU）] Problem 战神PrinceGush回归了，但许多原先的上层精灵越来越不安分。他们无法忍受失去权力的空虚感，开始重新寻找新的途径获取权利。他们直率急躁的领导人King_Bette开始公开抨击权威，并散布谣言。 权利的统治需要统一，需要强硬，被逼无奈下正义的领袖开始收缴反动的资料，清除世界的毒瘤，借以踏上快速发展之路。 不良信息指的是一组单词，每个单词均为不良信息。 不良信息文本是指包含一系列的单词，且其中包含有不良信息。发布信息者经常在单词中加些字母以外的字符以搅乱正义的视线，于是Prince想请你为他写一个能够将这些不良信息屏蔽掉的工具。但是为了尽量降低误删率,他提出了下面一个要求 你只需要将字母完全匹配的单词屏蔽掉即可。 例如: sex为不良信息时, sex8,sex$,se#x均为不良信息 sexx 则不属于不良信息. Input 第一行为一整数n，表示有n组测试数据。 每组测试数据第一行为一个正数k = 10000，表示有k个需要被屏蔽的词语，均为小写字母。 以下k行每行一个单词。 最后一行为输入需要处理的文本（文本长度=100000）,单词与单词之间空格分开且所有字母为小写字母。 Output 每组测试数据输出一行和输入格式一致的文本，被屏蔽的单词的字母以*代替原字母。 Sample Inpu