For the curious, that sparse-dense array construction of mratsim's impl is
useful when keys are sparse-subsets of a small universe and hails from Preston
Briggs' Rice PhD thesis in 1992, but has this more self-contained follow-up
paper:
[http://dcs.gla.ac.uk/~pat/ads2/papers/p59-briggs%5b1%5d.pdf](http://dcs.gla.ac.uk/~pat/ads2/papers/p59-briggs%5b1%5d.pdf)
If you need this to be an "associative array" with "satellite data" as values
for given keys, that is a straightforward extension where the dense array can
be an array of pairs (or you could have a parallel dense value array).
At some slightly different point in the design space is Varghese's Aggregate
Bit Vectors which do not allow associative extension,
[https://cseweb.ucsd.edu/~varghese/PAPERS/icnp2002.pdf](https://cseweb.ucsd.edu/~varghese/PAPERS/icnp2002.pdf)
, which is also pretty easy to implement.
And, of course, `Table[int,int]` is not actually that slow either.
