2017-12-31 64 views
1

Nach einem Blick auf einen einfachen hash table implementation in JavaScript gehasht werden, wird der Schlüsselindex wie folgt berechnet:Wie hashtable sicher Objektschlüssel macht in einen eindeutigen Index in JavaScript

function index(str, max) { 
    var hash = 0; 
    for (var i = 0; i < str.length; i++) { 
    var letter = str[i]; 
    hash = (hash << 5) + letter.charCodeAt(0); 
    hash = (hash & hash) % max; 
    } 
    return hash; 
} 

So im Fall von v8 ich frage mich, , wie es eine ähnliche Funktion verwendet, aber dafür sorgt, dass der Index für das Objekt eindeutig ist. Also, wenn Sie dies tun:

{ a: 'foo', b: 'bar' } 

Dann wird es so etwas wie:

var i = index('a', 100000) 
// 97 
var j = index('b', 100000) 
// 98 

Aber wenn Sie 100 der oder 1000 oder mehr Tasten auf einem Objekt, wie es scheint, könnte es Kollisionen zu sein.

Sie fragen sich, wie eine Hashtable garantiert, dass sie einzigartig sind und v8 als praktisches Beispiel verwenden.

+1

https://stackoverflow.com/questions/9282869/are-there-limits-to-the-number-of-properties-in-a-javascript- Objekt –

+0

Nein, jede Hashtabellenimplementierung benötigt eine Möglichkeit, mit Kollisionen umzugehen. Wenn Hashes garantiert einmalig wären, hätten sie keinen Größenvorteil. – Bergi

+0

Sie können die Größe einer Zeichenkettenmenge nicht vorhersagen, daher kommt es irgendwann zu Kollisionen. Kollisionen können jedoch mit Sammlungen so einfach wie Warteschlangen behandelt werden. –

Antwort

3

V8 Entwickler hier. Hashes von Strings sind nicht eindeutig (das ist der Sinn der Verwendung einer Hash-Funktion); V8 verwendet quadratisches Antasten, um mit Kollisionen umzugehen (siehe source). Sie können mehr über verschiedene Strategien bei https://en.wikipedia.org/wiki/Hash_table#Collision_resolution lesen.

Auch hash = (hash & hash) % max; ist ziemlich dumm ;-)

Verwandte Themen