- 浏览: 741463 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
u011487470:
感觉就是知识采集一样,博主能不能整理一下
基于Web的IM简介 -
whxtbest:
whxtbest 写道2里面:如果T本身就是重复的话 比如 ...
关于后缀树的一些理解 -
whxtbest:
2里面:如果T本身就是重复的话 比如S是aaab,T是aa ...
关于后缀树的一些理解 -
刘亮love小雪:
谢谢啦
Java 2D高级绘图 -
bluky999:
收集的资料挺多的 哈哈
基于Web的IM简介
以前一直觉得hash函数很深奥,上王珊的《数据库实现原理》的时候,似乎明白了一点点,但是到学java
的时候,频繁接触到hashcode(),hashMap这些,就总在想这三者之间有关系吗?hash函数是什么?hashcode(),
hashMap和hash函数又有什么关系呢?
今天终于对这个问题有了初步的学习和理解:
1.什么是hash函数:
1)来自:http://beyond911.bokee.com/1047973.html
什么是HASH函数(经典例子)
让我们先来了解一些基本知识,作作预热只有这样才能更好的了解hash。
Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法,他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系
2)来自:http://www.hour41.com/blog/hour41/entry/200701255
计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。
Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
3)自己的总结:
a)hash函数就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。
例如,散列算法为求余的hash函数。
b)实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。
c)在数据结构中,hash就是找到一种数据内容和数据存放地址之间的映射关系,比如,31对10求余后得1,就把31存放到第一个桶里(或者是第一块内存单元中),即把数据和存放地址建立映射关系;
d)所以,有了数据内容和数据存放地址之间的映射关系,Hash函数往往应用于查找上。不过,利用hash函数的查找跟以前自己理解的不同,以前自己以为是通过hash函数就能立即找到存储地址,就像HashMap中根据key立即能找到value一样,其实不是这样的,hash函数只不过是根据散列算法和解决冲突的方法来提供一种定位和查找的方式,hashmap中根据可以马上找到value值是理所当然的,但是根据hash函数找到key值就不是立即的了。当然,为了方便查找,尽量使得hash函数无冲突,可以唯一确定地址是最理想的。娃哈哈,终于弄清楚这一点了!
e)Hash函数是指把一个大范围映射到一个小范围,所以hash函数是求余之类的压缩函数,(比如,11,13的范围压缩为1,3),而不是10x+7这样的扩散函数,(比如,11,13的范围扩散为117,137);
f)由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
g)不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
2.散列表相关知识的系统学习:
数据结构自考网:http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.4.1.htm
3. JDK中HashMap的分析
1)来自:http://chinakite.iteye.com/blog/25073
2)请问hashtable类里面的hash函数是怎么样的?
来自:http://topic.csdn.net/t/20020311/09/567386.html
他是调用每个类自己本身的hashCode的方法来确定的
public synchronized Object put(Object key, Object value) {
...
int hash = key.hashCode();//就是这里了
int index = (hash & 0x7FFFFFFF) % tab.length;
...
}
详细请看java的源文件
String的散列值是由内容转换来的,Object类的却省散列函数返回对象地址转换来的散列值。
4.面试题:
来自:http://www.javaref.cn/topics/Question/10566.html
问题:
a)请问哈希表 (hashtable) 是如何存储数据的 ?
答案: Hashtable 是用来存储 key 和 value 对的数据结构 , 根据设定的 hash 函数 H(key) 和处理冲突的方法将一组关键字( key )映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中存储位置,这种表便成为 hashtable.
b)是否两个键值通过 hash 函数产生的映射地址会一样?怎么办?
答案 : 是,一般情况下,完全避免冲突是很难的。因为通常关键字集合会比目标地址空间大。哈希函数要尽量避免冲突(避免不同的关键字产生相同的 hash 值),使一组关键字的哈西地址尽可能的均匀分布在整个地址区间。所以有一些冲突处理方法:开放定址法,再哈希法,链地址法(用链表保存冲突的值),公共溢出区。
关于哈希表,有个与实际编程更密切的问题可以一问:为保证逻辑上的正确性,哈希表对可以作为键值的类型有什么要求? C++:除容器对元素类型的标准需求外,还需overload == 和 < Java:需override equals(逻辑上的正确性)和hashCode(性能) C#:需override Equals(逻辑上的正确性)和HashCode(性能)
的时候,频繁接触到hashcode(),hashMap这些,就总在想这三者之间有关系吗?hash函数是什么?hashcode(),
hashMap和hash函数又有什么关系呢?
今天终于对这个问题有了初步的学习和理解:
1.什么是hash函数:
1)来自:http://beyond911.bokee.com/1047973.html
什么是HASH函数(经典例子)
让我们先来了解一些基本知识,作作预热只有这样才能更好的了解hash。
Hash,一般翻译做"散列",也有直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。
简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法,他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系
2)来自:http://www.hour41.com/blog/hour41/entry/200701255
计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。
Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
3)自己的总结:
a)hash函数就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。
例如,散列算法为求余的hash函数。
b)实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。
c)在数据结构中,hash就是找到一种数据内容和数据存放地址之间的映射关系,比如,31对10求余后得1,就把31存放到第一个桶里(或者是第一块内存单元中),即把数据和存放地址建立映射关系;
d)所以,有了数据内容和数据存放地址之间的映射关系,Hash函数往往应用于查找上。不过,利用hash函数的查找跟以前自己理解的不同,以前自己以为是通过hash函数就能立即找到存储地址,就像HashMap中根据key立即能找到value一样,其实不是这样的,hash函数只不过是根据散列算法和解决冲突的方法来提供一种定位和查找的方式,hashmap中根据可以马上找到value值是理所当然的,但是根据hash函数找到key值就不是立即的了。当然,为了方便查找,尽量使得hash函数无冲突,可以唯一确定地址是最理想的。娃哈哈,终于弄清楚这一点了!
e)Hash函数是指把一个大范围映射到一个小范围,所以hash函数是求余之类的压缩函数,(比如,11,13的范围压缩为1,3),而不是10x+7这样的扩散函数,(比如,11,13的范围扩散为117,137);
f)由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
g)不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
2.散列表相关知识的系统学习:
数据结构自考网:http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.4.1.htm
3. JDK中HashMap的分析
1)来自:http://chinakite.iteye.com/blog/25073
2)请问hashtable类里面的hash函数是怎么样的?
来自:http://topic.csdn.net/t/20020311/09/567386.html
他是调用每个类自己本身的hashCode的方法来确定的
public synchronized Object put(Object key, Object value) {
...
int hash = key.hashCode();//就是这里了
int index = (hash & 0x7FFFFFFF) % tab.length;
...
}
详细请看java的源文件
String的散列值是由内容转换来的,Object类的却省散列函数返回对象地址转换来的散列值。
4.面试题:
来自:http://www.javaref.cn/topics/Question/10566.html
问题:
a)请问哈希表 (hashtable) 是如何存储数据的 ?
答案: Hashtable 是用来存储 key 和 value 对的数据结构 , 根据设定的 hash 函数 H(key) 和处理冲突的方法将一组关键字( key )映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象”作为记录在表中存储位置,这种表便成为 hashtable.
b)是否两个键值通过 hash 函数产生的映射地址会一样?怎么办?
答案 : 是,一般情况下,完全避免冲突是很难的。因为通常关键字集合会比目标地址空间大。哈希函数要尽量避免冲突(避免不同的关键字产生相同的 hash 值),使一组关键字的哈西地址尽可能的均匀分布在整个地址区间。所以有一些冲突处理方法:开放定址法,再哈希法,链地址法(用链表保存冲突的值),公共溢出区。
关于哈希表,有个与实际编程更密切的问题可以一问:为保证逻辑上的正确性,哈希表对可以作为键值的类型有什么要求? C++:除容器对元素类型的标准需求外,还需overload == 和 < Java:需override equals(逻辑上的正确性)和hashCode(性能) C#:需override Equals(逻辑上的正确性)和HashCode(性能)
发表评论
-
求交集和并集的线性算法
2011-10-24 23:00 5304对于给定的两个集合,使用哈希表可以在线性时间复杂度内得到他们的 ... -
关于后缀树的一些理解
2008-10-01 21:07 9010要理解suffix tree就首先 ... -
面试题集锦
2008-09-29 17:24 35631. 时针分针重合几次 表面上有60个小格,每小格代表一分钟, ... -
词频统计的C++实现
2008-03-10 16:01 3746#include <map> # ... -
Google面试题(九)
2008-02-20 00:13 275325匹马赛跑,5个跑道,怎么以最少的比赛次数来决出最快的3匹, ... -
数据结构面试大全
2008-02-19 12:50 44731.判断链表是否存在环 ... -
Google面试题(七)
2008-02-14 03:35 3037很多Google考生出来,也 ... -
Google面试题(六)
2008-02-14 03:03 6007题目:对现在的Stack(栈)数据结构进行改进,加一个min( ... -
Google面试题(五)
2008-02-14 02:30 2663几星期前,一个朋友接 ... -
Google面试题(四)
2008-02-13 22:07 226126个英文字母从新排序(未知的顺序alphabet),然后用这 ... -
google面试题(三)
2008-02-13 06:22 2499算法题一:Given 1 GB memory, input a ... -
google面试题(二)
2008-02-11 01:43 3484平面上N个点,求一条直线,穿过的点数最多 思路:2点确定一条 ... -
google面试题(一)
2008-02-11 01:27 2484有一个random number generator,是生成真 ... -
数据结构和算法中容易忽略的要点总结[未完待续]
2008-02-10 23:44 14391。递归需要有个递归出口,否则会是infinite的递归 -
矩阵求逆的快速算法
2008-02-10 20:40 3895算法介绍 矩阵求逆在3D ... -
约瑟夫问题
2008-02-10 09:57 1995有n个人围成一圈,顺序编号。从第一个人开始报数,凡报到m的人退 ... -
突然发现没真正领悟哈希表
2008-02-10 05:11 2555在一个字符串中找到第 ... -
[微软面试题]请把一个整形数组中重复的数字去掉
2008-02-10 04:08 4354请把一个整形数组a中重复的数字去掉 方法一: for i ... -
Java版堆排序
2008-02-09 23:41 1151/** * author Akalius Kung 2008 ... -
Java版插入排序
2008-02-09 04:40 1471/** * author Akalius Kung 2008 ...
相关推荐
hashmap中hash函数的构造问题,提供了各种构造方法。以及比较函数的构造 挺适合入门学习的
hash函数与消息认证讲义 包括 5.1 Hash函数概述 5.1.1 Hash函数定义 5.1.2 Hash函数的安全性 5.1.3 Hash函数的迭代构造法 5.2 Hash函数MD5 5.2.1 MD5算法 5.2.2 MD5的安全性 5.3 安全Hash算法SHA-1 5.3.1 SHA-1...
Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名
关于hash函数的ppt
RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....
提出了一种基于可并行和变参数的混沌分段线性映射hash函数算法。该函数通过明文扩展将并行处理的明文消息...计算机模拟表明,本算法具有较好的单向性、混乱、扩散性以及抗碰撞性,满足单向hash 函数的各项性能要求。
Hash函数研究综述 一篇非常不错的关于哈希函数的研究综述 07年发表的
Hash函数及数字签名应用实验 验证码的实现过程
HASH函数,用来提取摘要160bits。HASH函数,用来提取摘要160bits。HASH函数,用来提取摘要160bits。
hash字符串函数总结,挥泪大放送,绝对全面,各类总结。
该文档中包含 bloomFilter过滤器中用到的对于字符串进行hash的hash函数共十一个,并带有测试程序..
在分组序号和分组消息满足特定约束关系的条件下,无需复杂的计算可以直接给出特定分组和消息的中间 Hash 值。对于后者,分析了产生碰撞缓存器状态的约束条件。在此条件下,找到算法的输出碰撞的代价为 O ( 2100 ) ,...
该函数可以在输入Hash_QueryParameters.txt文件下,每行为一个数据(可以随便写)输入哈希表中,可以查找,删除,插入等操作
这是清华大学王老师报告PPT,介绍了密码HASH函数上研究的最新成果
uthash开源的hash函数实现,里面的uthash.h可用
Hash函数代码,便于结合原理与实践。你可以下载后学习,更希望你能分享出更好的代码
本文主要介绍Hash函数的设计优化,包括数字、字符串、排列等,并给出相关的代码。
hash函数实例 c语言版 不喜勿喷!
混沌加密算法与HASH函数构造研究_12767438.zip
hash函数 的 c语言版 大家可以试试 不喜勿喷!