xpcom/docs/hashtables.rst

   1 XPCOM Hashtable Guide
   2 =====================
   3
   4 .. note::
   5
   6    For a deep-dive into the underlying mechanisms that power our hashtables,
   7    check out the :ref:`XPCOM Hashtable Technical Details`
   8    document.
   9
  10 What Is a Hashtable?
  11 --------------------
  12
  13 A hashtable is a data construct that stores a set of **items**. Each
  14 item has a **key** that identifies the item. Items are found, added, and
  15 removed from the hashtable by using the key. Hashtables may seem like
  16 arrays, but there are important differences:
  17
  18 +-------------------------+----------------------+----------------------+
  19 |                         | Array                | Hashtable            |
  20 +=========================+======================+======================+
  21 | **Keys**                | *integer:* arrays    | *any type:* almost   |
  22 |                         | are always keyed on  | any datatype can be  |
  23 |                         | integers and must    | used as key,         |
  24 |                         | be contiguous.       | including strings,   |
  25 |                         |                      | integers, XPCOM      |
  26 |                         |                      | interface pointers,  |
  27 |                         |                      | IIDs, and almost     |
  28 |                         |                      | anything else. Keys  |
  29 |                         |                      | can be disjunct      |
  30 |                         |                      | (i.e. you can store  |
  31 |                         |                      | entries with keys 1, |
  32 |                         |                      | 5, and 3000).        |
  33 +-------------------------+----------------------+----------------------+
  34 | **Lookup Time**         | *O(1):* lookup time  | *O(1):* lookup time  |
  35 |                         | is a simple constant | is mostly-constant,  |
  36 |                         |                      | but the constant     |
  37 |                         |                      | time can be larger   |
  38 |                         |                      | than an array lookup |
  39 +-------------------------+----------------------+----------------------+
  40 | **Sorting**             | *sorted:* stored     | *unsorted:* stored   |
  41 |                         | sorted; iterated     | unsorted; cannot be  |
  42 |                         | over in a sorted     | iterated over in a   |
  43 |                         | fashion.             | sorted manner.       |
  44 +-------------------------+----------------------+----------------------+
  45 | **Inserting/Removing**  | *O(n):* adding and   | *O(1):* adding and   |
  46 |                         | removing items from  | removing items from  |
  47 |                         | a large array can be | hashtables is a      |
  48 |                         | time-consuming       | quick operation      |
  49 +-------------------------+----------------------+----------------------+
  50 | **Wasted space**        | *none:* Arrays are   | *some:* hashtables   |
  51 |                         | packed structures,   | are not packed       |
  52 |                         | so there is no       | structures;          |
  53 |                         | wasted space.        | depending on the     |
  54 |                         |                      | implementation,      |
  55 |                         |                      | there may be         |
  56 |                         |                      | significant wasted   |
  57 |                         |                      | memory.              |
  58 +-------------------------+----------------------+----------------------+
  59
  60 In their implementation, hashtables take the key and apply a
  61 mathematical **hash function** to **randomize** the key and then use the
  62 hash to find the location in the hashtable. Good hashtable
  63 implementations will automatically resize the hashtable in memory if
  64 extra space is needed, or if too much space has been allocated.
  65
  66 .. _When_Should_I_Use_a_Hashtable.3F:
  67
  68 When Should I Use a Hashtable?
  69 ------------------------------
  70
  71 Hashtables are useful for
  72
  73 -  sets of data that need swift **random access**
  74 -  with **non-integral keys** or **non-contiguous integral keys**
  75 -  or where **items will be frequently added or removed**
  76
  77 Hashtables should *not* be used for
  78
  79 -  Sets that need to be **sorted**
  80 -  Very small datasets (less than 12-16 items)
  81 -  Data that does not need random access
  82
  83 In these situations, an array, a linked-list, or various tree data
  84 structures are more efficient.
  85
  86 .. _Which_Hashtable_Should_I_Use.3F:
  87
  88 Which Hashtable Should I Use?
  89 -----------------------------
  90
  91 If there is **no** key type, you should use an ``nsTHashSet``.
  92
  93 If there is a key type, you should use an ``nsTHashMap``.
  94
  95 ``nsTHashMap`` is a template with two parameters. The first is the hash key
  96 and the second is the data to be stored as the value in the map. Most of
  97 the time, you can simply pass the raw key type as the first parameter,
  98 so long as its supported by `nsTHashMap.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsTHashMap.h>`_.
  99 It is also possible to specify custom keys if necessary. See `nsHashKeys.h
 100 <https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_ for examples.
 101
 102 There are a number of more esoteric hashkey classes in nsHashKeys.h, and
 103 you can always roll your own if none of these fit your needs (make sure
 104 you're not duplicating an existing hashkey class though!)
 105
 106 Once you've determined what hashtable and hashkey classes you need, you
 107 can put it all together. A few examples:
 108
 109 -  A hashtable that maps UTF-8 origin names to a DOM Window -
 110    ``nsTHashMap<nsCString, nsCOMPtr<nsIDOMWindow>>``
 111 -  A hashtable that maps 32-bit integers to floats -
 112    ``nsTHashMap<uint32_t, float>``
 113 -  A hashtable that maps ``nsISupports`` pointers to reference counted
 114    ``CacheEntry``\ s -
 115    ``nsTHashMap<nsCOMPtr<nsISupports>, RefPtr<CacheEntry>>``
 116 -  A hashtable that maps ``JSContext`` pointers to a ``ContextInfo``
 117    struct - ``nsTHashMap<JSContext*, UniquePtr<ContextInfo>>``
 118 -  A hashset of strings - ``nsTHashSet<nsString>``
 119
 120
 121 Hashtable API
 122 -------------
 123
 124 The hashtable classes all expose the same basic API. There are three
 125 key methods, ``Get``, ``InsertOrUpdate``, and ``Remove``, which retrieve entries from the
 126 hashtable, write entries into the hashtable, and remove entries from the
 127 hashtable respectively. See `nsBaseHashtable.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsBaseHashtable.h>`_
 128 for more details.
 129
 130 The hashtables that hold references to pointers (nsRefPtrHashtable and
 131 nsInterfaceHashtable) also have GetWeak methods that return non-AddRefed
 132 pointers.
 133
 134 Note that ``nsRefPtrHashtable``, ``nsInterfaceHashtable`` and ``nsClassHashtable``
 135 are legacy hashtable types which have some extra methods, and don't have automatic
 136 key type handling.
 137
 138 All of these hashtable classes can be iterated over via the ``Iterator``
 139 class, with normal C++11 iterators or using the ``Keys()`` / ``Values()`` ranges,
 140 and all can be cleared via the ``Clear`` method.