Detailed XPCOM hashtable guide

  • Revision slug: Detailed_XPCOM_hashtable_guide
  • Revision title: Detailed XPCOM hashtable guide
  • Revision id: 64400
  • Created:
  • Creator: Dria
  • Is current revision? No
  • Comment

Revision Content

What Is a Hashtable?

A hashtable is a data construct that stores a set of items. Each item has a key that identifies the item. Items are found, added, and removed from the hashtable by using the key. Hashtables may seem like arrays, but there are important differences:

Array Hashtable
Keys: integer: arrays are always keyed on integers, and must be contiguous. any type: almost any datatype can be used as key, including strings, integers, XPCOM interface pointers, IIDs, and almost anything else. Keys can be disjunct (i.e. you can store entries with keys 1, 5, and 3000).
Lookup Time: O(1): lookup time is a simple constant O(1): lookup time is mostly-constant, but the constant time can be larger than an array lookup
Sorting: sorted: stored sorted; enumerated in a sorted fashion. unsorted: stored unsorted; cannot be enumerated in a sorted manner.
Inserting/Removing: O(n): adding and removing items from a large array can be time-consuming O(1): adding and removing items from hashtables is a quick operation
Wasted space: none: Arrays are packed structures, so there is no wasted space. some: hashtables are not packed structures; depending on on the implementation, there may be significant wasted memory.

In their implementation, hashtables take the key and apply a mathematical hash function to randomize the key and then use the hash to find the location in the hashtable. Good hashtable implementations will automatically resize the hashtable in memory if extra space is needed, or if too much space has been allocated.

When Should I Use a Hashtable?

Hashtables are useful for

  • sets of data that need swift random access;
  • with non-integral keys or non-contiguous integral keys;
  • or where items will be frequently added or removed.

Hashtables should not be used for

  • Sets that need to be sorted;
  • Very small datasets (less than 12-16 items);
  • Data that does not need random access.

In these situations, an array, a linked-list, or various tree data structures are more efficient.

Mozilla's Hashtable Implementations

Mozilla has several hashtable implementations, which have been tested and, tuned, and hide the inner complexities of hashtable implementations:

  • PLDHash - low-level C API; stores keys and data in one large memory structure; uses the heap efficiently; client must declare an "entry class" and may not hold onto entry pointers.
  • PLHashTable - low-level C API; entry class pointers are constant; more efficient for large entry structures; often wastes memory making many small heap allocations.
  • nsTHashtable - low-level C++ wrapper around PLDHash; generates callback functions and handles most casting automagically. Client writes their own entry class which can include complex key and data types.
  • nsDataHashtable/nsInterfaceHashtable/nsClassHashtable - high-level C++ wrappers around PLDHash; simplifies the common usage pattern mapping a simple keytype to a simple datatype; client does not need to declare or manage an entry class; nsDataHashtable datatype is a scalar such as RUint32; nsInterfaceHashtable datatype is an interface; nsClassHashtable datatype is a class pointer owned by the hashtable.

Which Hashtable Should I Use?

Key Type:
integer String/CString nsID nsISupports* Complex
Data Type: 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 and JSDHash are the same thing; one is linked from the XPCOM libraries, the other from the JS libraries. JSDHash is used extensively in the SpiderMonkey JS engine.

The PLDHash implementation is a fairly low-level implementation, written in C. It is extremely flexible, but requires some time to understand and use. A basic guide is included here, but you should read most of {{template.Source("xpcom/ds/pldhash.h")}} if you intend to use PLDHash. The C++ wrappers for PLDHash (see below) are often much easier and safer to use in C++ code, as many potential casting errors are easily avoided.

