Sparse Arrays

Alright /proglodites/, let's hear how all of you implement a sparse arrays that stores two-dimensional data.

Radix trees are a good way to do this.

Assuming you want each cell in the grid to be indexable by two integers denoting the x and y positions, you can concatenate the bitstrings of the x and y locations and use that as the lookup key in a big radix tree. Each node in the radix tree holds an array of 2n pointers, where n is the number of bits to use as a lookup at each node. Anytime you come across a null pointer, you return the default value. This would allow dynamic use of memory and logarithmic lookups as opposed to linear ones.