XPCOM ハッシュテーブル・ガイド

このページは翻訳中です。
翻訳作業に参加する場合は、履歴にある翻訳者と連絡·調整してください。

ハッシュテーブルとは何ですか?

ハッシュテーブルは、アイテムを格納するための構造体です。個々のアイテムは、それぞれを識別するためのキーを持ちます。ハッシュテーブルからアイテムを検索・追加・削除するためにはキーを使います。ハッシュテーブルは配列に似ていますが、以下に示すような大きな違いがあります。

  配列 ハッシュテーブル
キー: 整数。配列ではキーとして常に整数が利用され、またキーは連続している必要があります。 任意の型。文字列、整数、 XPCOM インターフェースのポインタ、 IID を含む、ほとんどすべてのデータ型がキーとして利用できます。また、キーは連続している必要はありません(たとえば 1, 5, 3000 を利用できます)。
検索にかかる時間: O(1)。検索時間は定数時間です。 O(1)。検索時間は一般に定数時間ですが、配列よりも定数時間だけ長くかかる可能性があります。
ソート: ソートされています。アイテムはソートされて保管されます。また、ソートされた順序で列挙されます。 ソートされていません。アイテムはソートされずに保管されます。また、ソートされずに列挙されます。
追加・削除: O(n)。大きな配列へのアイテムの追加・削除は時間がかかる可能性があります。 O(1)。ハッシュテーブルへのアイテムの追加・削除は高速に行われます。
余計に消費される領域: なし。配列は中が詰まった構造体であり、アイテムのサイズ以上に消費される領域はありません。 あり。ハッシュテーブルは中が詰まった構造体ではありません。実装によりますが、大量のメモリが無駄に消費される可能性があります。

実装としては、ハッシュテーブルはキーを渡されるとそのキーに数学的なハッシュ関数を適用してキーを乱数化します。以後、キーのハッシュ値がアイテムの場所の検索に利用されます。優れたハッシュテーブルの実装は、メモリが余計に必要になったとき、または多すぎる量のメモリが割り当てられているとき、自動的にハッシュテーブルのサイズを変更します。

どんなときにハッシュテーブルを使うべきですか?

ハッシュテーブルは以下のような場合に有用です。

  • 高速なランダムアクセスが必要なデータのセット
  • 非整数のキー、連続しない整数のキーを持ったデータ
  • アイテムの追加・削除が大量に発生するデータ

以下のような場合、ハッシュテーブルは利用されるべきではありません

  • データのセットがソートされている必要がある場合
  • アイテムの数が非常に少ない場合(おおむね12-16個未満)
  • ランダムアクセスを必要としないデータ

このような状況では、配列、連結リスト、様々な木構造などが効果的です。

Mozilla のハッシュテーブル実装

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,
PRUint32>
<ns(C)StringHashKey,
PRUint32>
<nsIDHashKey,
PRUint32>
<nsISupportsHashKey,
PRUint32>
Interface (nsISupports) nsInterfaceHashtable
<nsUint32HashKey,
nsISupports>
<ns(C)StringHashKey,
nsISupports>
<nsIDHashKey,
nsISupports>
<nsISupportsHashKey,
nsISupports>
Class (nsString*) nsClassHashtable
<nsUint32HashKey,
nsString>
<ns(C)StringHashKey,
nsString>
<nsIDHashKey,
nsString>
<nsISupportsHashKey,
nsString>
Complex
(structures, etc.)
nsTHashtable<...>

PLDHash (JSDHash)

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 は、スタック・ヒープのどちらにも配置することができます。:

  • スタックに配置する場合、または C++ のクラスメンバとして利用される場合、テーブルは PL_DHashTableInit で初期化されPL_DHashTableFinish で破棄される必要があります。
  • ヒープに配置する場合、 PL_NewDHashTable, PL_DHashTableDestroy でテーブルの割り当て・削除を行ってください。

PLHashTable

PLHashTable は NSPR の一部です。ヘッダファイルは nsprpub/lib/ds/plhash.h にあります。 PLHashTable はヒープに多数の領域を割り当てようとするため、一般的には PLDHash の方が PLHashTable よりも優れています。

PLDHash よりも PLHashTable の方が好ましい状況は以下の2つです。

  • エントリーへのポインタが定数である必要がある場合。
  • ハッシュテーブルに格納されているエントリーが非常に大きい場合(12ワード以上)。 PLDHash は大きな構造体を効率的に扱えません。

nsTHashtable

nsTHashtablePLDHash をラップする C++ のテンプレートで、 PLDHash の複雑な部分(コールバック関数、構造体など)を隠蔽します。 xpcom/glue/nsTHashtable.h に目を通しておいてください。

