Difference between HashTable datastructure and Association datastructure

Question

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?

Answer 1

Summary

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

• associations are immutable whereas hash tables are mutable
• associations are hash array mapped tries as opposed to simple hash tables

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] // Internal`AssociationNodes // 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.

Answer 2

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

Answer 3

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.

2. 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.