Skip to content

Instantly share code, notes, and snippets.

@adnils
Created January 30, 2014 10:03
Show Gist options
  • Save adnils/8705618 to your computer and use it in GitHub Desktop.
Save adnils/8705618 to your computer and use it in GitHub Desktop.
murmur hash
function doHash(str, seed) {
var m = 0x5bd1e995;
var r = 24;
var h = seed ^ str.length;
var length = str.length;
var currentIndex = 0;
while (length >= 4) {
var k = UInt32(str, currentIndex);
k = Umul32(k, m);
k ^= k >>> r;
k = Umul32(k, m);
h = Umul32(h, m);
h ^= k;
currentIndex += 4;
length -= 4;
}
switch (length) {
case 3:
h ^= UInt16(str, currentIndex);
h ^= str.charCodeAt(currentIndex + 2) << 16;
h = Umul32(h, m);
break;
case 2:
h ^= UInt16(str, currentIndex);
h = Umul32(h, m);
break;
case 1:
h ^= str.charCodeAt(currentIndex);
h = Umul32(h, m);
break;
}
h ^= h >>> 13;
h = Umul32(h, m);
h ^= h >>> 15;
return h >>> 0;
}
function UInt32(str, pos) {
return (str.charCodeAt(pos++)) +
(str.charCodeAt(pos++) << 8) +
(str.charCodeAt(pos++) << 16) +
(str.charCodeAt(pos) << 24);
}
function UInt16(str, pos) {
return (str.charCodeAt(pos++)) +
(str.charCodeAt(pos++) << 8);
}
function Umul32(n, m) {
n = n | 0;
m = m | 0;
var nlo = n & 0xffff;
var nhi = n >>> 16;
var res = ((nlo * m) + (((nhi * m) & 0xffff) << 16)) | 0;
return res;
}
function getBucket(str, buckets) {
var hash = doHash(str, str.length);
var bucket = hash % buckets;
return bucket;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment