You would probably be quite interested in Nievergelt's [Grid File](https://en.wikipedia.org/wiki/Grid_file). It's like your Hash Space but has per-axis indices which let you subdivide the grid where it is densely populated. So, it works better for highly non-uniform distributions.
Scalability-wise, the typical description/impl and probably good enough for intermediate scale uses just a linear array on each axis with binary search and memory shifting insert/delete. However, one could certainly instead use a binary tree or B-tree for those axes.
