什么是哈希表?做什么的?大多数用在什么地方?有个小代码实例更好。 RT 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 用于把一对“键”和“值”相关键,比如可以把姓名(String)跟一个学生信息记录(一个Student类的对象)关键起来,用于基于姓名的快速查找。更多的知识可以找本数据结构的书来看看。 简单小实例:Hashtable<String, Integer> numbers = new Hashtable<String, Integer>(); numbers.put("one", 1); numbers.put("two", 2); numbers.put("three", 3); Integer n = numbers.get("two"); if (n != null) { System.out.println("two = " + n); } 这问题可以 去看下JAVA的数据结构 是种数据结构 可以提高查询,删除的效率了 就是hash值满了的时候重新hash时效率较低 字符串哈希函数(著名的ELFhash算法) int ELFhash(char *key) { unsigned long h=0; while(*key) { h=(h<<4)+*key++; unsigned long g=h&0Xf0000000L; if(g) h^=g>>24; h&=~g; } return h%MOD; } 概念性问题,只要Google或Baidu一下就可以的,没必要来这里浪费资源和时间吧? 一般的线性表、树中,记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上,查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此不需要进行比较便可直接取得所查记录。在此,称这个对应关系f为哈希函数,按这个思想建立的表为哈希表(又称为杂凑法或散列表)。 哈希表不可避免冲突(collision)现象:对不同的关键字可能得到同一哈希地址 即key1≠key2,而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲突的方法。可如下描述哈希表:根据设定的哈希函数H(key)和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置,这种表被称为哈希表。 对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个函数f(key)为哈希函数。(注意:这个函数并不一定是数学函数) 哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可。 现实中哈希函数是需要构造的,并且构造的好才能使用的好。 用途:加密,解决冲突问题。 用途很广,比特精灵中就使用了哈希函数,你可 以自己看看。 具体可以学习一下数据结构和算法的书。 字符串哈希函数(著名的ELFhash算法) int ELFhash(char *key) { unsigned long h=0; while(*key) { h=(h<<4)+*key++; unsigned long g=h&0Xf0000000L; if(g) h^=g>>24; h&=~g; } return h%MOD; } myeclipse设置java内存问题! 这个SQL异常怎么回事? 如何实现有序的字符串序列? 怎么打包成jar文件哦? Can someone help me with the "Thread"? (can't type Chinese, sorry) 如何比较两张结构相同的表,找出差异? 请问float如何转换成String???? 对象怎么序列化和反序列化? jdbc 连接sybase11.9时出错,错误提示:JZ0D5: 装载协议 com.sybase.jdbc2.tds.tds 时出错 简单的问题解码 讨论,下面的一段代码会产生死锁吗? think in java 第四版错误
更多的知识可以找本数据结构的书来看看。
Hashtable<String, Integer> numbers
= new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);
Integer n = numbers.get("two");
if (n != null) {
System.out.println("two = " + n);
}
重新hash时效率较低
{ unsigned long h=0;
while(*key)
{ h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}
哈希表不可避免冲突(collision)现象:对不同的关键字可能得到同一哈希地址 即key1≠key2,而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲突的方法。可如下描述哈希表:根据设定的哈希函数H(key)和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置,这种表被称为哈希表。
对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个函数f(key)为哈希函数。(注意:这个函数并不一定是数学函数)
哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可。
现实中哈希函数是需要构造的,并且构造的好才能使用的好。
用途:加密,解决冲突问题。
用途很广,比特精灵中就使用了哈希函数,你可 以自己看看。
具体可以学习一下数据结构和算法的书。
字符串哈希函数(著名的ELFhash算法)
int ELFhash(char *key)
{ unsigned long h=0;
while(*key)
{ h=(h<<4)+*key++;
unsigned long g=h&0Xf0000000L;
if(g) h^=g>>24;
h&=~g;
}
return h%MOD;
}