You must declare an entry struct type, deriving from {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#88", "<code>PLDHashEntryHdr</code>" ])}}. This entry struct should contain whatever data you wish to store in the hashtable (any pointer or fixed-length data type). Note: because of the double-hashing implementation, entries may move in memory when the hashtable is altered. If you need entry pointers to remain constant, you may want to consider using PLHashTable instead.

You must also initialize a {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#330", "<code>PLDHashTableOps</code>" ])}} structure. This serves similarly to a vtable in C++, with pointers to appropriate user-defined functions that initialize, compare, and match entries. Because PLDHash does not know what datatype your key is, all functions that work with keys are declared using {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#82", "const void*" ])}}, and your client code must cast these pointers to the appropriate type.

PLDHashTables can be allocated on the stack or the heap:

  • When allocated on the stack, or as a C++ class member, the table must be initialized using {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#417", "PL_DHashTableInit" ])}}, and finalized using {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#449", "PL_DHashTableFinish" ])}};
  • When allocated on the heap, use {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#400", "PL_NewDHashTable" ])}} and {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#408", "PL_DHashTableDestroy" ])}} to allocate and delete the table.

PLHashTable

PLHashTable is a part of NSPR. The header file can be found at {{template.Source("nsprpub/lib/ds/plhash.h")}}. In general, PLDHash is a better solution than PLHashTable, because PLHashTable makes many heap allocations.

There are two situations where PLHashTable may be preferable to PLDHash:

  • You need entry-pointers to remain constant.
  • The entries stored in the table are very large (larger than 12 words). PLDHash does not handle large entry structures efficiently.

nsTHashtable

nsTHashtable is a C++ template that wraps PLDHash. It hides many of the complexities of PLDHash (callback functions, the ops structure, etc). You should read {{template.Source("xpcom/ds/nsTHashtable.h")}}.

To use nsTHashtable, you must declare an entry-class in a {{wiki.template('Named-source', [ "xpcom/ds/nsTHashtable.h#65", "pre-defined format" ])}}. This entry class contains the key and the data that you are hashing (just like PLDHash, above). It also declares functions that manipulate the key. In most cases, the functions of this entry class can be entirely inline. For examples of entry classes, see the declarations at {{template.Source("xpcom/ds/nsHashKeys.h")}}.

The template parameter is the entry class. You must use the Init() function to initalize the table properly. At this point, use the functions PutEntry/GetEntry/RemoveEntry to alter the hashtable. EnumerateEntries will do enumeration, but beware that the enumeration will occur in a seemingly-random order (no sorting).

  • nsTHashtables can be allocated on the stack, as class members, or on the heap.
  • Entry pointers can and do change when items are added to the hashtable, or removed. Do not keep long-lasting pointers to entries.
  • because of this, nsTHashtable is not inherently thread-safe. If you use a hashtable in a multi-thread environment, you must provide locking as appropriate.

Before using nsTHashtable, see if nsBaseHashtable and relatives will work for you. They are much easier to use, because you do not have to declare an entry class. If you are hashing a simple key type to a simple data type, they are generally a better choice.

nsBaseHashtable and friends: nsDataHashtable, nsInterfaceHashtable, and nsClassHashtable

These C++ templates provide a high-level interface for using hashtables that hides most of the complexities of PLDHash. They provide the following features:

  • hashtable operations can be completed without using an entry class, making code easier to read;
  • optional thread-safety: the hashtable can manage a read-write lock around the table;
  • predefined key classes provide automatic cleanup of strings/interfaces
  • nsInterfaceHashtable and nsClassHashtable automatically release/delete data pointers to avoid leaks.

nsBaseHashtable is not used directly; choose one of the three derivative classes based on the data type you want to store. The KeyClass is taken from nsHashKeys.h and is the same for all three classes:

  • nsDataHashtable<KeyClass, DataType> - DataType is a simple type such as PRUint32 or PRBool.
  • nsInterfaceHashtable<KeyClass, Interface> - Interface is an XPCOM interface such as nsISupports or nsIDOMNode
  • nsClassHashtable<KeyClass, T> - T is any C++ class. The hashtable stores a pointer to the class, and deletes it when the entry is removed.

The important files to read are {{template.Source("xpcom/ds/nsBaseHashtable.h")}} and {{template.Source("xpcom/ds/nsHashKeys.h")}}. These classes can be used on the stack, as a class member, or on the heap. Initialize using the Init() function; you can specify whether you need thread-safety at this time. Use the Put(), Get(), and Remove() methods to alter the table.

There are two enumeration functions:

  • EnumerateRead() performs a read-only enumeration, where entries cannot be changed or removed;
  • Enumerate() performs a read-write enumeration, where entries may be changed or removed as necessary.

nsHashSets

A hash set only tracks the existence of keys: it does not associate data with the keys. nsHashSets has predefined hash sets for common keys, which are trivially easy to use. See {{template.Source("xpcom/ds/nsHashSets.h")}}. The appropriate functions are Put(), Contains(), and Remove().

Future Plans

nsTHashSet

Although some predefined hash sets are already available in nsHashSets.h, a generic solution using templates (similar to nsDataHashtable) would be easy to implement. When I have time...

nsClassIHashtable

nsClassHashtable keeps owning pointers to C++ objects. However, for many uses such as keeping nsString and nsCOMArray as data members, the class can be allocated within the hashtable, rather than as a pointer. This can reduce heap allocations, though it prevents thread-safety.

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 {{wiki.template('Named-source', [ "xpcom/base/nscore.h#316", "NS_PTR_TO_INT32" ])}}
char* string {{wiki.template('Named-source', [ "xpcom/ds/nsCRT.h#228", "nsCRT::HashCode()" ])}}
PRUnichar* string
nsAString {{wiki.template('Named-source', [ "string/src/nsReadableUtils.cpp#1105", "HashString()" ])}}
nsACString
nsID& {{wiki.template('Named-source', [ "xpcom/ds/nsHashKeys.h#207", "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

{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h", "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

{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h#143", "nsObjectHashtable" ])}} is a form of nsHashtable. It has been replaced by nsClassHashtable.

nsSupportsHashtable

{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h#173", "nsSupportsHashtable" ])}} is a form of nsHashtable. It has been replaced by nsInterfaceHashtable.

nsDoubleHashtable

{{wiki.template('Named-source', [ "xpcom/ds/nsDoubleHashtable.h", "nsDoubleHashtable" ])}} is the (obsolete) precursor to nsTHashtable. It uses macros instead of C++ templates.

Original Document Information

  • Author(s): Benjamin Smedberg <bsmedberg@covad.net>

Revision Source

<p>
</p>
<h2 name="What_Is_a_Hashtable.3F"> What Is a Hashtable? </h2>
<p>A hashtable is a data construct that stores a set of <b>items</b>. Each item has a <b>key</b> that identifies the item. Items are found, added, and removed from the hashtable by using the key. Hashtables may seem like <a href="en/XPCOM/Arrays">arrays</a>, but there are important differences:
</p>
<table class="standard-table">
<tbody><tr>
<th></th>
<th class="header">Array</th>
<th class="header">Hashtable</th>
</tr>
<tr>
<td class="header">Keys:</td>
<td><i>integer:</i> arrays are always keyed on integers, and must be contiguous.</td>
<td><i>any type:</i> almost any datatype can be used as key, including strings, integers, XPCOM interface pointers, IIDs, and almost anything else. Keys can be disjunct (i.e. you can store entries with keys 1, 5, and 3000).</td>
</tr>
<tr>
<td class="header">Lookup Time:</td>
<td><i>O(1):</i> lookup time is a simple constant</td>
<td><i>O(1):</i> lookup time is mostly-constant, but the constant time can be larger than an array lookup</td>
</tr>
<tr>
<td class="header">Sorting:</td>
<td><i>sorted:</i> stored sorted; enumerated in a sorted fashion.</td>
<td><i>unsorted:</i> stored unsorted; cannot be enumerated in a sorted manner.</td>
</tr>
<tr>
<td class="header">Inserting/Removing:</td>
<td><i>O(n):</i> adding and removing items from a large array can be time-consuming</td>
<td><i>O(1):</i> adding and removing items from hashtables is a quick operation</td>
</tr>
<tr>
<td class="header">Wasted space:</td>
<td><i>none:</i> Arrays are packed structures, so there is no wasted space.</td>
<td><i>some:</i> hashtables are not packed structures; depending on on the implementation, there may be significant wasted memory.</td>
</tr>
</tbody></table>
<p>In their implementation, hashtables take the key and apply a mathematical <b>hash function</b> to <b>randomize</b> the key and then use the hash to find the location in the hashtable. Good hashtable implementations will automatically resize the hashtable in memory if extra space is needed, or if too much space has been allocated.
</p>
<h2 name="When_Should_I_Use_a_Hashtable.3F"> When Should I Use a Hashtable? </h2>
<p>Hashtables are useful for
</p>
<ul><li> sets of data that need swift <b>random access</b>;
</li><li> with <b>non-integral keys</b> or <b>non-contiguous integral keys</b>;
</li><li> or where <b>items will be frequently added or removed</b>. 
</li></ul>
<p>Hashtables should <i>not</i> be used for
</p>
<ul><li> Sets that need to be <b>sorted</b>;
</li><li> Very small datasets (less than 12-16 items);
</li><li> Data that does not need random access. 
</li></ul>
<p>In these situations, an array, a linked-list, or various tree data structures are more efficient.
</p>
<h2 name="Mozilla.27s_Hashtable_Implementations"> Mozilla's Hashtable Implementations </h2>
<p>Mozilla has several hashtable implementations, which have been tested and, tuned, and hide the inner complexities of hashtable implementations:
</p>
<ul><li> <code><a href="#PLDHash_.28JSDHash.29">PLDHash</a></code> - low-level C API; stores keys and data in one large memory structure; uses the heap efficiently; client must declare an "entry class" and may not hold onto entry pointers.
</li><li> <code><a href="#PLHashTable">PLHashTable</a></code> - low-level C API; entry class pointers are constant; more efficient for large entry structures; often wastes memory making many small heap allocations.
</li><li> <code><a href="#nsTHashtable">nsTHashtable</a></code> - low-level C++ wrapper around <code>PLDHash</code>; generates callback functions and handles most casting automagically. Client writes their own entry class which can include complex key and data types.
</li><li> <code><a href="#nsBaseHashtable_and_friends:_nsDataHashtable.2C_nsInterfaceHashtable.2C_and_nsClassHashtable">nsDataHashtable/nsInterfaceHashtable/nsClassHashtable</a></code> - high-level C++ wrappers around <code>PLDHash</code>; simplifies the common usage pattern mapping a simple keytype to a simple datatype; client does not need to declare or manage an entry class; <code><b>nsDataHashtable</b></code> datatype is a scalar such as <code>RUint32</code>; <code><b>nsInterfaceHashtable</b></code> datatype is an interface; <code><b>nsClassHashtable</b></code> datatype is a class pointer owned by the hashtable.
</li></ul>
<h3 name="Which_Hashtable_Should_I_Use.3F"> Which Hashtable Should I Use? </h3>
<table class="standard-table">
<tbody><tr>
<th class="header" colspan="2" rowspan="2"></th>
<th class="header" colspan="5">Key Type:</th>
</tr>
<tr>
<th class="header">integer</th>
<th class="header">String/CString</th>
<th class="header">nsID</th>
<th class="header">nsISupports*</th>
<th class="header">Complex</th>
</tr>
<tr>
<td class="header" rowspan="8">Data Type:</td>
<td class="header">None (Hash Set)</td>
<td><code>nsInt32HashSet</code></td>
<td><code>ns(C)StringHashSet</code></td>
<td colspan="3"><code>nsTHashtable&lt;...&gt;</code></td>
</tr>
<tr>
<td class="header" rowspan="2">Simple (PRUint32)</td>
<td colspan="4"><code>nsDataHashtable</code>
</td><td rowspan="6"><code>nsTHashtable&lt;...&gt;</code></td>
</tr>
<tr>
<td><code>&lt;nsUInt32HashKey,<br>PRUint32&gt;</code></td>
<td><code>&lt;ns(C)StringHashKey,<br>PRUint32&gt;</code></td>
<td><code>&lt;nsIDHashKey,<br>PRUint32&gt;</code></td>
<td><code>&lt;nsISupportsHashKey,<br>PRUint32&gt;</code></td>
</tr>
<tr>
<td class="header" rowspan="2">Interface (nsISupports)</td>
<td colspan="4"><code>nsInterfaceHashtable</code>
</td></tr>
<tr>
<td><code>&lt;nsUInt32HashKey,<br>nsISupports&gt;</code></td>
<td><code>&lt;ns(C)StringHashKey,<br>nsISupports&gt;</code></td>
<td><code>&lt;nsIDHashKey,<br>nsISupports&gt;</code></td>
<td><code>&lt;nsISupportsHashKey,<br>nsISupports&gt;</code></td>
</tr>
<tr>
<td class="header" rowspan="2">Class (nsString*)</td>
<td colspan="4"><code>nsClassHashtable</code></td>
</tr>
<tr>
<td><code>&lt;nsUInt32HashKey,<br>nsString&gt;</code></td>
<td><code>&lt;ns(C)StringHashKey,<br>nsString&gt;</code></td>
<td><code>&lt;nsIDHashKey,<br>nsString&gt;</code></td>
<td><code>&lt;nsISupportsHashKey,<br>nsString&gt;</code></td>
</tr>
<tr>
<td class="header">Complex<br>(structures, etc.)</td>
<td colspan="5"><code>nsTHashtable&lt;...&gt;</code></td>
</tr>
</tbody></table>
<h3 name="PLDHash_.28JSDHash.29"> PLDHash (JSDHash) </h3>
<p><code>PLDHash</code> and <code>JSDHash</code> are the same thing; one is linked from the XPCOM libraries, the other from the JS libraries. <code>JSDHash</code> is used extensively in the SpiderMonkey JS engine.
</p><p>The <code>PLDHash</code> implementation is a fairly low-level implementation, written in C. It is extremely flexible, but requires some time to understand and use. A basic guide is included here, but you should read most of {{template.Source("xpcom/ds/pldhash.h")}} if you intend to use <code>PLDHash</code>. The C++ wrappers for <code>PLDHash</code> (see below) are often much easier and safer to use in C++ code, as many potential casting errors are easily avoided.
</p><p>You must declare an <b>entry struct</b> type, deriving from {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#88", "&lt;code&gt;PLDHashEntryHdr&lt;/code&gt;" ])}}. This entry struct should contain whatever data you wish to store in the hashtable (any pointer or fixed-length data type). <b>Note:</b> because of the double-hashing implementation, entries may move in memory when the hashtable is altered. If you need entry pointers to remain constant, you may want to consider using <code><a href="#PLHashTable">PLHashTable</a></code> instead.
</p><p>You must also initialize a {{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#330", "&lt;code&gt;PLDHashTableOps&lt;/code&gt;" ])}} structure. This serves similarly to a vtable in C++, with pointers to appropriate user-defined functions that initialize, compare, and match entries. Because <code>PLDHash</code> does not know what datatype your key is, all functions that work with keys are declared using <code>{{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#82", "const void*" ])}}</code>, and your client code must cast these pointers to the appropriate type.
</p><p>PLDHashTables can be allocated on the stack or the heap:
</p>
<ul><li> When allocated on the stack, or as a C++ class member, the table must be initialized using <code>{{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#417", "PL_DHashTableInit" ])}}</code>, and finalized using <code>{{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#449", "PL_DHashTableFinish" ])}}</code>;
</li><li> When allocated on the heap, use <code>{{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#400", "PL_NewDHashTable" ])}}</code> and <code>{{wiki.template('Named-source', [ "xpcom/ds/pldhash.h#408", "PL_DHashTableDestroy" ])}}</code> to allocate and delete the table.
</li></ul>
<h3 name="PLHashTable"> PLHashTable </h3>
<p><code>PLHashTable</code> is a part of NSPR. The header file can be found at <code>{{template.Source("nsprpub/lib/ds/plhash.h")}}</code>. In general, <code><a href="#PLDHash_.28JSDHash.29">PLDHash</a></code> is a better solution than <code>PLHashTable</code>, because <code>PLHashTable</code> makes many heap allocations.
</p><p>There are two situations where <code>PLHashTable</code> may be preferable to <code>PLDHash</code>:
</p>
<ul><li> You need entry-pointers to remain constant.
</li><li> The entries stored in the table are very large (larger than 12 words). <code>PLDHash</code> does not handle large entry structures efficiently.
</li></ul>
<h3 name="nsTHashtable"> nsTHashtable </h3>
<p><code>nsTHashtable</code> is a C++ template that wraps <code>PLDHash</code>. It hides many of the complexities of <code>PLDHash</code> (callback functions, the ops structure, etc). You should read {{template.Source("xpcom/ds/nsTHashtable.h")}}.
</p><p>To use <code>nsTHashtable</code>, you must declare an entry-class in a {{wiki.template('Named-source', [ "xpcom/ds/nsTHashtable.h#65", "pre-defined format" ])}}. This entry class contains the key and the data that you are hashing (just like <code>PLDHash</code>, above). It also declares functions that manipulate the key. In most cases, the functions of this entry class can be entirely inline. For examples of entry classes, see the declarations at {{template.Source("xpcom/ds/nsHashKeys.h")}}.
</p><p>The template parameter is the entry class. You must use the <code>Init()</code> function to initalize the table properly. At this point, use the functions <code>PutEntry/GetEntry/RemoveEntry</code> to alter the hashtable. <code>EnumerateEntries</code> will do enumeration, but beware that the enumeration will occur in a seemingly-random order (no sorting).
</p>
<ul><li> <code>nsTHashtable</code>s can be allocated on the stack, as class members, or on the heap.
</li><li> Entry pointers can and do change when items are added to the hashtable, or removed. Do not keep long-lasting pointers to entries.
</li><li> because of this, <code>nsTHashtable</code> is not inherently thread-safe. If you use a hashtable in a multi-thread environment, you must provide locking as appropriate.
</li></ul>
<p>Before using <code>nsTHashtable</code>, see if <code>nsBaseHashtable</code> and relatives will work for you. They are much easier to use, because you do not have to declare an entry class. If you are hashing a simple key type to a simple data type, they are generally a better choice.
</p>
<h3 name="nsBaseHashtable_and_friends:_nsDataHashtable.2C_nsInterfaceHashtable.2C_and_nsClassHashtable"> nsBaseHashtable and friends: nsDataHashtable, nsInterfaceHashtable, and nsClassHashtable </h3>
<p>These C++ templates provide a high-level interface for using hashtables that hides most of the complexities of <code>PLDHash</code>. They provide the following features:
</p>
<ul><li> hashtable operations can be completed without using an entry class, making code easier to read;
</li><li> optional thread-safety: the hashtable can manage a read-write lock around the table;
</li><li> predefined key classes provide automatic cleanup of strings/interfaces
</li><li> <code>nsInterfaceHashtable</code> and <code>nsClassHashtable</code> automatically release/delete data pointers to avoid leaks. 
</li></ul>
<p><code>nsBaseHashtable</code> is not used directly; choose one of the three derivative classes based on the data type you want to store. The <code>KeyClass</code> is taken from <code>nsHashKeys.h</code> and is the same for all three classes:
</p>
<ul><li> <code>nsDataHashtable&lt;KeyClass, <i>DataType</i>&gt;</code> - <code>DataType</code> is a simple type such as <code>PRUint32</code> or <code>PRBool</code>.
</li><li> <code>nsInterfaceHashtable&lt;KeyClass, <i>Interface</i>&gt;</code> - <code>Interface</code> is an XPCOM interface such as <code>nsISupports</code> or <code>nsIDOMNode</code>
</li><li> <code>nsClassHashtable&lt;KeyClass, <i>T</i>&gt;</code> - <code>T</code> is any C++ class. The hashtable stores a pointer to the class, and deletes it when the entry is removed. 
</li></ul>
<p>The important files to read are {{template.Source("xpcom/ds/nsBaseHashtable.h")}} and {{template.Source("xpcom/ds/nsHashKeys.h")}}. These classes can be used on the stack, as a class member, or on the heap. Initialize using the <code>Init()</code> function; you can specify whether you need thread-safety at this time. Use the <code>Put()</code>, <code>Get()</code>, and <code>Remove()</code> methods to alter the table.
</p><p>There are two enumeration functions:
</p>
<ul><li> <code>EnumerateRead()</code> performs a read-only enumeration, where entries cannot be changed or removed;
</li><li> <code>Enumerate()</code> performs a read-write enumeration, where entries may be changed or removed as necessary.
</li></ul>
<h3 name="nsHashSets"> nsHashSets </h3>
<p>A hash set only tracks the existence of keys: it does not associate data with the keys. <code>nsHashSets</code> has predefined hash sets for common keys, which are trivially easy to use. See {{template.Source("xpcom/ds/nsHashSets.h")}}. The appropriate functions are <code>Put()</code>, <code>Contains()</code>, and <code>Remove()</code>.
</p>
<h2 name="Future_Plans"> Future Plans </h2>
<h3 name="nsTHashSet"> nsTHashSet </h3>
<p>Although some predefined hash sets are already available in <code>nsHashSets.h</code>, a generic solution using templates (similar to <code>nsDataHashtable</code>) would be easy to implement. When I have time...
</p>
<h3 name="nsClassIHashtable"> nsClassIHashtable </h3>
<p><code>nsClassHashtable</code> keeps owning pointers to C++ objects. However, for many uses such as keeping <code>nsString</code> and <code>nsCOMArray</code> as data members, the class can be allocated within the hashtable, rather than as a pointer. This can reduce heap allocations, though it prevents thread-safety.
</p>
<h3 name="nsISimpleEnumerator_support"> nsISimpleEnumerator support </h3>
<p>The (obsolete) <code>nsHashtable</code> has a wrapper that exposes an <code>nsISimpleEnumerator</code> on its items. I will add this support to the various <code>nsBaseHashtable</code> classes as well, as needed.
</p>
<h2 name="Hash_Functions"> Hash Functions </h2>
<p>All of the above hashtables need a <a class="external" href="http://www.nist.gov/dads/HTML/hash.html">Hash Function</a>. 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:
</p>
<table class="standard-table">
<tbody><tr>
<td><code>void* <br>
(or nsISupports*)</code></td>
<td>cast using <code>{{wiki.template('Named-source', [ "xpcom/base/nscore.h#316", "NS_PTR_TO_INT32" ])}}</code></td>
</tr>
<tr>
<td><code>char*</code> string</td>
<td rowspan="2"><code>{{wiki.template('Named-source', [ "xpcom/ds/nsCRT.h#228", "nsCRT::HashCode()" ])}}</code></td>
</tr>
<tr>
<td><code>PRUnichar*</code> string</td>
</tr>
<tr>
<td><code>nsAString</code></td>
<td rowspan="2"><code>{{wiki.template('Named-source', [ "string/src/nsReadableUtils.cpp#1105", "HashString()" ])}}</code></td>
</tr>
<tr>
<td><code>nsACString</code></td>
</tr><tr>
<td><code>nsID&amp;</code></td>
<td><code>{{wiki.template('Named-source', [ "xpcom/ds/nsHashKeys.h#207", "nsIDHashKey::HashKey()" ])}}</code></td>
</tr>
</tbody></table>
<p>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 <code>nsID</code>.
</p>
<h2 name="Mozilla.27s_Old.2FObsolete.2FDeprecated.2FDecrepit_Hashtables"> Mozilla's Old/Obsolete/Deprecated/Decrepit Hashtables </h2>
<h3 name="nsHashtable"> nsHashtable </h3>
<p><code>{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h", "nsHashtable" ])}}</code> was a C++ wrapper around <code>PLHashTable</code>, and now wraps <code>PLDHash</code>. The design of the key classes is not optimal, however, and <code>nsHashtable</code> has been deprecated in favor of <code>nsDataHashtable</code> and friends.
</p>
<h3 name="nsObjectHashtable"> nsObjectHashtable </h3>
<p><code>{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h#143", "nsObjectHashtable" ])}}</code> is a form of <code>nsHashtable</code>. It has been replaced by <code>nsClassHashtable</code>.
</p>
<h3 name="nsSupportsHashtable"> nsSupportsHashtable </h3>
<p><code>{{wiki.template('Named-source', [ "xpcom/ds/nsHashtable.h#173", "nsSupportsHashtable" ])}}</code> is a form of <code>nsHashtable</code>. It has been replaced by <code>nsInterfaceHashtable</code>.
</p>
<h3 name="nsDoubleHashtable"> nsDoubleHashtable </h3>
<p><code>{{wiki.template('Named-source', [ "xpcom/ds/nsDoubleHashtable.h", "nsDoubleHashtable" ])}}</code> is the (obsolete) precursor to <code>nsTHashtable</code>. It uses macros instead of C++ templates.
</p>
<div class="originaldocinfo">
<h2 name="Original_Document_Information"> Original Document Information </h2>
<ul><li> Author(s): Benjamin Smedberg &lt;bsmedberg@covad.net&gt;
</li></ul>
</div>
Revert to this revision