Revision 64369 of Detailed XPCOM hashtable guide

  • Revision slug: Detailed_XPCOM_hashtable_guide
  • Revision title: Detailed XPCOM hashtable guide
  • Revision id: 64369
  • Created:
  • Creator: Tservo
  • Is current revision? No
  • Comment /* What Is a Hashtable? */
Tags: 

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?

Mozilla's Hashtable Implementations

Which Hashtable Should I Use?

PLDHash (JSDHash)

PLHashTable

nsTHashtable

nsBaseHashtable and friends: nsDataHashtable, nsInterfaceHashtable, and nsClassHashtable

nsHashSets

Future Plans

nsTHashSet

nsClassIHashtable

nsISimpleEnumerator support

Hash Functions

Mozilla's Old/Obsolete/Deprecated/Decrepit Hashtables

nsHashtable

nsObjectHashtable

nsSupportsHashtable

nsDoubleHashtable

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 “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.
</p>
<h2 name="When_Should_I_Use_a_Hashtable.3F"> When Should I Use a Hashtable? </h2>
<h2 name="Mozilla.27s_Hashtable_Implementations"> Mozilla's Hashtable Implementations </h2>
<h3 name="Which_Hashtable_Should_I_Use.3F"> Which Hashtable Should I Use? </h3>
<h3 name="PLDHash_.28JSDHash.29"> PLDHash (JSDHash) </h3>
<h3 name="PLHashTable"> PLHashTable </h3>
<h3 name="nsTHashtable"> nsTHashtable </h3>
<h3 name="nsBaseHashtable_and_friends:_nsDataHashtable.2C_nsInterfaceHashtable.2C_and_nsClassHashtable"> nsBaseHashtable and friends: nsDataHashtable, nsInterfaceHashtable, and nsClassHashtable </h3>
<h3 name="nsHashSets"> nsHashSets </h3>
<h2 name="Future_Plans"> Future Plans </h2>
<h3 name="nsTHashSet"> nsTHashSet </h3>
<h3 name="nsClassIHashtable"> nsClassIHashtable </h3>
<h3 name="nsISimpleEnumerator_support"> nsISimpleEnumerator support </h3>
<h2 name="Hash_Functions"> Hash Functions </h2>
<h2 name="Mozilla.27s_Old.2FObsolete.2FDeprecated.2FDecrepit_Hashtables"> Mozilla's Old/Obsolete/Deprecated/Decrepit Hashtables </h2>
<h3 name="nsHashtable"> nsHashtable </h3>
<h3 name="nsObjectHashtable"> nsObjectHashtable </h3>
<h3 name="nsSupportsHashtable"> nsSupportsHashtable </h3>
<h3 name="nsDoubleHashtable"> nsDoubleHashtable </h3>
<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