nsTHashtable を利用するためには、利用者は pre-defined format にある通りにエントリークラスを宣言する必要があります。このエントリークラスは、ハッシュテーブルに格納するキーとデータを保持します(上記の PLDHash と同様です)。また、クラスの中でキーを処理する関数も宣言します。ほとんどの場合、エントリークラスは完全にインラインで書くことができます。エントリークラスの例については xpcom/glue/nsHashKeys.h を参照してください。

テンプレートのパラメータはエントリークラスです。テーブルを正しく初期化するためには Init() を利用しなくてはいけません。また現在のところ、テーブルの内容を変更するためには PutEntry/GetEntry/RemoveEntry 関数を利用してください。 EnumerateEntries 関数では列挙ができますが、並び順は見かけ上ランダムである(ソートされていない)ことに気をつけてください。

  • nsTHashtable はスタック、クラスメンバ、ヒープに割り当てることができます。
  • エントリーへのポインタは、ハッシュテーブルにアイテムが追加・削除された際に変更されることがあります。エントリーへのポインタを長時間保持しないでください。
  • このため、 nsTHashtable は本質的にスレッドセーフではありません。マルチスレッドで利用する場合、適切なロック機構を用意する必要があります。

nsTHashtable を使用する前に、 nsBaseHashtable とその関連クラスが利用用途に合うかどうか確認してください。エントリークラスを宣言する必要がないため、それらの方がずっと使いやすくなっています。もし単純なキー型・データ型を利用するのであれば、多くの場合こちらの方が良い選択肢です。

nsBaseHashtable とその関連クラス: nsDataHashtable, nsInterfaceHashtable, nsClassHashtable

これらの C++ テンプレートは、 PLDHash の複雑な部分のほとんどを隠蔽しつつ、ハッシュテーブルを利用するための高レベルなインタフェースを提供します。以下のような機能を持ちます:

  • ハッシュテーブルの操作はエントリークラスを使わずに行うことができます。コードの可読性を高めます。
  • スレッドセーフ性(オプション)。ハッシュテーブルは読み書きの際にロックを設定することができます。
  • 予め定義されたキークラス。strings, インタフェースを自動的にクリーンアップします。
  • nsInterfaceHashtable nsClassHashtable は自動的にオブジェクトを解放・削除し、メモリリークを防ぎます。

nsBaseHashtable は直接利用しません。ここから派生した3つの派生クラスから、保持するデータ型に合わせて利用するクラスを1つ選んでください。 KeyClassnsHashKeys.h で定義されています。他3つも同様です:

  • nsDataHashtable<KeyClass, DataType> - DataTypePRUint32 or PRBool のような単純型です。
  • nsInterfaceHashtable<KeyClass, Interface> - InterfacensISupports, nsIDOMNode のような XPCOM インタフェースです。
  • nsClassHashtable<KeyClass, T> - T は任意の C++ クラスです。ハッシュテーブルはオブジェクトへのポインタを格納します。また、オブジェクトがハッシュテーブルから取り去られた場合、そのオブジェクトを削除します。

目を通しておくべき重要なファイルは xpcom/glue/nsBaseHashtable.hxpcom/glue/nsHashKeys.h です。これらのクラスはスタック、クラスメンバ、ヒープに置くことができます。初期化には Init() 関数を利用してください。このとき、スレッドセーフな排他制御を行うかどうかを決められます。ハッシュテーブルの内容を変更するには Put(), Get(), Remove() 関数を利用してください。

2つの列挙関数が用意されています:

  • EnumerateRead() は読み取り専用の列挙型を提供します。内容の変更や削除はできません。
  • Enumerate() は読み書きのできる列挙型を提供します。必要に応じて内容の変更・削除ができます。

nsTHashtable をハッシュセットとして利用する

ハッシュセットはキーの存在だけを追跡します。キーとデータとの関連づけは行いません。このような動作は、 nsTHashtable<nsSomeHashKey> を利用することで実現できます。The appropriate entries are GetEntry and PutEntry.

Future Plans

nsISimpleEnumerator support

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.

Hash Functions

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*
(or nsISupports*)
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.

Mozilla's Old/Obsolete/Deprecated/Decrepit Hashtables

nsHashtable

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

nsObjectHashtable is a form of nsHashtable. It has been replaced by nsClassHashtable.

nsSupportsHashtable

nsSupportsHashtable is a form of nsHashtable. It has been replaced by nsInterfaceHashtable.

nsHashSets

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

nsDoubleHashtable is the (obsolete) precursor to nsTHashtable. It uses macros instead of C++ templates.

Original Document Information

 

ドキュメントのタグと貢献者

 このページの貢献者: teoli, tubureteru
 最終更新者: teoli,