Difference between HashTable datastructure and Association datastructure

Is there a difference in the runtimes between CreateDataStructure["HashTable"] and <||> in terms of inserting, removing, retrieving etc?

Why do both of these exist? Why would I ever use HashTable with extremely ugly syntax?

• Not exactly answering your question, but I think the main difference is that Associations keep the order of the entries, so they probably are more like CreateDataStructure["OrderedHashTable"]. Any performance differences might well be related to that detail... Oct 31 '21 at 10:52

3 Answers

Summary

Important differences between Association and CreateDataStructure["HashTable"] include:

Mutability

As a rule, Wolfram Language's native data structures are immutable. Any attempt to change even just a part of a structure causes a new copy to be allocated. If a target variable is assigned from a source variable containing a structure, the target variable gets its own copy (although internally there are optimization tricks like copy-on-write and structure-sharing).

In contrast, the data structures created by CreateDataStructure are mutable. If a part of the structure is changed, the structure is destructively altered. Furthermore, multiple variables can share references to that structure and all will see such changes.

Some simple experiments illustrate the difference.

We assign a new association to $a1 and copy it into $a2:

$a1 = <| "x" -> 1, "y" -> 2 |>;$a2 = $a1;  Then we change the "x" component of $a1:

$a1["x"] = 999;  Even though $a1 has been changed, $a2 has not and neither even has the original association that was assigned to $a1 in the first place:

$a1 (* <| "x" -> 999, "y" -> 2 |> *)$a2
(* <| "x" -> 1, "y" -> 2 |>  *)

Out[-5]
(* <| "x" -> 1, "y" -> 2 |>  *)


Now in contrast we can see that if the same sequence of events takes place using a hash table, all references point to the same table and all see the change... no copies are made:

$$ht1 = CreateDataStructure["HashTable"];$$ht1["Insert", "x" -> 1];
$ht1["Insert", "y" -> 2]; $$ht2 =$$ht1;$ht1["Insert", "x" -> 999];

$ht1["Lookup", "x"] (* 999 *)$ht2["Lookup", "x"]
(* 999 *)

Out[-7]["Lookup", "x"]
(* 999 *)


Structural Differences

Internally, the two data structures are quite different. Associations are hash array mapped tries whereas hash tables are, well, simple hash tables.

It is for immutability reasons that associations are not implemented by means of simple hash tables. Since an association must be copied every time even a single subcomponent value is changed, the overhead can be very large for large associations. A hash array mapped trie is a persistent data structure that arranges for mutated copies of a structure to share unchanged portions with the original.

Simple hash tables do not have this property. That makes them unsuitable for implementing the core immutable semantics of Wolfram Language's native data structures.

The following visualizations give a sense of the structural differences:

$pairs = # -> 10 # & /@ Range[10]; Association[$pairs] // InternalAssociationNodes // ExpressionGraph


$ht = CreateDataStructure["HashTable"]; Scan[$ht["Insert", #] &, $pairs];$ht["Visualization"]


Conclusion

Wolfram Language emphasizes immutability in support of its preferred rule-based rewriting and functional programming styles. But mutability is presumed in much discussion and application of classical computer science data structures. The CreateDataStructure functionality makes it much easier to express programming paradigms that depend upon mutability.

• Is it true that "an association must be copied every time even a single subcomponent value is changed"? If that were true then adding a new key-value pair to an association would be as costly as calling AppendTo on a list. Oct 31 '21 at 21:03
• @JasonB. It is true. But unlike in the case of an array, the entire structure does not need to be copied. Only a portion of the trie needs to be copied, namely the branch nodes that lead to the changed component. The rest of the trie can be reused. This can be a significant saving as a trie gets larger. In the worst case it is like AppendTo but the cost is usually reckoned as "amortized constant time" (I think log(n) is closer to the truth, but for a large base so I guess it is near enough to constant time for practical purposes). Oct 31 '21 at 22:41

HashTable seems a bit slower in creating, probably due to compiling, than Association:

n = 10^6;
ht["Insert", # -> 2 #] & /@ Range[n]; // Timing
(*{1.5625, Null}*)
as = Association[  Table[i -> 2 i, {i, n}]  ]; // Timing
(*{0.96875, Null}*)


For retrieving there is no big difference, HashTable is slightly faster:

n = 10^6;
ht["Lookup", #] & /@ Range[n]; // Timing
(*{0.42187,Null}*)
as /@ Range[n]; // Timing
(*{0.5312,Null}*)


All in all, I do not see a big difference between both methods

• Use AbsoluteTiming instead of Timing, and use as /@ Range[n] instead of as[[#]]& /@ Range[n] because Part is slower than Lookup Oct 31 '21 at 12:37
• You are right, Part slows it down. I corrected my answer. However, I think Timing is the right thing to use, if other jobs run, AbsoluteTiming may give the wrong answer. Oct 31 '21 at 13:31
• Timing may give the wrong answer, if you have more than one core. For more debate, see mathematica.stackexchange.com/questions/14152/… Oct 31 '21 at 19:17

Thanks to the people who gave answers, but I thought I could be more succinct. There are 2 differences:

1. immutability of <||>, which makes adding/deleting on an association a little slower.

Immutability is not implemented in Mathematica as naively as copying the entire structure every time we add something to the association, but some extra work needs to be done, and it seems as a result it is still slightly slower to add/remove from an association (but the convenience outweighs the very small difference in my opinion). Note that immutability is also why using a bunch of AppendTo's on a list can be EXTREMELY slow compared to using Table[] to make the list.

1. Associations keep the order of items, in addition to their hashes. For example, <|"a"->3|>[[1]] evaluates to 3. I don't think this makes much of a difference for lookup times.

See the given answers/comments for some good info which helped me write the above.

• I mean also Association is natively supported at top level as a first-class construct and the other is behind the DataStructre` machinery Nov 3 '21 at 5:57