js中has,js计算hash值
本教程运行环境：windows7系统，javascript1.8.5版本1.8.5，戴尔G3电脑。
javascript hash的基本概念：
哈希表是根据关键字直接访问内存存储位置的数据结构。通过哈希表，在数据元素的存储位置和数据元素的关键字之间建立了一定的对应关系。建立这种对应关系的函数称为哈希函数。
哈希表的构造方法：
假设要存储的数据元素个数为n，设置一个长度为m(m ^ n)的连续存储单元，将每个数据元素的key Ki(0=i=n-1)作为自变量，通过hash函数将Ki映射到存储单元的地址hash(Ki)中，将数据元素存储在存储单元中。
从数学的角度来看，哈希函数实际上是关键字到存储单元的映射。因此，我们希望通过最简单的运算，将哈希函数计算出的华西地址尽可能均匀地投影到一系列存储单元中。构造hash函数有三个关键点：(1)操作过程要尽可能简单高效，提高哈希表的插入和查找效率；(2)哈希函数要有好的哈希类型，减少哈希冲突的概率；第三，哈希函数应该更具可压缩性，以节省内存。
常用方法：
直接寻址法：取一个关键字的线性函数值作为哈希地址，可以表示为hash(K)=aK C；优点是不会有冲突，缺点是空间复杂度可能会更高，适合元素较少的情况。余数方法：它是一个散列地址，通过将数据元素关键字除以某个常数而得到余数。该方法计算简单，应用广泛。它是一个常用的哈希函数，可以表示为：
hash(K=K mod C；这种方法的关键是常数的选取，一般要求接近或等于哈希表本身的长度。研究理论表明，选择质数时常数的效果最好：这种方法将数据元素的关键字中一些取值为偶数的数作为哈希地址，尽可能避免冲突，但这种方法只适用于所有已知的关键字，不适合设计更一般的哈希表。平方求和法：将当前字符串转换为Unicode值，求该值的平方。平方值的中间位是当前数的哈希值，这取决于当前哈希表的大小。分段求和法：根据当前哈希表的位数，将待插入的值分成若干段，将各段相加，去掉最高位，得到该值的哈希值。哈希冲突的解决方案：
在构造哈希表时，有这样一个问题：对于两个不同的关键字，通过我们的哈希函数计算哈希地址时，得到的是相同的哈希地址。我们称这种现象为哈希冲突。
哈希冲突主要与两个因素有关。
(1)填充因子，指哈希表中存储的数据元素个数与哈希地址空间大小的比值，a=n/m；A越小，冲突的可能性越小；反之，冲突的可能性就越大；但是，A越小，空间利用率就越小，A越大，空间利用率就越高。为了兼顾哈希冲突和存储空间利用率，A通常控制在0.6到0.9之间，而HashTable在。net直接将A的最大值定义为0.72(虽然微软官方MSDN声明HashTable的默认填充因子是1.0，实际上是0.72的倍数)
(2)与使用的哈希函数有关。如果哈希函数合适，哈希地址可以尽可能均匀地分布在哈希地址空间中，从而减少冲突的发生。然而，一个好的散列函数的成功很大程度上取决于大量的实践。
1)开放式寻址方法
Hi=(H(key) di) MOD m i=1，2，…k(k=m-1)
其中H(key)是哈希函数；m是哈希表的长度；Di是一个增量序列。有3个增量序列：
线性检测和哈希：di=1，2，3，…，m-1
二次检测重散列：di=12，-12，22，-22，… k 2 (k=m/2)
伪随机检测和哈希：di=伪随机数序列
缺点：
我们可以看到一个现象：当表中的I，i 1，i 2位置已经被记录填充后，下一个hash地址为I，i 1，i 2，i 3的记录都会被填充到i 3位置。这种第一哈希地址不同的两条记录在处理冲突的过程中争夺同一后续哈希地址的现象称为“二次聚合”，即在处理同义词冲突的过程中加入了非同义词冲突。另一方面，使用线性检测和哈希来处理冲突，可以确保只要哈希表没有满，我们就总能找到一个没有冲突的地址Hk。然而，只有当散列表长度m是像4j ^ 3(j是整数)这样的质数时，通过二次检测进行重新散列才是可能的。即开放式寻址方式会造成二次聚集现象，不利于查找。
2)重新散列
Hi=RHi(key)，i=1，2，…k RHi都是不同的哈希函数，即当同义词产生地址冲突时，计算另一个哈希函数地址，直到不发生冲突。这种方法不容易产生聚合，但增加了计算时间。
缺点：计算时间增加。
3)链地址法(拉链法)
所有带有同义词的记录都存储在同一个线性链表中。
优势：
Zipper法处理冲突简单，没有积累现象，即非同义词永远不会有冲突，所以平均搜索长度短；
由于zipper方法中每个链表上的节点空间是动态应用的，所以更适用于在做表之前无法确定表长的情况；
为了减少冲突，开放式寻址方式要求填充因子很小，所以当节点规模较大时，会浪费大量空间。而当zipper方法采用1，节点较大时，zipper方法中增加的指针字段可以忽略，从而节省空间；
在zipper方法构建的哈希表中，很容易删除节点。只需删除链表上相应的节点。但是对于开放地址法构建的哈希表，删除节点不能简单的清空被删除节点的空间，否则哈希表中填充的同义词节点的搜索路径会被截断。这是因为在各种开放地址方法中，空地址单元(即开放地址)是查找失败的条件。所以用开放地址法删除哈希表时，只能标记删除的节点，不能真正删除节点。
缺点：
zipper方法的缺点是指针需要额外的空间，所以当节点尺寸较小时，开放式寻址方法节省更多的空间。如果将节省下来的指针空间用于扩展哈希表的大小，那么填充因子就会降低，从而减少开放式寻址方法中的冲突，提高平均搜索速度。
4)建立公共溢出区。
假设hash函数的取值范围为[0，m-1]，设向量HashTable[0…m-1]为基本表，每个组件存储一条记录，设向量OverTable[0…v]为溢出表。所有其关键字与基本表中的关键字是同义词的记录，无论其哈希函数获得的哈希地址如何，一旦有冲突，都将被填充到溢出表中。
使用简单哈希函数实现无冲突处理的哈希表
类哈希{
构造函数(){
this.table=新数组(1024)；
}
哈希(数据){
//将字符串中每个字符的ASCLL代码值相加，然后取数组长度的余数。
var total=0；
for(var I=0；I数据长度；i ) {
total=data . charcode at(I)；
}
console.log(哈希值： 数据-合计)；
返回总计% this . table . length；
}
插入(键，值){
var pos=this . hash(key)；
this . table[pos]=val；
}
获取(密钥){
var pos=this . hash(key)；
返回此表[pos]
}
show() {
for(var I=0；我这个.表.长度；i ) {
if (this.table[i]！=未定义){
console . log(I : this . table[I])；
}
}
}
}
var someNames=[David ， Jennifer ， Donnie ， Raymond ， Cynthia ， Mike ， Clayton ， Danny ， Jonathan ]；
var Hash=new Hash()；
for(var I=0；我有些名字。长度；i) {
hash.insert(someNames[i]，some names[I])；
}
hash.show()。
哈希函数采用取平方方法构造，冲突采用开放地址线性检测方法解决。
类哈希{
构造函数(){
this.table=新数组(1000)；
}
哈希(数据){
var total=0；
for(var I=0；我数据长度；i ) {
总计=数据。charcode at(I)；
}
//把字符串转化为字符用来求和之后进行平方运算
var s=总计*总计
//保留中间2位
定义变量指数=s . charat(s . length/2-1)* 10s。字符(长度/2)* 1
console.log(哈希值： 数据-索引);
回报指数；
}
解决冲突(索引，值){
var table=this.table
//进行线性开放地址法解决冲突
for(var I=0；指数i 1000i ) {
如果(表[索引i]==null) {
表[索引我]=值；
打破；
}
}
}
插入（键，值){
var指数=这个。哈希(键)；
//把取中当做哈希表中索引
if (this.table[index]==null) {
这个。table[index]=val；
}否则{
this.solveClash(index，val)；
}
}
获取（密钥){
var pos=this。哈希(键)；
返回此表[位置]
}
show() {
for(var I=0；我这个。表。长度；i ) {
if (this.table[i]！=未定义){
控制台。log(I): this。表[I])；
}
}
}
}
var someNames=[David ， Jennifer ， Donnie ， Raymond ， Cynthia ， Mike ， Clayton ， Danny ， Jonathan ]；
var Hash=new Hash()；
for(var I=0；我有些名字。长度；i) {
hash.insert(someNames[i]，some names[I])；
}
hash.show()。
【推荐学习：javascript高级教程】以上就是java描述语言哈希是什么的详细内容，更多请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。