Fast hash tables

The Dictionary class – a dead end for other targets

Recently I started to adjust my code with the C++ and JavaScript haXe target in mind. I have to say it’s really amazing to see your code running on different platforms. This offers an incredible amount of flexibility! While almost everything worked out of the box, the biggest hurdle was to find a replacement for the flash.utils.Dictionary class, which I was using extensively in my library.
Although the haXe API already offers a Hash and IntHash class (both using the Dictionary for the flash target), I’ve decided to implement my own hash tables so they blend in nicely into my ds library.

What are hash tables?

A hash table is a very important and fundamental data structure in computer science. It offers rapid insertion, access and deletion of sparse data. This is achieved by distributing the data amongst a fixed number of slots using a hash function.

There are many ways of implementing hash tables, but from my experience (and from reading dozens of papers) the easiest solution is something called a ‘standard-chain hash table’, which simply uses linked lists as a collision resolution scheme. When linked lists are replaced with dynamic arrays, the result is called an ‘array hash table’, which offers a smaller memory footprint because it eliminates nodes and pointers all together and is more cache friendly.

Other implementations include ‘bucketized cuckoo hash tables’ or ‘open-address hash tables’ using techniques like linear probing or double hashing for collision resolution. Those are interesting if you are into computer science, but from the point of view of a game programmer, they don’t offer any advantages, but have drawbacks of some kind (problems with high load factor, difficult to implement, complex hashing and so on).

The hash table implementation which I’ve included in the ds library is somewhere in between a standard-chain hash table and an array hash table – the data is stored in an array while still offering basic advantages of a linked list, namely removal in constant time and move-front-on-access by pointer manipulation.

So the procedure for searching a key in my code is:

  1. Hash the key to acquire a slot.
  2. Check if the slot is empty. If it’s empty, the key does not exist and the search fails.
  3. Otherwise scan the array a key at a time until a match is found or until the array is exhausted (search fails).
  4. If the key was found, move it to the front of the list by pointer manipulation. This way further queries to the same key take less time (optional).

Implementation overview

The latest version of my ds library now contains a bunch of additional interfaces and classes:
Classes implementing de.polygonal.ds.Map:

  • IntIntHashTable – A hash table using 32-bit integers for both keys and values.
  • IntHashTable<T> – A generic hash table using 32-bit integer keys.
  • HashTable<K, T> – A generic hash table. Keys have to implement Hashable.
  • HashMap – The existing wrapper for the Dictionary class, which was updated so it now implements Mapinstead of Collection. Flash only!

Classes implementing de.polygonal.ds.Set:

  • IntHashSet – Similar to IntIntHashTable, this is a set for integer values.
  • HashSet<T> – A generic set. Values have to implement Hashable.
  • ListSet<T> – A simple set backed up by a list; this is a replacement for the former Set class that now defines an interface.

IntIntHashTable and IntHashSet are the most important ones since they provide the core functionality used in other classes. IntHashTable, HashTable and HashSet extend their behavior via composition.

The core classes use ‘alchemy’ memory and lots of inlining to achieve very good performance. I’ve documented all classes, and I hope it’s not that difficult to understand. Some notes:

  • Although hash tables implement a Map interface, they allow multiple entries of the same key following the FIFO rule. If you want to make sure that the hash table contains unique keys, use the setIfAbsent(key, val) method or manually check for existence using hasKey(key) before calling set(key, val). Example:
    //duplicate key
    var hash = new IntIntHashTable(1024);
    hash.set(1, 2);
    hash.set(1, 3);
    trace(hash.hasKey(1)); //true
    trace(hash.get(1)); //2
    trace(hash.hasKey(1)); //true
    trace(hash.get(1)); //3
    //ensure unique keys
    var success = myHashTable.setIfAbsent(1, "value1"); //success == true
    var success = myHashTable.setIfAbsent(1, "value2"); //success == false
    if (!myHashTable.hasKey(1)) myHashTable.set(1, "value");
  • As you know, the Dictionary lets you use the object ‘identity’ as a key, and not the value returned from calling toString() on it. This behavior is not available in JavaScript and other targets. So objects used as keys in a HashTable or as values in a HashSet have to implement the Hashable interface or extend from the abstract class HashableItem. Hashable defines a single method getKey() (or just a field key if using haXe) returning an unique integer value to identify the object. This is a little awkward, but I currently don’t see any other (simple) solution. Example:
    class Foo implements Hashable {
      public var key(default, null):Int;
      public function new() { key =; }
    class Foo extends HashableItem {
      public function new() { super(); }
    var item = new Foo();
    myHashTable.set(foo, "myValue");
  • For the AS3 users out there, I’m providing the following swc files (xxx stands for debug or release):
    • ds_xxx_alchemy.swc: ds version with alchemy support for FP10.
    • ds_xxx_.swc: ds version without alchemy support but using Vectors for FP10.
    • ds_xxx_fp9.swc: ds version without alchemy support but using Arrays for FP9.

    When using the alchemy version, it’s important to call free() to release all used memory once the object is no longer needed.

The Dictionary class

If you want to take a look at the hash table implementation used in the Dictionary, you can do so by downloading the Tamarin source code and open the file core/MultinameHashtable.cpp or core/avmplusHashtable.cpp. From my understanding (please correct me if I’m wrong!) flash uses an open-addressed hash table with quadratic probing for resolving collisions. This means that keys are directly stored within hash slots, while my hash table is open: in the case of a hash collision, a single slot stores multiple entries, which must be searched sequentially. Also the Tamarin implementation automatically rehashes the hash table when it’s full (load factor > 0.75), while I’m only allocating more capacity and leave rehashing to the user, because it’s an expensive operation and performance only slightly degrades when the load factor goes beyond one.


So here are the numbers for the IntIntHashTable. All results were done with the latest Flash Player for Windows. You can compile & run the benchmark on your own, but I guess you have to adjust the number of iterations or you get a script timeout.

The chart below shows how the HashTable behaves when a slot contains more than one key. A load factor of 1 means that each slot contains only one key/value pair. A load factor of 2 means each slot has two pairs that have to be searched sequentially and so on.

hash table benchmark

So it’s very predictable. A load factor of 10 makes the hash table 10x slower.

The chart and table below compares read/write/access operations between a IntIntHashTable and the Dictionary. Both structures are preallocated to minimize the time it takes to find a key.

hash table benchmark

size 1024 2048 4096 8192 16384 32768 65536 131072
IntIntHashTable 0,08 0,14 0,29 0,57 1,15 2,29 4,75 10,03
Dictionary 0,84 1,54 3,3 6,7 16,5 44,76 97,72 218,32
x times faster 10x 11x 11x 11x 14x 19x 20x 21x

The last chart compares the generic HashTable implementation against the Dictionary class. The difference is not too big, still the HashTable is about 20-30% faster.

hash table benchmark

size 1024 2048 4096 8192 16384 32768 65536 131072
HashTable 0,28 0,57 1,15 2,3 4,7 9,28 20,55 39,45
Dictionary 0,37 0,72 1,35 2,73 5,6 13,48 27,45 52,48
x times faster 1,32x 1,26x 1,17x 1,19x 1,19x 1,45x 1,34x 1,33x


While in most cases you won’t notice a big difference I have some applications in mind like hierarchical spatial hash tables for collision pruning where the extra speed should be very noticeable. So what’s next for ds? Probably a deque structure and lots of bug fixing of course ;).