Jenkins哈希的Javascript实现?
有没有我可以使用的詹金斯哈希的JavaScript实现 - 而不是自己实现它?Jenkins哈希的Javascript实现?
我知道有一个python实现我可以用来写我自己的js。但我不是JavaScript专家,因此我宁愿有人执行。
更新:(我曾尝试转换http://www.burtleburtle.net/bob/c/lookup3.c) 更新2:此代码为您提供了相同的哈希值作为hashlittle2在lookup3.c
var Jenkins = {
rot: function(x,k) {
return (x<<k) | (x>>>(32-k));
},
mix: function(a,b,c) {
a = (a - c) | 0; a ^= Jenkins.rot(c, 4); c = (c + b) | 0;
b = (b - a) | 0; b ^= Jenkins.rot(a, 6); a = (a + c) | 0;
c = (c - b) | 0; c ^= Jenkins.rot(b, 8); b = (b + a) | 0;
a = (a - c) | 0; a ^= Jenkins.rot(c,16); c = (c + b) | 0;
b = (b - a) | 0; b ^= Jenkins.rot(a,19); a = (a + c) | 0;
c = (c - b) | 0; c ^= Jenkins.rot(b, 4); b = (b + a) | 0;
return {a : a, b : b, c : c};
},
final: function(a,b,c) {
c ^= b; c -= Jenkins.rot(b,14) | 0;
a ^= c; a -= Jenkins.rot(c,11) | 0;
b ^= a; b -= Jenkins.rot(a,25) | 0;
c ^= b; c -= Jenkins.rot(b,16) | 0;
a ^= c; a -= Jenkins.rot(c,4) | 0;
b ^= a; b -= Jenkins.rot(a,14) | 0;
c ^= b; c -= Jenkins.rot(b,24) | 0;
return {a : a, b : b, c : c};
},
hashlittle2: function(k, initval, initval2) {
var length = k.length;
a = b = c = 0xdeadbeef + length + initval;
c += initval2;
offset = 0;
while (length > 12) {
a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); a = a>>>0;
b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); b = b>>>0;
c += (k.charCodeAt(offset+8) + (k.charCodeAt(offset+9)<<8) + (k.charCodeAt(offset+10)<<16) + (k.charCodeAt(offset+11)<<24)); c = c>>>0;
o = Jenkins.mix(a,b,c);
a = o.a; b = o.b; c = o.c;
length -= 12;
offset += 12;
}
switch(length) {
case 12: c += (k.charCodeAt(offset+8) + (k.charCodeAt(offset+9)<<8) + (k.charCodeAt(offset+10)<<16) + (k.charCodeAt(offset+11)<<24)); b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 11: c += (k.charCodeAt(offset+8) + (k.charCodeAt(offset+9)<<8) + (k.charCodeAt(offset+10)<<16)); b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 10: c += (k.charCodeAt(offset+8) + (k.charCodeAt(offset+9)<<8)); b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 9: c += (k.charCodeAt(offset+8)); b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 8: b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16) + (k.charCodeAt(offset+7)<<24)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 7: b += (k.charCodeAt(offset+4) + (k.charCodeAt(offset+5)<<8) + (k.charCodeAt(offset+6)<<16)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 6: b += ((k.charCodeAt(offset+5)<<8) + k.charCodeAt(offset+4)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 5: b += (k.charCodeAt(offset+4)); a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 4: a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16) + (k.charCodeAt(offset+3)<<24)); break;
case 3: a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8) + (k.charCodeAt(offset+2)<<16)); break;
case 2: a += (k.charCodeAt(offset+0) + (k.charCodeAt(offset+1)<<8)); break;
case 1: a += (k.charCodeAt(offset+0)); break;
case 0: return {b : b, c : c};
}
o = Jenkins.final(a,b,c);
a = o.a; b = o.b; c = o.c;
return {b : b>>>0, c : c>>>0};
}
}
这里有一个JavaScript端口,我做了lookup3.c
个人项目,在JavaScript中实现了Bloom filter。我不能确定它是否会对C代码产生相同的结果。
不直接转换成JavaScript的主要事情之一是指针算术在指向键输入的指针上执行。在下面的代码中查找offset
这个词,看看我是如何处理这个问题的。
如果您希望输出如同整数未经签名,则可以使用returnValue >>> 0
。
var BloomFilter = {
// Convert a JavaScript string into an array of 32-bit words.
// This preserves the UTF-16 encoding, padding with the null character if necessary.
stringToWords: function(s) {
var b = [];
if(s.length & 1) {
s += "\u0000";
}
for (var i = 0; i < s.length; i += 2) {
b.push((s.charCodeAt(i) << 16) | (s.charCodeAt(i + 1)));
}
return b;
},
// Hash an array of multiple 32-bit words to a single word.
// Adapted from "lookup3.c, by Bob Jenkins, May 2006, Public Domain."
// as retrieved 2010-07-03 from http://burtleburtle.net/bob/c/lookup3.c
hashWord: function(k, initval) {
// definition of bitwise rotate function
function rot(x, k) {
return (x << k) | (x >>> (32 - k));
}
// initialization
var a, b, c, length = k.length, offset = 0;
a = b = c = (0xdeadbeef + (length << 2) + initval) | 0;
// handle most of the key
while(length > 3) {
a = (a + k[offset]) | 0;
b = (b + k[offset + 1]) | 0;
c = (c + k[offset + 2]) | 0;
// mixing function
a = (a - c) | 0; a ^= rot(c, 4); c = (c + b) | 0;
b = (b - a) | 0; b ^= rot(a, 6); a = (a + c) | 0;
c = (c - b) | 0; c ^= rot(b, 8); b = (b + a) | 0;
a = (a - c) | 0; a ^= rot(c,16); c = (c + b) | 0;
b = (b - a) | 0; b ^= rot(a,19); a = (a + c) | 0;
c = (c - b) | 0; c ^= rot(b, 4); b = (b + a) | 0;
length -= 3;
offset += 3;
}
// handle the final words if left over; fall-through is intended
switch(length) {
case 3: c = (c + k[offset + 2]) | 0;
case 2: b = (b + k[offset + 1]) | 0;
case 1: a = (a + k[offset]) | 0;
// final mixing
c ^= b; c = (c - rot(b,14)) | 0;
a ^= c; a = (a - rot(c,11)) | 0;
b ^= a; b = (b - rot(a,25)) | 0;
c ^= b; c = (c - rot(b,16)) | 0;
a ^= c; a = (a - rot(c, 4)) | 0;
b ^= a; b = (b - rot(a,14)) | 0;
c ^= b; c = (c - rot(b,24)) | 0;
case 0: break; // nothing left to do
}
// return the result
return c;
},
// Hash a string by converting to UTF-16 before using the lookup3 algorithm.
hashString: function(s) {
return BloomFilter.hashWord(BloomFilter.stringToWords(s), 0);
}
}
看起来有不同的输出比lookup3.c,但它比其他两个版本更快_much_很慢(包括OP),出了什么问题? – bryc 2018-02-10 03:51:54
只需几修改,C code on Wikipedia将在JavaScript中完美工作。只是摆脱数据类型,并使用key.length
,而不是必须通过的长度。
但是,这是与“我的哈希”詹金的礼物:http://www.burtleburtle不同的*(并且更简单)。 net/bob/hash/doobs.html,其中包含混合阶段和其他区别。 (一次一个散列只是上述链接中的讨论散列之一。) – 2010-11-20 19:32:55
@pst:那么,这仍然只是一堆轮班和其他算术运算符,所以大部分将在JavaScript中保持不变。 – casablanca 2010-11-20 19:35:36
@casablanca只要指出:-)然而,我认为差异可能在于如何处理溢出 - 这必须手动*添加到JavaScript逻辑中。 “我的哈希”假定一个无符号的4字节,我相信一个2的补码。 – 2010-11-20 19:36:08
来吧,它会很有趣。此外,如果您有测试有效数据的现有来源...:p – 2010-11-20 19:21:25