最小完美哈希函数(深入搜索引擎)
最小完美哈希函数
哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数
据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。
a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈
希函数。
25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做
过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。
如果在一般的哈希函数中再增加一条额外的性质，即对于任意的x i和x j，当且仅当i=j时才有h(x i)=h(x j)，这就是完美哈希函数(perfect hash function)。这里，当对一个键值集合L进行哈希时，不可能出现任何冲突。
如果哈希函数不仅是完美的，并映射到的值域范围为m=n，n个键值中的任意一个都一一映射到唯一整数（该整数是介于1~n的某个整数），这时表的装载因子是a = 1.0，因此该函数称为“最小完美哈希函数”(minimal perfect hash function)，或者简记为“MPHF”。一个MPHF保证了任何一个键值只需进行一次探测(one-probe)访问，并且表中不包含无用槽。
最后，如果哈希函数还具有这样的性质，即若x i 当煞，一个MPHF或者OPMPHF对某一个键值集合L有效，但可能对另一个集合就不“完美”了，因此这里不过是对一个单一静态集合预先计算( precalculated)了查找函数。然而在空间节省很大，并且预先计算被授权的场合下才能这么做。 作为例子，表4-3给出了我们曾经使用过的12个键值的一个OPMPHF。这个哈希函数的推导过程在下节中将展开讨论。构造的过程预先假定存在两个一般的哈希函数h1(t)和h2(t)，它们都是将字符串映射到范围O~m-1的一个整数。其中m≥n，并且允许重复。一种定义方法是用数值来表示基数为36的字符串，与前面提到的一样，最后计算权重之后得到wj， 这里t[i]是用基数为36的值描述的术语中第f个字符，|t|表示术语t的长度。那么不同的权重集合W1[i]和W2[i]中的i为1≤i≤|t|，这样就导出了两个不同的函数h1(t)和h2(t)。与这两个函数一起，还需要一个特别的数组g。它需要继续把O...m-1映射到O...n-1，如表4-3 (b)所示。 给某个字符串t，采用OPMPHF h(t)的方法计算公式为： h(t)=g(h1(t))+ n g(h2(t)) 这里+n表示加法执行后还需对n取模，即先把两个数相加。然后把这个数除以n，最后取余数(例如4 +n7=2)。换句话说，首先计算两个非完美哈希函数的值，用映射g分别计算这两个哈希函数的值。然后将其相加后对n取模，例子字典中的计算结果可以在表4-3 (a)的第4列中找到。如同变戏法一样，最后的哈希值确实就是字符串列表中的原位置26。 表4-3最小完美哈希函数表 (b)哈希函数g 的索引术语集进行计算的话，那么就不必存放字符串或者字符串指 针。只需要存储f t值，而术语t的倒排文件地址直接从数组中的第h(t) 位置就能找到。 26译者注：可以看出在表4-3 (a)中最后计算的h(t)值从0—11顺序摊列，可知h即保序，又单射且满射，这些性质符合OPMPHF的定义要求。 27译者注：这里其实表达的是通过字符串本身能够建立与其编号对应的关系，假定我们已知单词“bed”的三个字母的编码分别为ABC，其在字典中按序排放的顺序为R，那么函数h(t)的就是从ABC计算出R的公式。 这里有一个难题，描述哈希函数h需要多少存储空间？一个 MPHF至少需要1.44n比特的存储空间(Fox及Heath等1992)，更典 型的很容易计算出对于大数的n，MPHF大约需要每个键值4个—20 比特。而描述OPMPHF所需要的空间还要更大，大约需要至少nlogn 比特的存储空间（Fox等1991）。在OPMPHF中，两个哈希函数h1 和h2可以有较小的权重表W1和W2描述，因此它们需要的空间可 以忽略不计；另一方面，数组g有m个项，即便是紧凑存放，也需 要占用mlogn比特。下一节将要介绍的方法采用了m= 1.25n的比例 关系。这也是为什么在表4-3的例子中，n(n= 12)个字符串m=15的数 组g来处理。即数组g占用了25比特每字符串，或者，在实际的带 有索引项的术语存储为4字节的整数28。对于假定n=1 000 000个单 词的字典，大约需要1.25×4×1 000 000=5 MB的存储开销，另外8 MB依然需要存放磁盘指针( disk pointer)和术语词频。从整体上看， 如果OPMPHF被实际使用的话，与3-in-4的前端编码所需的15.5 MB 相比，字典能够降佤到大约13 MB。 完美哈希函数的设计 在介绍找到最小哈希函数的算法前，首先让我们计算一下生日悖论的概率。假定n个项将被哈希到m个槽内，第1项可以没有任何碰撞风险的情况下放在某个槽内；第2项的放置能够成功避免冲突的概率为(m-l)/m，因为此时已经有一个槽不可用了；第3项的放置概率是(m-2)/m。依此类推，连续插入n个项而不发生一次冲突的概率就是这些概率的乘积： (4.1) 当m= 365且n=22时，概率为0.524;当n=23时，概率下降到0.493。因此一个屋子里如果有23个人，那么很有可能有两个人的生日是同一天。 现在我们来看数组g的构造过程，它是表4-3例子中MPHF的奥秘所在。让我们首先回忆一下如下3组公式： 28译者注：数组g为每个术语分配25比特，每个术语存放ft需要8比特。大约需要32比特，即4字节。 这里t[i]是字符串中第i个要被哈希的字符，构造一个OPMPHF 第1步就是要随机地选择函数h1和h2的映射方法。有很多办法可以实施，最简便的方法是按照其定义构造随机整数数组W1和W2，一旦构造好，找到这样一个函数g就可以开始了。 将这个问题可视化为一个m点图(m-vertex graph)，每个顶点标记上0~m-1的数。每条边代表一个术语序号，定义为(h1(t)),(h2(t))。字典中的每个术语对应于图上的一条边，两个哈希值定义了该边连接的哪两个顶点。最后为每条边用h(t)值标记，这里h(t)就是术语t的哈希函数值。图4-4中的图对应表4-3 (a)中的哈希函数h1和h2。这里有m=15个顶点，有n=12条边。一般的图算法(Graph algorithm)把顶点数定义成n，边数定义为m。但是在这个讨论中，一致性需要逆着这个传统来讨论29。 图4-4对应表4-3哈希函数的图模型 29译者注：这里只是代数方法的不同，定义m为顶点，n为边。 现在我们需要的是计算映射g，使之能够将每个顶点映射到0~n-1的整数。即对于每条边(h1(t)),(h2(t))，该映射为： g((h1(t))+ng(h2(t))，这个值作为边的标记30。 对于一个一般的图，找到某个标记。如果存在的话，是很难的。但是如果图已知是无环的，即不存在一个封闭的由边构成的环(cycle of edges)。例如，图4-4就是一个无环图，但是如果这里加上一条从2~8的边，那么就形成了2-4-8-2的环，也就不再符合无环的要求了。 对于一个无环图，理想的函数g是很容易推导出的。任意选择一个未处理的顶点，令g(v)=0。顺着从该点出发的边，这些边指向的顶点用该边的h值标记下一代的顶点，这时这个值等于边值减去项点值之差（这个顶点也是边的一端）。如果不存在未标记的顶点，那么就选择下一个根。周而复始，直到所有的顶点都被做好标记，这时映射函数g宣告完成。 举个例子，假定我们选择图4.4中的顶点0作为一个连通分量(connectedcomponent)的根。令g[0]=0 31，那么g[3]就必须赋值为732。这样一来，按照顺序g[6]就必须赋值为l，同时g[1]被赋值为4。由于g[6]赋值为1，g[10]就必须赋值为2，同理g[12]赋值为0，这样就做完了以顶点0为根的连通分量的赋值工作。下一个未标记的顶点在本例中为2，将被选做一个新的连通分量的根，即g[2l=0、g[4]=6且g[8l=3。最后顶点5被当做根，整个余下的顶点都在这次连通分量的赋值过程中分配完毕。 如果图不是无环的，这个标记的过程可能会在一个循环中打圈圈，持续不断地为那些已经处理过的顶点标记不同的标签（这与之前的标签不同）。这在一个无环图中是不可能的，打标记总是不会出错。鉴于此，将测试是否有环的工作就必须增加到标记处理过程中。图4-5描述了处理任意无向图G(V，E)的过程，它假定adjacent(v)为点的邻接点列表。这些领接点都和该顶点v共享一条边，这样h(v，u)就是连接v和u的边的标记。 30译者注：这里以表4-3 (a)中序号为7的术语“jezrahiah”为例，其h1和h2函数分别计算值为0及3，因此这个术语的两个顶点为0，3（如图4-4所示），它们的边为7。映射g就是要把(0，3)映射到7的计算。 31译者注：这里的意思是为图中顶点0做个标记值，也为0。读者可以在图中也写上这个值，便于理解。 32译者注：该边的边值已经事先确定为7，那么要保证g[3]+n g[0]=7，就必须设置g[3]为7。 To label an acyclic graph, 1. For υ∈V, Set g[υ]←unknown. 2.Forυ∈V, If g[υ]=unknown then LabelFrom(υ,0). Where the function LabelFrom(υ,c) is defined by 1. If g[υ]≠unknown then Return with failure—the graph is not acyclic, Else Return—this vertex has already been visited. 2. Set g[υ] ←c. 3. Forυ∈adjancent(υ), LabelFrom(u,h((υ,u)))—g[υ]). 图4-5检查无环图，并且分配映射函数 这个机制需要一个线性步长序号来确定完全分配了映射函数g 或者发现图中存在环，函数LabelFrom将会被至多调用2m次。图4-6描述了这样一个迭代过程，这个过程生成并且测试哈希函数。该算法的本质是很朴素的，生成新函数hi和h2直到得到一个无环图。 To generate a perfect hash function, 1.Choose a value for m. 2.Randomly choose weights w1[i] and w2[i] for 1≤i≤max t∈L|t|, where L is the set of strings to be hashed and |t| is the length of string t. 3. Generate the graph G=(V , E) , where V = {1,…m} and E = { ( h1( t ) , h2( t ) ) | t∈L } 4. Use the algorithm of Figure 4.5 to attempt to calculate the mapping g. 5. If the labeling algorithm returns with failure, go back to step 2. 6. Return the arrays w1 , w2 , and g. 图4-6生成一个完美哈希函数 还有一个遗留的问题，它是该项技术能否实用的关键，即第2步和第3步生成的图G多大可能是无环的？回答这个问题首先取决于第1步m值的选择。很明显，m值选的越大，那么图G越稀疏，其成为无环图的可能性就越大。 基于随机图理论分析可知对于m≤2n，随着n的增长生成一个无环图的概率趋近于0，边太稠密不可避免地在图中的某处形成一个环(Czech，Havas和Majewski 1922)。另一方面，当m>2n时，一个m 个顶点，，z条边的随机图是一个无环图的概率近似于： 因此在发现第一个无环图之前，期望生成的图的数量为： 例如，如果m=3n，那么平均情况下√3≈1.7个图需要被检查才能确定一个合适的能作为哈希函数生成的无环图。总的看来，假定m>2n，则生成哈希函数的代价和集合L的项数成正比。 使用m=3n的缺点是数组g耗费的空间开销，如果该数组需要为每个术语分配3个4字节的整数，这个代价一点也不比存储字符串本身更低；另一方面，将m/n的比值降低到2以下，将意味着在找到一个无环图之前必须创建大量的有环图。这只有在键值集合较小的情况下才能容忍，并且花费在创建映射函数的时间开销可以忽略。 当然，还有其他方法可以降低mln的比值，表4-3和图4-4的例子假定了使用二维图( 2-graph)。每条边连接两个顶点。假定再引入第 3个随机哈希函数h3，在m个顶点上建立一个三维图( 3-graph)，每条边是这样一个三元组：(h1(t), h2(t), h3(t)) 哈希函数的形式为： h(t)=g(h1(t))+n g(h21(t))+n g(h3(t)) 找到一个映射函数g变得更加复杂，但逻辑还是不变的33：一幅图可用。当删除某个序号的边时，每个刑除边至少有一个度1的顶点，按序能够移除所有边。另一种方式来表示这种需求是没有一幅子图是仅包含度2或以上的顶点。 实验和分析表明，在三维图中，m和n的临界比例大约是1.23(havas等1993;Majewski等1996)。换句话说，如果m>1.23n，那么创建一幅理想性质的图在平均情况下只需要常数次的尝试。其他步骤花费的时间也都和图的比例成正比，在实际环境中都能极快地处理。例如，一般情况下为超过500 000术语的TREC字典创建一个完美哈希函数所耗费的时间不超过1分钟。 最后，我们必须承认有一些小小的不一致性，为了避免混淆，在表4-3和图4-4中使用的例子n= 12且m= 15，它们的比例是1.25。但只是用了两个哈希函数，而不是3个，它之所以能够工作得很完美是因为这个例子是精心挑选的。 33译者注：通过和作者的交流，这里逻辑不变指的是处理无环的方法是相似的。在考虑到3个哈希函数(h1，h2，h3)时此前的判断是否有环的规则不能直接使用，因此给出了更加复杂的判断一幅图是否无环的规则。 (1 )找到一条边，其中该边的3个顶点至少有一个是度l的顶点。 (2 )删除这条边。 (3 )重复执行(1)和(2)。 如果最后还留下边，则该图是有环的。 计算机算法领域 基本知识 Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系 基本概念 * 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数） 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。 处理冲突的方法 1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1. di=1,2,3,…, m-1，称线性探测再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列; 什么是哈希函数 哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。 1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质： 2、给定输入数据，很容易计算出它的哈希值； 3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻击性； 4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，（这种情况称为碰撞，Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性； 5、哈希值不表达任何关于输入数据的信息。 哈希函数在实际中有多种应用，在信息安全领域中更受到重视。从哈希函数的特性，我们不难想象，我们可以在某些场合下，让哈希值来“代表”信息本身。例如，检验哈希值是否发生改变，借以判断信息本身是否发生了改变。` 怎样构建数字签名 好了，有了Hash函数，我们可以来构建真正实用的数字签名了。 发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一个摘要H’，再把H和H’相比较，看看两者是否相同。根据哈希函数的特性，我们可以让简短的摘要来“代表”信息本身，如果两个摘要H和H’完全符合，证明信息是完整的；如果不符合，就说明信息被人篡改了。 数字签名也可以用在非通信，即离线的场合，同样具有以上功能和特性。 由于摘要一般只有128位或160位比特，比信息本身要短许多倍，USB Key或IC卡中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。 本文为“等考二级JAVA：Java规则引擎工作原理及应用”，以供广大学员参考使用。更多关于计算机 等级考试资料，请访问考试吧计算机等级考试频道。 摘要：Java规则引擎是一种嵌入在Java程序中的组件，它的任务是把当前提交给引擎的Java数据对象与加载在引擎中的业务规则进行测试和比对，激活那些符合当前数据状态下的业务规则，根据业务规则中声明的执行逻辑，触发应用程序中对应的操作。 引言 目前，Java社区推动并发展了一种引人注目的新技术——Java规则引擎(Rule Engine)。利用它就可以在应用系统中分离商业决策者的商业决策逻辑和应用开发者的技术决策，并把这些商业决策放在中心数据库或其他统一的地方，让它们能在运行时可以动态地管理和修改，从而为企业保持灵活性和竞争力提供有效的技术支持。 规则引擎的原理 1、基于规则的专家系统(RBES)简介 Java规则引擎起源于基于规则的专家系统，而基于规则的专家系统又是专家系统的其 中一个分支。专家系统属于人工智能的范畴，它模仿人类的推理方式，使用试探性的方法进行推理，并使用人类能理解的术语解释和证明它的推理结论。为了更深入地了解Java规则引擎，下面简要地介绍基于规则的专家系统。RBES包括三部分：Rule Base(knowledge base)、Working Memory(fact base)和Inference Engine。它们的结构如下系统所示： 如图1所示，推理引擎包括三部分：模式匹配器(Pattern Matcher)、议程(Agenda)和执行引擎(Execution Engine)。推理引擎通过决定哪些规则满足事实或目标，并授予规则优先级，满足事实或目标的规则被加入议程。模式匹配器决定选择执行哪个规则，何时执行规则;议程管理模式匹配器挑选出来的规则的执行次序;执行引擎负责执行规则和其他动作。 推理引擎的推理步骤如下： (1)将初始数据(fact)输入Working Memory。 数据结构课程设计哈希表设计问题 目录 1 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15) 1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言 3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图 最小完美哈希函数 哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数 据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。 a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈 希函数。 25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做 过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。 规则引擎研究——Rete算法介绍 一、R ETE概述 Rete算法是一种前向规则快速匹配算法，其匹配速度与规则数目无关。Rete是拉丁文，对应英文是net，也就是网络。Rete算法通过形成一个rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structuralsimilarity），提高系统模式匹配效率。 二、相关概念 2.1事实（FACT）： 事实：对象之间及对象属性之间的多元关系。为简单起见，事实用一个三元组来表示：（identifier^attributevalue），例如如下事实： w1:(B1^onB2)w6:(B2^colorblue) w2:(B1^onB3)w7:(B3^left-ofB4) w3:(B1^colorred)w8:(B3^ontable) w4:(B2^ontable)w9:(B3^colorred) w5:(B2^left-ofB3) 2.2规则（RULE）: 由条件和结论构成的推理语句，当存在事实满足条件时，相应结论被激活。一条规则的一般形式如下： (name-of-this-production LHS/*oneormoreconditions*/ --> RHS/*oneormoreactions*/ ) 其中LHS为条件部分，RHS为结论部分。 下面为一条规则的例子： (find-stack-of-two-blocks-to-the-left-of-a-red-block (^on) (^left-of) (^colorred) --> ...RHS... ) 2.3模式（PATTEN）： 模式：规则的IF部分，已知事实的泛化形式，未实例化的多元关系。 (^on) (^left-of) (^colorred) 三、模式匹配的一般算法 规则主要由两部分组成：条件和结论，条件部分也称为左端（记为LHS,left-handside），结论部分也称为右端（记为RHS,right-handside）。为分析方便，假设系统中有N条规则，每个规则的条件部分平均有P个模式，工作内存中有M个事实，事实可以理解为需要处理的数据对象。 规则匹配，就是对每一个规则r,判断当前的事实o是否使LHS(r)=True，如果是，就把规则r的实例r(o)加到冲突集当中。所谓规则r的实例就是用数据对象o的值代替规则r的相应参数，即绑定了数据对象o的规则r。 规则匹配的一般算法： 1)从N条规则中取出一条r； 2)从M个事实中取出P个事实的一个组合c； 3)用c测试LHS(r)，如果LHS(r（c）)=True，将RHS(r（c）)加入冲突集中； 4)取出下一个组合c，goto3； 5)取出下一条规则r，goto2； 四、RETE算法 Rete算法的编译结果是规则集对应的Rete网络,如下图。Rete网络是一个事实可以在其中流动的图。Rete网络的节点可以分为四类：根节点（root）、类型节点（typenode）、alpha节点、beta节点。其中，根结点是一个虚拟节点，是构建rete网络的入口。类型节点中存储事实的各种类型，各个事实从对应的类型节点进入rete网络。 4.1建立RETE网络 Rete网络的编译算法如下： 1)创建根； 2)加入规则1(Alpha节点从1开始，Beta节点从2开始)； a.取出模式1，检查模式中的参数类型，如果是新类型，则加入一个类型节点； 数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库？ 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？ 在实际开发中，我们应该如何用哈希算法解决问题？ 1. 什么是哈希算法？ 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法？ 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈 希值。 2. 哈希算法的常见应用有哪些？ 7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？ Java规则引擎工作原理及其应用 作者：缴明洋谭庆平出处：计算机与信息技术责任编辑：方舟[ 2006-04-06 08:18 ] Java规则引擎是一种嵌入在Java程序中的组件，它的任务是把当前提交给引擎的Java数据对象与加载在引擎中的业务规则进行测试和比对 摘要Java规则引擎是一种嵌入在Java程序中的组件，它的任务是把当前提交给引擎的Java数据对象与加载在引擎中的业务规则进行测试和比对，激活那些符合当前数据状态下的业务规则，根据业务规则中声明的执行逻辑，触发应用程 序中对应的操作。 引言 目前，Java社区推动并发展了一种引人注目的新技术——Java规则引擎（Rule Engine）。利用它就可以在应用系统中分离商业决策者的商业决策逻辑和应用开发者的技术决策，并把这些商业决策放在中心数据库或其他统一的地方，让它们能在运行时可以动态地管理和修改，从而为企业保持灵活性和竞争力 提供有效的技术支持。 规则引擎的原理 1、基于规则的专家系统（RBES）简介 Java规则引擎起源于基于规则的专家系统，而基于规则的专家系统又是专家系统的其中一个分支。专家系统属于人工智能的范畴，它模仿人类的推理方式，使用试探性的方法进行推理，并使用人类能理解的术语解释和证明它的推理结论。为了更深入地了解Java规则引擎，下面简要地介绍基于规则的专家系统。RBES包括三部分：Rule Base（knowledge base）、Working Memory（fact base）和Inference Engine。它们的结构如下系统所示： 图1 基于规则的专家系统构成 如图1所示，推理引擎包括三部分：模式匹配器（Pattern Matcher）、议程（Agenda）和执行引擎（Execution Engine）。推理引擎通过决定哪些规则满足事实或目标，并授予规则优先级，满足事实或目标的规则被加入议程。模式 计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。 前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。 不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资-源下，哈希算法还是被很难破解的。 对于加密知识点的补充，md5这个算法固然安全可靠，但网络上也有针对MD5中出现的彩虹表，最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。 第9卷第3期杨凌职业技术学院学报V ol.9 No.3 2010年9月Jour nal of Y ang ling V ocatio nal&T echnical Co lleg e Sep.2010 * Jess规则引擎在数据质量分析中的应用 史 峰 (江苏省宿迁市广播电视大学,江苏宿迁223809) 摘 要:规则引擎通过将业务规则和开发者的技术决策分离,实现了动态管理和修改业务规则而又不影响软件系统的需求。Jess是一个基于Java的规则引擎,可以方便地嵌入到Jav a应用程序中。本文论述了Jess规则引擎的核心组成及基于Jess规则的数据质量分析的工作原理,通过实例对基于SQ L查询、自定义规则和Jess规则进行了对比分析,得出了Jess规则引擎能够有效地对业务规则进行结构化表示和自动完成数据质量分析的结论。 关键词:Jess规则引擎;数据质量分析;事实库;规则库 中图分类号:T P311.13;T P311.5 文献标识码:A 文章编号:1671 9131(2010)03 0052 04 The Application of Jess Rule Engine in Data Q uality Analysis SHI Feng (Suqian Radio&T V U niv ersity,Suqian,Jiang su223809,China) Abstract:T he reg ular eng ine meets the demand o f dy namic manag ement and the r ev isio n o f business r ule,and does not af fect soft war e sy st em as w ell thr ough the separ ation of ser vice rule and ex ploiter's technical decisio n making.Jess is one r eg ular eng ine based on the Java,ma y be inserted co nv eniently into the Java application procedur e.T his art icle elabor ated the co re composition of Jess r egular eng ine and the w or king principle of data qualit y analysis based on the Jess r ule.With case study,w e made a compariso n of self def initio n rule based on SQ L inquiry and Jess rule,the co nclusion is obtained that Jess rule eng ine could car ry on st ruct ur al represent ation f or business rule effectively and t o co mplete the data qualit y analysis au to matically. Key words:Jess rule engine;data quality analysis;fact base;r ule base 在现代的企业级项目开发中,商业决策逻辑或业务规则往往是硬编码嵌入在系统各处代码中的。但是外部市场业务规则是随时可能发生变化的,这样开发人员必须时刻准备修改、更新系统,降低了效率。在这种背景下,规则引擎应运而生,它通过将业务规则和开发者的技术决策分离,实现了动态管理和修改业务规则而又不影响软件系统的需求。规则引擎具有广泛的应用领域,同样也适用于数据质量分析和清洗。 Jess是一个基于Java的规则引擎,是流行的CLIPS专家系统的Java实现,可以方便地嵌入到Java应用程序中。Jess采用产生式规则作为基本的知识表示,其核心由事实库、规则库和推理机组成。 Jess规则引擎的外部输入包括两部分:事实库和规则库。在数据质量分析应用中,待分析的数据构成了事实库,而所有业务规则构成了规则库。 1 事实库 Jess事实模板与数据库关系表定义有很好的对应关系: 表1 Jess事实模板与数据库关系表定义的对应 事实模板模板名槽名槽类型槽值 关系表定义表名字段名字段类型字段值 因此可以从待分析的数据库中抽取关系表的定义来构造事实模板,而关系表的每一条记录则对应一个事实。这样所有待分析的数据构成了事实库。假设有一个员工信息数据表employee,其字段定义如表2所示。 *收稿日期:2010 04 11 作者简介:史峰(1975 ),男,江苏省沭阳县人,讲师,主要从事数据库研究与数字化校园建设。 Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。 数学表述为：h = H(M) ，其中H( )--单向散列函数，M--任意长度明文，h--固定长度散列值。 在信息安全领域中应用的Hash算法，还需要满足其他关键特性： 第一当然是单向性(one-way)，从预映射，能够简单迅速的得到散列值，而在计算上不可能构造一个预映射，使其散列结果等于某个特定的散列值，即构造相应的M=H-1(h)不可行。这样，散列值就能在统计上唯一的表征输入值，因此，密码学上的Hash 又被称为"消息摘要(message digest)"，就是要求能方便的将"消息"进行"摘要"，但在"摘要"中无法得到比"摘要"本身更多的关于"消息"的信息。 第二是抗冲突性(collision-resistant)，即在统计上无法产生2个散列值相同的预映射。给定M，计算上无法找到M'，满足H(M)=H(M') ，此谓弱抗冲突性；计算上也难以寻找一对任意的M和M'，使满足H(M)=H(M') ，此谓强抗冲突性。要求"强抗冲突性"主要是为了防范所谓"生日攻击(birthday attack)"，在一个10人的团体中，你能找到和你生日相同的人的概率是2.4%，而在同一团体中，有2人生日相同的概率是11.7%。类似的，当预映射的空间很大的情况下，算法必须有足够的强度来保证不能轻易找到"相同生日"的人。 第三是映射分布均匀性和差分分布均匀性，散列结果中，为0 的bit 和为 1 的bit ，其总数应该大致相等；输入中一个bit 的变化，散列结果中将有一半以上的bit 改变，这又叫做"雪崩效应(avalanche effect)"；要实现使散列结果中出现1bit 的变化，则输入中至少有一半以上的bit 必须发生变化。其实质是必须使输入中每一个bit 的信息，尽量均匀的反映到输出的每一个bit 上去；输出中的每一个bit，都是输入中尽可能多bit 的信息一起作用的结果。 Damgard 和Merkle 定义了所谓"压缩函数(compression function)"，就是将一个固定长度输入，变换成较短的固定长度的输出，这对密码学实践上Hash 函数的设计产生了很大的影响。Hash函数就是被设计为基于通过特定压缩函数的不断重复"压缩"输入的分组和前一次压缩处理的结果的过程，直到整个消息都被压缩完毕，最后的输出作为整个消息的散列值。尽管还缺乏严格的证明，但绝大多数业界的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息也将是安全的。这就是所谓Damgard/Merkle 结构： 在下图中，任意长度的消息被分拆成符合压缩函数输入要求的分组，最后一个分组可能需要在末尾添上特定的填充字节，这些分组将被顺序处理，除了第一个消息分组将与散列初始化值一起作为压缩函数的输入外，当前分组将和前一个分组的压缩函数输出一起被作为这一次 6、8 哈希表及其查找★3◎4 哈希译自“haｓh"一词,也称为散列或杂凑。?哈希表查找得基本思想就是:根据当前待查找数据得特征,以记录关键字为自变量,设计一个哈希函数,依该函数按关键码计算元素得存储位置,并按此存放;查找时,由同一个函数对给定值ｋｅy计算地址,将ｋｅy与地址单元中元素关键码进行比较,确定查找就是否成功。哈希方法中使用得转换函数称为哈希函数(杂凑函数),按这个思想构造得表称为哈希表(杂凑表)。?对于n个数据元素得集合,总能找到关键码与存放地址一一对应得函数、若最大关键为m,可以分配m个数据元素存放单元,选取函数f(ke ｙ)=ｋey即可,但这样会造成存储空间得很大浪费,甚至不可能分配这么大得存储空间、通常关键码得集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同得关键码映射到同一个哈希地址上,这种现象称为冲突(Cｏlｌｉsio ｎ)。映射到同一哈希地址上得关键码称为同义词。可以说,冲突不可能避免,只能尽可能减少。所以,哈希方法需要解决以下两个问题:?(1)构造好得哈希函数?①所选函数尽可能简单,以便提高转换速度。?②所选函数对关键码计算出得地址,应在哈希地址集中大致均匀分布,以减少空间浪费。 (2)制定解决冲突得方案 1.常用得哈希函数 (1)直接定址法 即取关键码得某个线性函数值为哈希地址,这类函数就是一一对应函数,不会产生冲突,但要求地址集合与关键码集合大小相同,因此,对于较大得关键码集合不适用。如关键码集合为｛100,300,500,7０0,8０0,900｝,选取哈希函数为Hａ sh(key)=ｋey／100,则存放如表6-3所示。 表6—3 直接定址法构造哈希表 (２)除留余数法 即取关键码除以p得余数作为哈希地址。使用除留余数法,选取合适得p很重要,若哈希表表长为m,则要求p≤m,且接近ｍ或等于ｍ。p一般选取质数,也可以就是不包含小于20质因子得合数、?(3)数字分析法 设关键码集合中,每个关键码均由ｍ位组成,每位上可能有r种不同得符号、?数字分析法根据ｒ种不同得符号及在各位上得分布情况,选取某几位,组合成哈希地址。所选得位应就是各种符号在该位上出现得频率大致相同。 (4)平方取中法?对关键码平方后,按哈希表大小,取中间得若干位作为哈希地址。?(5)折叠法(Ｆoｌｄinｇ)?此方法将关键码自左到右分成位数相等得几部分,最后一部分位数可以短些,然后将这几部分叠加求与,并按哈希表表长,取后几位作为哈希地址。这种方法称为折叠法。?有两种叠加方法:?①移位法-—将各部分得最后一位对齐相加。 ②间界叠加法—-从一端向另一端沿各部分分界来回折叠后,最后一位对齐相加。?如对关键码为key=25３46358705,设哈希表长为３位数,则可对关键码每3位一部分来分割。关键码分割为如下4组: 253 ４６3 5８７05 分别用上述方法计算哈希地址如图6—12所示、对于位数很多得关键码,且每一位上符号分布较均匀时,可采用此方法求得哈希地址。 基于Java的规则引擎 目录 1.简介 (3) 1.1业务规则 (3) 1.2规则引擎产生背景 (3) 2.规则引擎 (4) 2.1业务规则 (4) 2.2规则引擎 (4) 2.3规则引擎的使用方式 (4) 2.4规则引擎架构与推理 (5) 2.5规则引擎的算法 (6) 3.Java规则引擎 (7) 3.1Java规则引擎商业产品 (7) 3.2规则引擎产品特点分析 (8) 3.2.1IBM WebSphere ILOG JRules (8) 3.2.2Redhat JBoss Dools (11) 3.2.3JESS (11) 4.Java规则引擎API（JSR94） (13) 4.1简介 (13) 4.2简介Java规则引擎API体系结构 (13) 3.2.4规则管理API (13) 3.2.5运行时API (14) 4.3Java规则引擎API安全问题 (15) 4.4异常与日志 (15) 4.5JSR94小结 (16) 5规则语言 (17) 1.简介 1.1业务规则 一个业务规则包含一组条件和在此条件下执行的操作．它们表示业务规则应用程序的一段业务逻辑。业务规则通常应该由业务分析人员和策略管理者开发和修改，但有些复杂的业务规则也可以由技术人员使用面向对象的技术语言或脚本来定制。 业务规则的理论基础是：设置一个或多个条件，当满足这些条件时会触发一个或多个操作。 1.2规则引擎产生背景 复杂企业级项目的开发以及其中随外部条件不断变化的业务规则（business logic），迫切需要分离商业决策者的商业决策逻辑和应用开发者的技术决策，并把这些商业决策放在中心数据库或其他统一的地方，让它们能在运行时（即商务时间）可以动态地管理和修改从而提供软件系统的柔性和适应性。规则引擎正是应用于上述动态环境中的一种解决方法。 企业管理者对企业级IT系统的开发有着如下的要求： 1.为提高效率，管理流程必须自动化，即使现代商业规则异常复杂； 2.市场要求业务规则经常变化，IT系统必须依据业务规则的变化快速、低成本的更 新； 3.为了快速、低成本的更新，业务人员应能直接管理IT系统中的规则，不需要程序 开发人员参与。 而项目开发人员则碰到了以下问题： 4程序=算法+数据结构，有些复杂的商业规则很难推导出算法和抽象出数据模型； 5软件工程要求从需求->设计->编码，然而业务规则常常在需求阶段可能还没有明确，在设计和编码后还在变化，业务规则往往嵌在系统各处代码中； 6对程序员来说，系统已经维护、更新困难，更不可能让业务人员来管理。 基于规则的专家系统的出现给开发人员以解决问题的契机。规则引擎由基于规则的专家系统中的推理引擎发展而来。 密码学 （第十三讲） HASH函数 张焕国 武汉大学计算机学院 目录 密码学的基本概念 1、密码学 2、古典 、古典密码 3、数据加密标准（ ） DES） 、数据加密标准（DES 4、高级 ） AES） 数据加密标准（AES 高级数据加密标准（ 5、中国商用密码（ ） SMS4） 、中国商用密码（SMS4 6、分组密码的应用技术 7、序列密码 8、习题课：复习对称密码 、公开密钥密码（11） 9、公开密钥密码（ 目录 公开密钥密码（22） 10 10、 11、数字签名（1） 12、数字签名（2） 13、 、HASH函数 13 14 14、 15、 15 PKI技术 16 16、 、PKI 17、习题课：复习公钥密码 18、总复习 一、HASH 函数函数的概念的概念 1、Hash Hash的作用的作用 ?Hash Hash码也称报文摘要码也称报文摘要。。 ?它具有极强的错误检测能力错误检测能力。。 ?用Hash Hash码作码作MAC ，可用于认证认证。。 ?用Hash Hash码辅助码辅助数字签名数字签名。。 ?Hash Hash函数可用于函数可用于保密保密。。 一、HASH 函数的概念 2、Hash Hash函数的定义函数的定义 ①Hash Hash函数将任意长的数据函数将任意长的数据M 变换为定长的码h ， 记为记为：：h=HASH(M)h=HASH(M)或或h=H(M)h=H(M)。。 ②实用性：对于给定的数据对于给定的数据M M ，计算，计算h=HASH(M)h=HASH(M)是是 高效的。 ③安全性安全性：： ? 单向性：对给定的对给定的Hash Hash值值h ，找到满足H(x)H(x)＝＝h 的x 在 计算上是不可行的计算上是不可行的。。 否则否则，，设传送数据为设传送数据为C=C=＜＜M ，H(M||K )＞,K 是密钥。攻击者可以截获攻击者可以截获C,C,求出求出Hash 函数的逆函数的逆，，从而得出 M||S ＝H -1(C)，然后从M 和M ||Ｋ即可即可得出得出Ｋ。 第一章计算机信息安全技术概述 1、计算机信息系统安全的威胁因素主要有哪些? (1)人为无意失误 (2)人为恶意攻击 (3)计算机软件的漏洞和后门 2、从技术角度分析引起计算机信息系统安全问题的根本原因。 (1)计算机外部安全 (2)信息在计算机系统存储介质上的安全 (3)信息在传输过程中的安全 3、信息安全的CIA指的是什么? Confidenciality 隐私性,也可称为机密性,是指只有授权的用户才能获取信息Integrity 完整性,是指信息在传输过程中,不被非法授权和破坏,保证数据的一致性 Availability 可用性,是指信息的可靠度 4、简述PPDR安全模型的构成要素及运作方式 PPDR由安全策略,防护,检测和响应构成 运作方式:PPDR模型在整体的安全策略的控制和指导下,综合运用防护工具的同时,利用检测工具了解和评估系统的安 全状态,通过适当的安全响应将系统调整在一个相对安全的状态。防护,检测和响应构成一个完整的、动态的安全循环。 5、计算机信息安全研究的主要内容有哪些? (1)计算机外部安全 (2)信息在计算机系统存储介质上的安全 (3)信息在传输过程中的安全 6、计算机信息安全的定义是什么? 计算机信息安全是研究在特定的应用环境下,依据特定的安全策略,对信息及信息系统实施防护,检测和恢复的科学 7、信息安全系统中,人、制度和技术之间的关系如何? 在信息安全系统中,人是核心。任何安全系统的核心都是人。而技术是信息安全系统发展的动力,技术的发展推动着信息安全系统的不断完善。信息安全系统不仅要靠人和技术,还应该建立相应的制度以起到规范的作用。只有三者的完美结合,才有安全的信息安全系统 哈希算法乱谈（摘自知乎） 最近【现场实战追-女孩教-学】初步了解了Hash算法的相关知识，一些人的见解让我能够迅速的了解相对不熟悉的知识，故想摘录下来，【QQ】供以后温故而知新。 HASH【⒈】算法是密码学的基础，比较常用的有MD5和SHA，最重要的两【О】条性质，就是不可逆和无冲突。 所谓不【１】可逆，就是当你知道x的HASH值，无法求出x； 所谓无【б】冲突，就是当你知道x，无法求出一个y，使x与y的HA【９】SH值相同。 这两条性【⒌】质在数学上都是不成立的。因为一个函数必然可逆，且【２】由于HASH函数的值域有限，理论上会有无穷多个不同的原始值【６】，它们的hash值都相同。MD5和SHA做到的，是求逆和求冲突在计算上不可能，也就是正向计算很容易，而反向计算即使穷尽人类所有的计算资-源都做不到。 顺便说一下，王小云教授曾经成功制造出MD5的碰撞，即md5(a) = md5(b)。这样的碰撞只能随机生成，并不能根据一个已知的a求出b（即并没有破坏MD5的无冲突特性）。但这已经让他声名大噪了。 HASH算法的另外一个很广泛的用途，就是很多程序员都会使用的在数据库中保存用户密码的算法，通常不会直接保存用户密码（这样DBA就能看到用户密码啦，好危险啊），而是保存密码的HASH值，验 证的时候，用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致，从而完成验证。由于用户的密码的一样的可能性是很高的，防止DBA猜测用户密码，我们还会用一种俗称“撒盐”的过程，就是计算密码的HASH值之前，把密码和另外一个会比较发散的数据拼接，通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的，会很发散。最后，作为一个老程序员，我会把用户的HASH值保存好，然后把我自己密码的HASH值保存到数据库里面，然后用我自己的密码和其他用户的用户名去登录，然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是，数据库泄露后，得到用户数据库的黑客看着一大堆HASH值会翻白眼。 哈希算法又称为摘要算法，它可以将任意数据通过一个函数转换成长度固定的数据串（通常用16进制的字符串表示），函数与数据串之间形成一一映射的关系。 举个粒子，我写了一篇小说，摘要是一个string:'关于甲状腺精灵的奇妙冒险'，并附上这篇文章的摘要是'2d73d4f15c0db7f5ecb321b6a65e5d6d'。如果有人篡改了我的文章，并发表为'关于JOJO的奇妙冒险'，我可以立即发现我的文章被篡改过，因为根据'关于JOJO的奇妙冒险'计算出的摘要不同于原始文章的摘要。 可见，摘要算法就是通过摘要函数f()对任意长度的数据data计算出固定长度的摘要digest，目的是为了发现原始数据是否被人篡 1. 引言 哈希表（Hash Table）的应用近两年才在NOI（全国青少年信息学奥林匹克竞赛）中出现，作为一种高效的数据结构，它正在竞赛中发挥着越来越重要的作用。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 哈希表又叫做散列表，分为“开散列” 和“闭散列”。考虑到竞赛时多数人通常避免使用动态存储结构，本文中的“哈希表”仅指“闭散列”，关于其他方面读者可参阅其他书籍。 2. 基础操作 2.1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。后面我们将看到一种解决“冲突”的简便做法。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 2.2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p ，这里，p 如果选取的是比较大 的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 2.3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k)已经存储了元素的时候，依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 2.4 支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(i nsert)、查找元素(member)。设插入的元素的关键字为x ，A 为存储的数组。初始化比较容易，例如： const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子：哈希算法散列
什么是哈希函数
Java规则引擎工作原理及应用
数据结构课程设计哈希表设计问题复习过程
最小完美哈希函数(深入搜索引擎)
规则引擎研究-整理
哈 希 常 见 算 法 及 原 理
Java规则引擎工作原理及其应用
哈 希 常 见 算 法 及 原 理
Jess规则引擎在数据质量分析中的应用
hash算法
哈希的基本概念
基于JAVA的规则引擎
HASH函数
计算机信息安全技术课后习题答案
哈 希 常 见 算 法 及 原 理 ( 2 0 2 0 )
散列表(哈希表)