XPCOM hashtable guide

This is the simplified version of the Detailed XPCOM hashtable guide. Everything you need to know is probably on this page.

Also note that mfbt/HashTable.h now exists. It is a lot faster than the XPCOM hashtables due to more inlining and templating, and the API is arguably better.

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; iterated over in a sorted fashion. unsorted: stored unsorted; cannot be iterated over 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 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.

Which Hashtable Should I Use?

The appropriate hashtable class to use depends solely on the data type. The template specialization to use depends on the data type and the key type.

Data Type Hashtable class
None (for a hash set) nsTHashtable

Simple Types

(numbers, booleans, etc)

 nsDataHashtable

Structs or Classes

(nsString, custom defined structs or classes that are not reference-counted)

nsClassHashtable
Reference-counted Concrete Classes nsRefPtrHashtable
Interface Pointers nsInterfaceHashtable

Each of these classes is a template with two parameters. The first is the hash key and the second is the data to be stored. There are a number of builtin hash keys available in nsHashKeys.h, the more useful of which are listed below.

Key Type Hashkey class
Strings nsStringHashKey/nsCStringHashKey
Integers nsUint32HashKey/nsUint64HashKey
Pointers nsPtrHashKey<T>
Owned Interface Pointers nsISupportsHashKey
Reference-Counted Concrete Classes nsRefPtrHashKey

There are a number of more esoteric hashkey classes in nsHashKeys.h, and you can always roll your own if none of these fit your needs (make sure you're not duplicating an existing hashkey class though!)

Once you've determined what hashtable and hashkey classes you need, you can put it all together. A few examples:

  • A hashtable that maps UTF-8 origin names to a DOM Window - nsInterfaceHashtable<nsCStringHashKey, nsIDOMWindow>
  • A hashtable that maps 32 bit integers to floats - nsDataHashtable<nsUint32HashKey, float>
  • A hashtable that maps nsISupports pointers to reference counted CacheEntrys - nsRefPtrHashtable<nsISupportsHashKey, CacheEntry>
  • A hashtable that maps JSContext pointers to a ContextInfo struct - nsClassHashtable<nsPtrHashKey<JSContext>, ContextInfo>
  • A hashset of strings - nsTHashtable<nsStringHashKey>

Hashtable API

The hashtable classes all expose the same basic API. There are three key methods, Get, Put, and Remove, which retrieve entries from the hashtable, write entries into the hashtable, and remove entries from the hashtable respectively.

The hashtables that hold references to pointers (nsRefPtrHashtable and nsInterfaceHashtable) also have GetWeak methods that return non-AddRefed pointers.

All of these hashtable classes can be iterated over via the Iterator class and cleared via the Clear method.