XPCOM Hashtable Technical Details¶
This is a deep-dive into the underlying mechanisms that power the XPCOM hashtables. Some of this information is quite old and may be out of date. If you’re looking for how to use XPCOM hashtables, you should consider reading the XPCOM Hashtable Guide instead.
Mozilla’s Hashtable Implementations¶
Mozilla has several hashtable implementations, which have been tested and tuned, and hide the inner complexities of hashtable implementations:
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.
nsTHashMap/nsInterfaceHashtable/nsClassHashtable- simplifies the common usage pattern mapping a simple keytype to a simple datatype; client does not need to declare or manage an entry class;
nsTHashMapdatatype is a scalar such as
nsInterfaceHashtabledatatype is an XPCOM interface;
nsClassHashtabledatatype is a class pointer owned by the hashtable.
PLHashTable is a part of NSPR. The header file can be found at plhash.h.
There are two situations where
PLHashTable may be preferable:
You need entry-pointers to remain constant.
The entries stored in the table are very large (larger than 12 words).
nsTHashtable, you must declare an entry-class. This
entry class contains the key and the data that you are hashing. 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 nsHashKeys.h.
The template parameter is the entry class. After construction, use the
PutEntry/GetEntry/RemoveEntry to alter the hashtable. The
Iterator class will do iteration, but beware that the iteration 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 or removed from the hashtable. Do not keep long-lasting pointers to entries.
because of this,
nsTHashtableis not inherently thread-safe. If you use a hashtable in a multi-thread environment, you must provide locking as appropriate.
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: nsTHashMap, nsInterfaceHashtable, and nsClassHashtable¶
These C++ templates provide a high-level interface for using hashtables that hides most of the complexities of the underlying implementation. 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
nsClassHashtableautomatically release/delete objects 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
DataTypeis a simple type such as
Interfaceis an XPCOM interface such as
Tis any C++ class. The hashtable stores a pointer to the object, and deletes that object when the entry is removed.
The important files to read are nsBaseHashtable.h and nsHashKeys.h. These classes can be used on the stack, as a class member, or on the heap.
Using nsTHashtable as a hash-set¶
A hash set only tracks the existence of keys: it does not associate data
with the keys. This can be done using
The appropriate entries are GetEntry and PutEntry.