JSのほとんどのエージェントセット構造

Question

私は一意の文字列のリストを持たせたいので、毎回新しい文字列を取得する必要があります。リストに追加する必要があります。リスト。これは不適格と思われる。

ただし、ハッシュ構造を使用してアイテムをキーとして保存すると、単純な配列よりもパフォーマンスを向上させる方法はありますか？

私は、JavaScriptで最もパフォーマンスの高いセットデータ構造が何であるか考えていると思います。

Answer 1

はい、セットを使用すると、既存の値（配列のO（n）に対してO（1））をチェックするよりもはるかに高速になります。最近のブラウザで

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

（クローム38+、IE11 +）Set型が定義され、それがここに文書化されていますhttps://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

そうでない場合は、JavaScriptで、Object値（ECMAScriptの中の基本的なタイプ）が内部的に実装されていますハッシュテーブルとして使用することができます。したがって、最も遅い概念の "HashSet"構造は、無視された値型のハッシュテーブルの一般化として存在します。ここで

は（Setが利用できなかった場合）、私はそれを行うだろう方法は次のとおりです。

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"));