Most peformant set Struktur in JS

Question

Ich möchte eine Liste von Strings haben, die eindeutig ist und so jedes Mal, wenn ich eine neue Zeichenfolge, die ich auf die Liste schieben sollte ich überprüfen, ob die Liste das Element enthält, bevor Sie es auf der Liste. Dies scheint unperformant zu sein.

Wenn ich jedoch eine Hash-Struktur verwenden und die Elemente als Schlüssel speichern, gibt es eine Möglichkeit, dies leistungsfähiger als ein einfaches Array zu machen?

Ich denke ich frage mich einfach, was die performanteste Datenstruktur in JavaScript gibt.

Answer 1

Ja, die Verwendung eines Sets ist viel schneller als die Suche nach einem vorhandenen Wert (O (1) für Set vs. O (n) für ein Array).

var s = Set(); 

s.add(1); // s is (1) 
s.add(2); 
s.add(3); 
s.add(1) 
s.add(1) 

// s is now (1, 2, 3) 

Answer 2

In modernen Browsern (Chrome 38+, IE11 +) der Set Typ definiert ist, wird es hier dokumentiert: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Ansonsten in JavaScript, Object Werte (ein Grundtyp in ECMAScript) intern umgesetzt werden als Hashtabellen - so würde die schnellste konzeptionelle "HashSet" -Struktur als eine Verallgemeinerung einer Hashtabelle mit einem nicht berücksichtigten Werttyp existieren.

Hier ist, wie ich es tun würde (wenn Set nicht verfügbar ist):

function StringSet() { 
    this.values = {}; 
    this.add = function(value) { 
     value = value.toUpperCase(); // use UpperCase for string normalization because of how casing rules work in different languages, especially Turkish 
     this.values[ value ] = true; // use bool values as stubs 
    }; 
    this.contains = function(value) { 
     value = value.toUpperCase(); 
     return value in this.values; // JavaScript has a fast `in` operator which runs in `O(1)` time 
    } 
} 

var foo = new StringSet(); 
foo.add("bar"); 
assert(foo.contains("bar"));