2

一部の言語では、文字列だけでなくあらゆるものをキーとして使用できるハッシュ テーブルを実装しています。JavaScript では、文字列と数値に制限されています。この種の実装のルックアップはまだ O(1) ですか? JavaScript での実装はありますか?

4

2 に答える 2

14

この件については明らかに多くの誤解があります。JavaScript では、オブジェクトのキーは実際には文字列のみです( §8.10を参照)。 オブジェクト キーとして使用されるもの(数字を含む) はすべて文字列に変換されます。したがって、obj[1]とobj["1"] は等価です。

内部的には、多くの JS 実装は、オブジェクト プロパティの迅速な検索を可能にするために、ある種のハッシュ テーブルを使用します。V8 は実際に、単一の CPU 命令でルックアップを実行できる隠し C++ クラスを生成します。いずれにせよ、オブジェクト プロパティへのアクセスは高速で O(1) に近いと考えて間違いありません。

すべてのオブジェクト プロパティ キーが文字列に変換されるため、文字列に変換されるものだけをキーとして使用できます。数値は自然に文字列に変換されるため、正常に機能します。ブール値についても同じです。インスタンスは一意の文字列に変換されるため、日付も機能Dateします (ただし、注意が必要な特殊なケースがあります)。

ただし、オブジェクトは意味のある文字列に変換されません。例えば：

var o = {};
o[{a:1}]='some value';

実際には次のようになります。

o = { '[object Object]': 'some value' }

文字列変換規則のため。すべてのオブジェクトは に変換されるため[object Object]、多くのオブジェクトをキーとして別のオブジェクトに追加すると、プロパティが 1 つだけのオブジェクトになります。

もちろん、オブジェクトをキーとして使用することも可能です。のデフォルトの実装をオーバーライドするだけで済みますtoString— 実際には、独自のハッシュ アルゴリズムを作成します。例えば、

function ComplexKey(a,b) {
    this.a = a;
    this.b = b;
}

ComplexKey.prototype.toString = function() {
    return this.a + ':' + this.b;
}

var o = {};
o[new ComplexKey(1,2)] = 'x';
o[new ComplexKey(3,4)] = 'y';

結果:

o = {
    '1:2': 'x',
    '3:4': 'y'
}
于 2012-09-02T19:58:25.907 に答える
6

JavaScript には「ハッシュテーブル」がありません。

キーと値のペアのコレクションである辞書があり、キーは一意でなければならないという制限があります。違いは、Dictionary の実装はハッシュを意味しないことですが、ハッシュ テーブルはパフォーマンス上の理由から実装によって内部的に使用される可能性があります。

JavaScriptのすべてのオブジェクトstringは辞書として機能します (これには、やなどのプリミティブ型は含まれませnumberん)。通常、空のオブジェクトは汎用の「ハッシュテーブル」に使用されます。

var o = {};
o[propExpression] = valueExpression;

ただし、重要なことは次のとおりです。すべてのプロパティ/キー値は最初に string に変換されます。

したがって、以下は同一です。

o[true] = 1
o["true"] = 1

ECMAScript に従うのは少し混乱しますが、プロパティ名がすべて文字列であることを「知る」ための重要な部分は、Property Descriptorsにあります。

プロパティ識別子タイプは、プロパティ名をプロパティ記述子に関連付けるために使用されます。プロパティ識別子型の値は、(名前、記述子) の形式のペアです。ここで、名前は文字列で、記述子はプロパティ記述子の値です。

于 2012-09-02T19:21:21.917 に答える