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:
|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;
nsDataHashtabledatatype is a scalar such as
nsInterfaceHashtabledatatype is an interface;
nsClassHashtabledatatype is a class pointer owned by the hashtable.
Which Hashtable Should I Use?
|Data Type:||None (Hash Set)||
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.
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 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
PLDHashEntryHdr. 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
You must also initialize a
PLDHashTableOps 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
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
PL_DHashTableInit, and finalized using
- When allocated on the heap, use
PL_DHashTableDestroyto allocate and delete the table.
nsBaseHashtable and friends: nsDataHashtable, nsInterfaceHashtable, and nsClassHashtable
Mozilla's Old/Obsolete/Deprecated/Decrepit Hashtables
Original Document Information
- Author(s): Benjamin Smedberg <email@example.com>