文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 互联网 > 常见的几种hash算法的原理
侵权投诉

常见的几种hash算法的原理

常见的几种hash算法的原理

2011-07-13 17:51

几种经典的hash算法

注:最近因为在做和hash有关的题目,感到很纠结。虽然上学期数据结构学过,但是当时觉得hash没什么用,所以没有认真学~后悔啊~~~现在恶补一下~

计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人 类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函 数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。

Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:

1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。

2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。

3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

应用于加密的Hash函数已经探讨过太多了,在作者的博客里面有更详细的介绍。所以,本文只探讨用于查找的Hash函数。Hash函数应用的主要对象是数组(比如,字符串),而其目标一般是一个int类型。以下我们都按照这种方式来说明。一般的说,Hash函数可以简单的划分为如下几类:

1. 加法Hash;

2. 位运算Hash;

3. 乘法Hash;

4. 除法Hash;

5. 查表Hash;

6. 混合Hash;

下面详细的介绍以上各种方式在实际中的运用。

一 加法Hash

所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:

static int additiveHash(String key, int prime)

{

int hash, i;

for (hash = key.length(), i = 0; i < key.length(); i++)

hash += key.charAt(i);

return (hash % prime);

}

这里的prime是任意的质数,看得出,结果的值域为[0,prime-1]。

二 位运算Hash

这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比如,标准的旋转Hash的构造如下: static int rotatingHash(String key, int prime)

{

int hash, i;

for (hash=key.length(), i=0; i<key.length(); ++i)

hash = (hash<<4)^(hash>>28)^key.charAt(i);

return (hash % prime);

}

先移位,然后再进行各种位运算是这种类型Hash函数的主要特点。比如,以上的那段计算hash的代码还可以有如下几种变形:

1. hash = (hash<<5)^(hash>>27)^key.charAt(i);

2. hash += key.charAt(i);

hash += (hash << 10);

hash ^= (hash >> 6);

3. if((i&1) == 0)

{

hash ^= (hash<<7) ^ key.charAt(i) ^ (hash>>3);

}

else

{

第1页

你可能喜欢

热门文档

相关文档

  • Hash 函数的常用算法和应用领域

    Hash 函数的常用算法和应用领域 1.Hash 介绍 Hash 这个在实现某些功能的经常会...所以,在考虑使用 Hash 函数之前,需要明白它的几个限制: 1. Hash 的主要原理...

  • simhash算法的原理

    simhash算法的原理_计算机软件及应用_IT/计算机_专业资料。传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值,原理上相当于伪随机数产生算法。传统hash...

  • 常用的几个著名哈希算法源代码.cs

    常用的几个著名哈希算法源代码.cs_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 常用的几个著名哈希算法源代码.cs_IT/计算机_专业资料。class General...

  • 常见hash算法

    常用的几个著名哈希算法源... 2页 免费 Hash算法 1页 2财富值 Hash算法 6...本文档中介绍了常见的各种hash算法,作者用通俗的语言,言简意赅!本文档中介绍了常...

  • Hash算法原理及在快速检索中的应用

    本文介绍了 Hash 算法原理,并从一个校园网流量计费系统的实例入手,诠释快速检索...常用的定 位方法有以下几种: 1. 直接寻址法:取关键字或关键字的某个线性...

  • 几种经典的Hash算法的实现(源代码)

    几种经典的Hash算法的实现(源代码)_IT/计算机_专业资料。几种经典的Hash算法的实现(源代码)链表查找的时间效率为 O(N),二分法为 log2N,B+ Tree 为 log2N,但...

  • 经典哈希算法 new

    被逼的,发个技术文章吧(几种经典的 hash 算法) ...Hash 的主要原理就是把大范围映射到小范围;所以,你...函数通过利用各种位运算(常见的是移位和异或)来充分...

  • 关于对哈希算法的研究与应用

    几种,分别为:md2、md4、md5 和安全哈希算法(sha...哈希表的工作原理就是把一个数据帧按照某一种设定好...的算法就是哈希 算法,其中以 md5 算法最为常见。...

  • hash_join算法原理

    sheagle@yeah.net Hash join 算法原理自从 oracke 7...oracle 引进了几种技术,位图向量过滤、角色互换、...常见hash算法 9页 免费 字符串hash算法比较 6页 免费...

  • 几种经典的Hash算法的实现(源代码)

    几种经典的Hash算法的实现(源代码)_IT/计算机_专业资料。几种经典的Hash算法的实现(源代码)链表查找的时间效率为 O(N),二分法为 log2N,B+ Tree 为 log2N,但...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email