ハッシュテーブルは、アイテムを格納するための構造体です。個々のアイテムは、それぞれを識別するためのキーを持ちます。ハッシュテーブルからアイテムを検索・追加・削除するためにはキーを使います。ハッシュテーブルは配列に似ていますが、以下に示すような大きな違いがあります。
| 配列 | ハッシュテーブル | |
|---|---|---|
| キー: | 整数。配列ではキーとして常に整数が利用され、またキーは連続している必要があります。 | 任意の型。文字列、整数、 XPCOM インターフェースのポインタ、 IID を含む、ほとんどすべてのデータ型がキーとして利用できます。また、キーは連続している必要はありません（たとえば 1, 5, 3000 を利用できます）。 |
| 検索にかかる時間: | O(1)。検索時間は定数時間です。 | O(1)。検索時間は一般に定数時間ですが、配列よりも定数時間だけ長くかかる可能性があります。 |
| ソート: | ソートされています。アイテムはソートされて保管されます。また、ソートされた順序で列挙されます。 | ソートされていません。アイテムはソートされずに保管されます。また、ソートされずに列挙されます。 |
| 追加・削除: | O(n)。大きな配列へのアイテムの追加・削除は時間がかかる可能性があります。 | O(1)。ハッシュテーブルへのアイテムの追加・削除は高速に行われます。 |
| 余計に消費される領域: | なし。配列は中が詰まった構造体であり、アイテムのサイズ以上に消費される領域はありません。 | あり。ハッシュテーブルは中が詰まった構造体ではありません。実装によりますが、大量のメモリが無駄に消費される可能性があります。 |
実装としては、ハッシュテーブルはキーを渡されるとそのキーに数学的なハッシュ関数を適用してキーを乱数化します。以後、キーのハッシュ値がアイテムの場所の検索に利用されます。優れたハッシュテーブルの実装は、メモリが余計に必要になったとき、または多すぎる量のメモリが割り当てられているとき、自動的にハッシュテーブルのサイズを変更します。
ハッシュテーブルは以下のような場合に有用です。
以下のような場合、ハッシュテーブルは利用されるべきではありません。
このような状況では、配列、連結リスト、様々な木構造などが効果的です。
Mozilla ではいくつかのハッシュテーブルの実装を用意しています。これらはテスト・調整されており、また実装にかかわる内部の複雑さが隠蔽されています。
PLDHash - C の低レベルAPI。キーとデータを単独の大きな構造体としてメモリ上に格納します。ヒープ領域を効果的に利用します。利用者は「エントリークラス」（訳注：保管するアイテムを表すクラス・構造体）を宣言する必要があります。 また、アイテムへのポインタを別に持っておくことはできません。PLHashTable - C の低レベルAPI。エントリークラスへのポインタは変化しません。大きな構造体を利用する場合は効果的です。細かなヒープ領域を大量に確保する結果、メモリを無駄に使用することがよくあります。nsTHashtable - 低レベル C++ による PLDHash のラッパです。コールバック関数を生成し、ほとんどのキャストを自動的に行います。利用者はキーとデータを保持するエントリークラスを自分で用意します。nsDataHashtable/nsInterfaceHashtable/nsClassHashtable - 高レベル C++ による PLDHash のラッパです。単純なキー型・データ型を利用する一般的な使い方をする場合は簡単に利用できます。 利用者はエントリークラスを宣言・使用する必要がありません。 nsDataHashtable 型は PRUint32 のようなスカラー値を扱います。 nsInterfaceHashtable 型はインタフェースを、 nsClassHashtable 型はクラスへのポインタ型を扱います。| キーの型: | ||||||
|---|---|---|---|---|---|---|
| integer | String/CString | nsID | nsISupports* | Complex | ||
| データ型: | None (Hash Set) | nsInt32HashSet |
ns(C)StringHashSet |
nsTHashtable<...> |
||
| Simple (PRUint32) | nsDataHashtable |
nsTHashtable<...> |
||||
<nsUint32HashKey, |
<ns(C)StringHashKey, |
<nsIDHashKey, |
<nsISupportsHashKey, |
|||
| Interface (nsISupports) | nsInterfaceHashtable |
|||||
<nsUint32HashKey, |
<ns(C)StringHashKey, |
<nsIDHashKey, |
<nsISupportsHashKey, |
|||
| Class (nsString*) | nsClassHashtable |
|||||
<nsUint32HashKey, |
<ns(C)StringHashKey, |
<nsIDHashKey, |
<nsISupportsHashKey, |
|||
| Complex (structures, etc.) |
nsTHashtable<...> |
|||||
PLDHash と JSDHash は同じものです。 PLDHash は XPCOM ライブラリから、 JSDHash は JavaScript のライブラリからリンクされています。 JSDHash は SpiderMonkey の JavaScript エンジンで広く利用されています。
PLDHash は C で書かれた低レベルな実装です。非常に柔軟ですが、 PLDHash を理解し、利用するためには多少の時間がかかります。基本的なガイドはここにありますが、 PLDHash を利用するつもりであれば、 xpcom/glue/pldhash.h のほとんどを読む必要があります。 C++ のコードから利用する場合、キャストにかかわるエラーの可能性を容易に避けられるため、 C++ によるラッパ（後述）の方がずっと易しく、また安全です。
利用者はまず <code>PLDHashEntryHdr</code> から派生するエントリー構造体を宣言する必要があります。エントリー構造体はハッシュテーブルに格納するデータ（任意のポインタ、固定長のデータ型）を持ちます。ノート: double-hashing 実装のため、ハッシュテーブルの内容が変更された際、エントリーはメモリ上で移動される可能性があります。エントリーへのポインタを定数としたい場合は、 PLHashTable が代わりに利用できます。
また、利用者は <code>PLDHashTableOps</code> 構造体を初期化しなくてはいけません。この構造体は C++ の vtable と似たようなもので、エントリーを初期化・比較・検索するための適切なユーザ定義関数へのポインタを提供します。 PLDHash はキーの型が何であるかを知らないため、キーを扱う全ての関数は const void* で宣言されなければなりません。また、利用者のコードはこれらのポインタを適切な型にキャストする必要があります。
PLDHashTables は、スタック・ヒープのどちらにも配置することができます。:
PL_DHashTableInit で初期化され、 PL_DHashTableFinish で破棄される必要があります。PL_NewDHashTable, PL_DHashTableDestroy でテーブルの割り当て・削除を行ってください。PLHashTable は NSPR の一部です。ヘッダファイルは nsprpub/lib/ds/plhash.hPLHashTable はヒープに多数の領域を割り当てようとするため、一般的には PLDHash の方が PLHashTable よりも優れています。
PLDHash よりも PLHashTable の方が好ましい状況は以下の2つです。
PLDHash は大きな構造体を効率的に扱えません。nsTHashtable は PLDHash をラップする C++ のテンプレートで、 PLDHash の複雑な部分（コールバック関数、構造体など）を隠蔽します。 xpcom/glue/nsTHashtable.h に目を通しておいてください。
nsTHashtable を利用するためには、利用者は pre-defined format にある通りにエントリークラスを宣言する必要があります。このエントリークラスは、ハッシュテーブルに格納するキーとデータを保持します（上記の PLDHash と同様です）。また、クラスの中でキーを処理する関数も宣言します。ほとんどの場合、エントリークラスは完全にインラインで書くことができます。エントリークラスの例については xpcom/glue/nsHashKeys.h を参照してください。
テンプレートのパラメータはエントリークラスです。テーブルを正しく初期化するためには Init() を利用しなくてはいけません。また現在のところ、テーブルの内容を変更するためには PutEntry/GetEntry/RemoveEntry 関数を利用してください。 EnumerateEntries 関数では列挙ができますが、並び順は見かけ上ランダムである（ソートされていない）ことに気をつけてください。
nsTHashtable はスタック、クラスメンバ、ヒープに割り当てることができます。nsTHashtable は本質的にスレッドセーフではありません。マルチスレッドで利用する場合、適切なロック機構を用意する必要があります。nsTHashtable を使用する前に、 nsBaseHashtable とその関連クラスが利用用途に合うかどうか確認してください。エントリークラスを宣言する必要がないため、それらの方がずっと使いやすくなっています。もし単純なキー型・データ型を利用するのであれば、多くの場合こちらの方が良い選択肢です。
これらの C++ テンプレートは、 PLDHash の複雑な部分のほとんどを隠蔽しつつ、ハッシュテーブルを利用するための高レベルなインタフェースを提供します。以下のような機能を持ちます:
nsInterfaceHashtable と nsClassHashtable は自動的にオブジェクトを解放・削除し、メモリリークを防ぎます。nsBaseHashtable は直接利用しません。ここから派生した3つの派生クラスから、保持するデータ型に合わせて利用するクラスを1つ選んでください。 KeyClass は nsHashKeys.h で定義されています。他3つも同様です:
nsDataHashtable<KeyClass, DataType> - DataType は PRUint32 or PRBool のような単純型です。nsInterfaceHashtable<KeyClass, Interface> - Interface は nsISupports, nsIDOMNode のような XPCOM インタフェースです。nsClassHashtable<KeyClass, T> - T は任意の C++ クラスです。ハッシュテーブルはオブジェクトへのポインタを格納します。また、オブジェクトがハッシュテーブルから取り去られた場合、そのオブジェクトを削除します。目を通しておくべき重要なファイルは xpcom/glue/nsBaseHashtable.h と xpcom/glue/nsHashKeys.h です。これらのクラスはスタック、クラスメンバ、ヒープに置くことができます。初期化には Init() 関数を利用してください。このとき、スレッドセーフな排他制御を行うかどうかを決められます。ハッシュテーブルの内容を変更するには Put(), Get(), Remove() 関数を利用してください。
2つの列挙関数が用意されています:
EnumerateRead() は読み取り専用の列挙型を提供します。内容の変更や削除はできません。Enumerate() は読み書きのできる列挙型を提供します。必要に応じて内容の変更・削除ができます。ハッシュセットはキーの存在だけを追跡します。キーとデータとの関連づけは行いません。このような動作は、 nsTHashtable<nsSomeHashKey> を利用することで実現できます。The appropriate entries are GetEntry and PutEntry.
The (obsolete) nsHashtable has a wrapper that exposes an nsISimpleEnumerator on its items. I will add this support to the various nsBaseHashtable classes as well, as needed.
All of the above hashtables need a Hash Function. This function converts the key into a semi-unique integer. The mozilla codebase already contains hash functions for most key types, including narrow and wide strings, pointers, and most binary data:
void* |
cast using NS_PTR_TO_INT32 |
char* string |
nsCRT::HashCode() |
PRUnichar* string |
|
nsAString |
HashString() |
nsACString |
|
nsID& |
nsIDHashKey::HashKey() |
Writing a good hash function is well beyond the scope of this document, and has been discussed extensively in computer-science circles for many years. There are many different types of hash functions. Mozilla has tuned a good general-purpose hash algorithm for strings and nsID.
nsHashtable was a C++ wrapper around PLHashTable, and now wraps PLDHash. The design of the key classes is not optimal, however, and nsHashtable has been deprecated in favor of nsDataHashtable and friends.
nsObjectHashtable is a form of nsHashtable. It has been replaced by nsClassHashtable.
nsSupportsHashtable is a form of nsHashtable. It has been replaced by nsInterfaceHashtable.
nsHashSets has predefined hash sets for common keys, which are trivially easy to use. See xpcom/ds/nsHashSets.h. This functionality has been replaced by nsTHashtable<nsSomeHashKey>.
nsDoubleHashtable is the (obsolete) precursor to nsTHashtable. It uses macros instead of C++ templates.