Mathematica 9 is now available

Sparse arrays (hash tables)

Sparse arrays are quite simple, and are among the most heavily used of data structures in Mathematica (often without giving that name to them). One uses them to store values associated to "indices" attached to a given "head." But this head need not be an atom, and, unlike Mathematica part specifications, the indices need not be positive integers. When left-hand-sides of such indices are free of patterns, Mathematica will compute what is called a "hash value" for them; think of these as positive integers that can be used as an index into an actual table (more on this below).

Below we use the symbol a as a head for a sparse array defined for three particular indices.

[Graphics:../Images/index_gr_12.gif]
[Graphics:../Images/index_gr_13.gif]
[Graphics:../Images/index_gr_14.gif]
[Graphics:../Images/index_gr_15.gif]
[Graphics:../Images/index_gr_16.gif]

One might (and frequently will) choose to view such definitions as something other than a sparse array. For example, one often defines Mathematica functions in this way. But most often function definitions will rely on Mathematica patterns and this disqualifies them from being sparse arrays in an important aspect.. Specifically, it is only families of associated values free of patterns that may be hashed.  This is both because pattern matching relies heavily on technology that is intrinsically non-hashable and because rule ordering neecessary for pattern matching precludes look-up based on hashed values.

What is the benefit of these sparse arrays? It all boils down to efficiency. The Mathematica kernel will compute what is called a "hash value" for each left-hand-side, and use that to place it into an internal data structure with associated right-hand-value. While multiple left-hand-sides might have the same hash value and hence be placed in the same bin, the Mathematica kernel checks that bins do not grow too large,  rehashing to a larger space when need be. The upshot is that if we assume the computation of a hash value is constant time, then:
(i) Adding new elements to such a table is, on average, constant time.
(ii) Element look-up is, on average, constant time.
Hence we may use such arrays to store values and retrieve them quickly. Below we show simple implementations of a union that does not sort its elements. One uses Mathematica lists and the other uses a sparse array.

[Graphics:../Images/index_gr_17.gif]
[Graphics:../Images/index_gr_18.gif]

First we check that these give the same results.

[Graphics:../Images/index_gr_19.gif]
[Graphics:../Images/index_gr_20.gif]
[Graphics:../Images/index_gr_21.gif]

Now we check speed and algorithmic complexity.

[Graphics:../Images/index_gr_22.gif]

It is quite clear that unionNoSort1 has quadratic complexity whereas unionNoSort2 has only linear complexity.

There are two further observations to be made about this implementation of unsorted union. First, the semantics are not entirely the same as in Union because that latter will test equivalence using SameQ whereas unionNoSort2 relies on hash look-up. Second, in addition to hashing we make rudimentary use of a sort of "stack" by nesting the result we construct. We will cover this in more detail in the next section.

Application: sparse sets

One might use sparse arrays to represent sets with cardinality relatively small by comparison to the universe of allowable elements. We show a simple implementation of such sets, including functions to find unions, intersections and complements of pairs of such sets.

[Graphics:../Images/index_gr_23.gif]

Here we show some simple examples.

[Graphics:../Images/index_gr_24.gif]
[Graphics:../Images/index_gr_25.gif]
[Graphics:../Images/index_gr_26.gif]
[Graphics:../Images/index_gr_27.gif]
[Graphics:../Images/index_gr_28.gif]

We will use Mathematica built-in logical operations on the set elements in order to check our set functions for correctness.

[Graphics:../Images/index_gr_29.gif]
[Graphics:../Images/index_gr_30.gif]
[Graphics:../Images/index_gr_31.gif]
[Graphics:../Images/index_gr_32.gif]
[Graphics:../Images/index_gr_33.gif]
[Graphics:../Images/index_gr_34.gif]
[Graphics:../Images/index_gr_35.gif]
[Graphics:../Images/index_gr_36.gif]

It is easy to demonstrate that the average complexity for adding or removing elements is O(1) (that is, constant time), as expected.

[Graphics:../Images/index_gr_37.gif]
[Graphics:../Images/index_gr_38.gif]
[Graphics:../Images/index_gr_39.gif]
[Graphics:../Images/index_gr_40.gif]
[Graphics:../Images/index_gr_41.gif]
[Graphics:../Images/index_gr_42.gif]
[Graphics:../Images/index_gr_43.gif]
[Graphics:../Images/index_gr_44.gif]