[javascript] Javascript의 문자열에서 해시 생성

참고 : 최상의 32 비트 해시라도 조만간 충돌 이 발생합니다.

해시 충돌 probablility은 다음과 같이 계산 될 수
로 aproximated,

( 여기 참조 ). 이는 직감이 제안한 것보다 높을 수 있습니다
. 32 비트 해시 및 k = 10,000 항목을 가정하면 확률 1.2 %로 충돌이 발생합니다. 77,163 개의 샘플에서 확률은 50 %가됩니다! ( 계산기 ).
하단에 해결 방법을 제안합니다.

이 질문에 대한 답변으로
고유성과 속도에 가장 적합한 해싱 알고리즘은 무엇입니까? Ian Boyd는 심층 분석 결과를 올렸다 . 한마디로 (내가 해석 한대로), 그는 Murmur가 최고라는 결론에 도달 한 다음 FNV-1a를 따릅니다.
esmiralha가 제안한 Java의 String.hashCode () 알고리즘은 DJB2의 변형 인 것 같습니다.

• FNV-1a는 DJB2보다 더 나은 분포를 가지고 있지만 느립니다.
• DJB2는 FNV-1a보다 빠르지 만 더 많은 충돌을 일으키는 경향이 있습니다.
• MurmurHash3는 DJB2 및 FNV-1a보다 낫고 빠릅니다 (그러나 최적화 된 구현에는 FNV 및 DJB2보다 더 많은 코드 줄이 필요함)

여기에 큰 입력 문자열 일부 벤치 마크 : http://jsperf.com/32-bit-hash
때 짧은 입력 문자열을 해시, DJ2B 및 FNV-1A에 비해 잡음의 성능 방울 : http://jsperf.com/32- 비트 해시 / 3

따라서 일반적으로 murmur3을 권장합니다.
JavaScript 구현에 대해서는 여기를 참조하십시오 :
https://github.com/garycourt/murmurhash-js

입력 문자열이 짧고 분배 품질보다 성능이 더 중요한 경우, esmiralha의 승인 된 답변에서 제안한대로 DJB2를 사용하십시오.

품질과 작은 코드 크기가 속도보다 중요한 경우 FNV-1a 구현 ( 이 코드 기반 )을 사용합니다.

/**
 * Calculate a 32 bit FNV-1a hash
 * Found here: https://gist.github.com/vaiorabbit/5657561
 * Ref.: http://isthe.com/chongo/tech/comp/fnv/
 *
 * @param {string} str the input value
 * @param {boolean} [asString=false] set to true to return the hash value as 
 *     8-digit hex string instead of an integer
 * @param {integer} [seed] optionally pass the hash of the previous chunk
 * @returns {integer | string}
 */
function hashFnv32a(str, asString, seed) {
    /*jshint bitwise:false */
    var i, l,
        hval = (seed === undefined) ? 0x811c9dc5 : seed;

    for (i = 0, l = str.length; i < l; i++) {
        hval ^= str.charCodeAt(i);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }
    if( asString ){
        // Convert to 8 digit hex string
        return ("0000000" + (hval >>> 0).toString(16)).substr(-8);
    }
    return hval >>> 0;
}

충돌 확률 향상

여기 에 설명 된 대로이 트릭을 사용하여 해시 비트 크기를 확장 할 수 있습니다.

function hash64(str) {
    var h1 = hash32(str);  // returns 32 bit (as 8 byte hex string)
    return h1 + hash32(h1 + str);  // 64 bit (as 16 byte hex string)
}

조심해서 사용하고 너무 많이 기대하지 마십시오.

답변

function hashCode(str) {
  return str.split('').reduce((prevHash, currVal) =>
    (((prevHash << 5) - prevHash) + currVal.charCodeAt(0))|0, 0);
}

// Test
console.log("hashCode(\"Hello!\"): ", hashCode('Hello!'));

const hashCode = s => s.split('').reduce((a,b) => (((a << 5) - a) + b.charCodeAt(0))|0, 0)

// test
console.log(hashCode('Hello!'))

hashCode=s=>{for(var i=0,h;i<s.length;i++)h=Math.imul(31,h)+s.charCodeAt(i)|0;return h}

const cyrb53 = function(str, seed = 0) {
    let h1 = 0xdeadbeef ^ seed, h2 = 0x41c6ce57 ^ seed;
    for (let i = 0, ch; i < str.length; i++) {
        ch = str.charCodeAt(i);
        h1 = Math.imul(h1 ^ ch, 2654435761);
        h2 = Math.imul(h2 ^ ch, 1597334677);
    }
    h1 = Math.imul(h1 ^ h1>>>16, 2246822507) ^ Math.imul(h2 ^ h2>>>13, 3266489909);
    h2 = Math.imul(h2 ^ h2>>>16, 2246822507) ^ Math.imul(h1 ^ h1>>>13, 3266489909);
    return 4294967296 * (2097151 & h2) + (h1>>>0);
};

0xc2ba782c97901 = cyrb53("a")
0xeda5bc254d2bf = cyrb53("b")
0xe64cc3b748385 = cyrb53("revenge")
0xd85148d13f93a = cyrb53("revenue")

0xee5e6598ccd5c = cyrb53("revenue", 1)
0x72e2831253862 = cyrb53("revenue", 2)
0x0de31708e6ab7 = cyrb53("revenue", 3)

return (h2>>>0).toString(16).padStart(8,0)+(h1>>>0).toString(16).padStart(8,0);
// or
return [h2>>>0, h1>>>0];

TSH=s=>{for(var i=0,h=9;i<s.length;)h=Math.imul(h^s.charCodeAt(i++),9**9);return h^h>>>9}

/**
 * @see http://stackoverflow.com/q/7616461/940217
 * @return {number}
 */
String.prototype.hashCode = function(){
    if (Array.prototype.reduce){
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);
    }
    var hash = 0;
    if (this.length === 0) return hash;
    for (var i = 0; i < this.length; i++) {
        var character  = this.charCodeAt(i);
        hash  = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

var hash = "some string to be hashed".hashCode();

String.prototype.hashCode = function() {
    var hash = 0, i = 0, len = this.length;
    while ( i < len ) {
        hash  = ((hash << 5) - hash + this.charCodeAt(i++)) << 0;
    }
    return hash;
};

String.prototype.hashcode = function() {
    return (this.hashCode() + 2147483647) + 1;
};

public static long hashcode(Object obj) {
    return ((long) obj.hashCode()) + Integer.MAX_VALUE + 1l;
}