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:

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.

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.

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.