1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
XPCOM Hashtable Guide
=====================
.. note::
For a deep-dive into the underlying mechanisms that power our hashtables,
check out the :ref:`XPCOM Hashtable Technical Details`
document.
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 | *any type:* almost |
| | are always keyed on | any datatype can be |
| | integers and must | used as key, |
| | be contiguous. | 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 | *O(1):* lookup time |
| | is a simple constant | is mostly-constant, |
| | | but the constant |
| | | time can be larger |
| | | than an array lookup |
+-------------------------+----------------------+----------------------+
| **Sorting** | *sorted:* stored | *unsorted:* stored |
| | sorted; iterated | unsorted; cannot be |
| | over in a sorted | iterated over in a |
| | fashion. | sorted manner. |
+-------------------------+----------------------+----------------------+
| **Inserting/Removing** | *O(n):* adding and | *O(1):* adding and |
| | removing items from | removing items from |
| | a large array can be | hashtables is a |
| | time-consuming | quick operation |
+-------------------------+----------------------+----------------------+
| **Wasted space** | *none:* Arrays are | *some:* hashtables |
| | packed structures, | are not packed |
| | so there is no | structures; |
| | wasted space. | 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.3F:
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.3F:
Which Hashtable Should I Use?
-----------------------------
If there is **no** key type, you should use an ``nsTHashSet``.
If there is a key type, you should use an ``nsTHashMap``.
``nsTHashMap`` is a template with two parameters. The first is the hash key
and the second is the data to be stored as the value in the map. Most of
the time, you can simply pass the raw key type as the first parameter,
so long as its supported by `nsTHashMap.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsTHashMap.h>`_.
It is also possible to specify custom keys if necessary. See `nsHashKeys.h
<https://searchfox.org/mozilla-central/source/xpcom/ds/nsHashKeys.h>`_ for examples.
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 -
``nsTHashMap<nsCString, nsCOMPtr<nsIDOMWindow>>``
- A hashtable that maps 32-bit integers to floats -
``nsTHashMap<uint32_t, float>``
- A hashtable that maps ``nsISupports`` pointers to reference counted
``CacheEntry``\ s -
``nsTHashMap<nsCOMPtr<nsISupports>, RefPtr<CacheEntry>>``
- A hashtable that maps ``JSContext`` pointers to a ``ContextInfo``
struct - ``nsTHashMap<JSContext*, UniquePtr<ContextInfo>>``
- A hashset of strings - ``nsTHashSet<nsString>``
.. _nsBaseHashtable_and_friends:_nsDataHashtable.2C_nsInterfaceHashtable.2C_and_nsClassHashtable:
Hashtable API
-------------
The hashtable classes all expose the same basic API. There are three
key methods, ``Get``, ``InsertOrUpdate``, and ``Remove``, which retrieve entries from the
hashtable, write entries into the hashtable, and remove entries from the
hashtable respectively. See `nsBaseHashtable.h <https://searchfox.org/mozilla-central/source/xpcom/ds/nsBaseHashtable.h>`_
for more details.
The hashtables that hold references to pointers (nsRefPtrHashtable and
nsInterfaceHashtable) also have GetWeak methods that return non-AddRefed
pointers.
Note that ``nsRefPtrHashtable``, ``nsInterfaceHashtable`` and ``nsClassHashtable``
are legacy hashtable types which have some extra methods, and don't have automatic
key type handling.
All of these hashtable classes can be iterated over via the ``Iterator``
class, with normal C++11 iterators or using the ``Keys()`` / ``Values()`` ranges,
and all can be cleared via the ``Clear`` method.
|
