☰

JavaScript hashmap equivalent Ask Question

tag-icon • tag-icon javascript data-structures language-features hashmap
JavaScript hashmap equivalent Ask Question

As made clear in update 3 on this answer, this notation:

var hash = {};
hash[X]

does not actually hash the object X; it actually just converts X to a string (via .toString() if it's an object, or some other built-in conversions for various primitive types) and then looks that string up, without hashing it, in "hash". Object equality is also not checked - if two different objects have the same string conversion, they will just overwrite each other.

Given this - are there any efficient implementations of hashmaps in JavaScript?

(For example, the second Google result of javascript hashmap yields an implementation which is O(n) for any operation. Various other results ignore the fact that different objects with equivalent string representations overwrite each other.

ベストアンサー1

Hash your objects yourself manually, and use the resulting strings as keys for a regular JavaScript dictionary. After all, you are in the best position to know what makes your objects unique. That's what I do.

Example:

var key = function(obj){
  // Some unique object-dependent key
  return obj.totallyUniqueEmployeeIdKey; // Just an example
};

var dict = {};

dict[key(obj1)] = obj1;
dict[key(obj2)] = obj2;

This way you can control indexing done by JavaScript without heavy lifting of memory allocation, and overflow handling.

Of course, if you truly want the "industrial-grade solution", you can build a class parameterized by the key function, and with all the necessary API of the container, but … we use JavaScript, and trying to be simple and lightweight, so this functional solution is simple and fast.

The key function can be as simple as selecting right attributes of the object, e.g., a key, or a set of keys, which are already unique, a combination of keys, which are unique together, or as complex as using some cryptographic hashes like in DojoX encoding, or DojoX UUID. While the latter solutions may produce unique keys, personally I try to avoid them at all costs, especially, if I know what makes my objects unique.

Update in 2014: Answered back in 2008 this simple solution still requires more explanations. Let me clarify the idea in a Q&A form.

Your solution doesn't have a real hash. Where is it???

JavaScript is a high-level language. Its basic primitive (Object) includes a hash table to keep properties. This hash table is usually written in a low-level language for efficiency. Using a simple object with string keys we use an efficiently implemented hash table without any efforts on our part.

How do you know they use a hash?

There are three major ways to keep a collection of objects addressable by a key:

  • Unordered. In this case to retrieve an object by its key we have to go over all keys stopping when we find it. On average it will take n/2 comparisons.
  • Ordered.
    • Example #1: a sorted array — doing a binary search we will find our key after ~log2(n) comparisons on average. Much better.
    • Example #2: a tree. Again it'll be ~log(n) attempts.
  • Hash table. On average, it requires a constant time. Compare: O(n) vs. O(log n) vs. O(1). Boom.

明らかに、JavaScript オブジェクトは一般的なケースを処理するために何らかの形式でハッシュ テーブルを使用します。

ブラウザベンダーは本当にハッシュテーブルを使用しているのでしょうか?

本当に。

衝突は処理されますか?

はい。上記を参照してください。不等な文字列の衝突を発見した場合は、遠慮なくベンダーにバグを報告してください。

それであなたのアイデアは何ですか？

オブジェクトをハッシュ化する場合は、そのオブジェクトを一意にする要素を見つけて、それをキーとして使用します。実際のハッシュを計算したり、ハッシュ テーブルをエミュレートしたりしないでください。これは、基盤となる JavaScript オブジェクトによって既に効率的に処理されています。

このキーを JavaScript で使用すると、Objectデフォルトのプロパティとの衝突を回避しながら、組み込みのハッシュ テーブルを活用できます。

始めるための例:

  • オブジェクトに一意のユーザー名が含まれている場合は、それをキーとして使用します。
  • 固有の顧客番号が含まれている場合は、それをキーとして使用します。
    • 米国政府発行の固有の番号が含まれている場合SSN（社会保障番号）、またはパスポート番号であり、システムで重複が許可されていない場合は、それをキーとして使用します。
  • フィールドの組み合わせが一意である場合は、それをキーとして使用します。
    • 米国の州の略語 + 運転免許証番号は優れたキーになります。
    • 国名略語 + パスポート番号も優れたキーです。
  • フィールドまたはオブジェクト全体の一部の関数は一意の値を返すことができるので、それをキーとして使用します。

あなたの提案に従って、ユーザー名を使用してすべてのオブジェクトをキャッシュしました。しかし、ある賢い人が「toString」という組み込みプロパティを名付けました。どうすればいいでしょうか?

当然ですが、結果のキーがラテン文字のみで構成される可能性が少しでもある場合は、何らかの対処をする必要があります。たとえば、デフォルトのプロパティと衝突しないように、先頭または末尾に任意の非ラテン Unicode 文字を追加します: "#toString"、"#MarySmith"。複合キーを使用する場合は、非ラテン文字の区切り文字を使用してキー コンポーネントを区切ります: "name,city,state"。

一般的に、ここでは創造性を発揮し、与えられた制限（一意性、デフォルトのプロパティとの潜在的な衝突）の範囲内で最も簡単なキーを選択する必要があります。

注: 一意のキーは定義上は衝突しませんが、潜在的なハッシュの衝突は基礎となる によって処理されますObject。

なぜ産業用ソリューションが気に入らないのですか?

私の意見では、最良のコードとは、まったくコードがないことです。エラーがなく、メンテナンスが不要で、理解しやすく、瞬時に実行されます。私が見た「JavaScript のハッシュ テーブル」はすべて 100 行を超えるコードで、複数のオブジェクトが含まれていました。以下と比較してくださいdict[key] = value。

もう 1 つのポイント: すでに実装されているものを実装するために JavaScript とまったく同じ原始オブジェクトを使用して、低レベル言語で記述された原始オブジェクトのパフォーマンスを上回ることは可能でしょうか?

キーなしでオブジェクトをハッシュしたいです。

幸運なことに:ECMAスクリプト6（2015年6月リリース）は定義します地図そしてセット。

定義から判断すると、オブジェクトのアドレスをキーとして使用できるため、人工的なキーがなくてもオブジェクトを即座に区別できます。一方、2 つの異なるが同一のオブジェクトは、別個のものとしてマップされます。

比較の内訳翻訳:

オブジェクトは、キーに値を設定したり、それらの値を取得したり、キーを削除したり、キーに何かが格納されているかどうかを検出したりできる点でマップに似ています。このため (および組み込みの代替手段がなかったため)、オブジェクトは歴史的にマップとして使用されてきましたが、重要な違いがあり、特定のケースではマップを使用する方が望ましい場合があります。

  • オブジェクトのキーは文字列とシンボルですが、マップの場合は関数、オブジェクト、任意のプリミティブを含む任意の値にすることができます。
  • Map 内のキーは順序付けられていますが、オブジェクトに追加されたキーは順序付けられていません。したがって、反復処理を実行すると、Map オブジェクトは挿入順にキーを返します。
  • Map のサイズは size プロパティを使用して簡単に取得できますが、Object 内のプロパティの数は手動で決定する必要があります。
  • Map は反復可能であり、直接反復できますが、Object を反復するには、何らかの方法でキーを取得し、それを反復する必要があります。
  • オブジェクトにはプロトタイプがあるため、マップ内にデフォルトのキーがあり、注意しないとキーと衝突する可能性があります。ES5 では、map = Object.create(null) を使用してこれを回避できますが、これはほとんど行われません。
  • キーペアの頻繁な追加と削除を伴うシナリオでは、マップのパフォーマンスが向上する可能性があります。

おすすめ記事