Have two responsibilities:
- storing data efficiently
- performing queries/updates efficiently.
Hashmaps do not make for a particularly elegant solution to these two problems.
HashMaps become less efficient the more dense they become, so an hashmap optimal for retrieval is more than sub-optimal for storage.
Conversely a dense hashmap is also called a bag, great for storage, horrible for searching.
Worse than this, consider scaling a hashmap up to gigabytes (or larger). Presume that the whole map cannot simply be stored in main memory so scale it to be larger than your machines abilities. This means that some portion of the map is on a slower storage medium.
There are only a limited number of slots in each page of memory. Depending on this number and the amount of cells skipped by a hash collision each page loaded may only be tested once (or in the single digits) for slots to store or search through. This will cause more pages to be loaded without the guarantee that the page actually contains something useful (like an empty slot, or the searched for item).
The total number of pages loaded can be somewhat optimised by expending even more space to hold another datastructure (like a different hashmap, tree, or a list) that stores all of the elements whose hash collided.
To compound all of that, hashmaps are horrible for range based searches. You either have to:
- generate each item in the range being queried and then individually hash and search for each of them.
- treat the entire hashmap as a bag and check every slot to see if it has an element, and then if that element is a match for the query.
Both are slow algorithms.
Compare this to a balanced tree.
A Balanced Tree can be organised very efficiently in memory as an array. You just need a good mapping such as Russ Cox describes. This actually serves to make the tree even more memory dense without sacrificing search speed. It may actually improve the speed under some architectures.
The tree structure (particularly as an array) even plays very nicely with memory pages. As it allows you to load exactly those pages which are needed to satisfy the query.
Additionally (as an arranged array) the data structure supports fast neighbour and range queries.
- Simply find the first and last element in the range and every element between those is also a match.
- Find the element and look forward and backward in the array for its neighbours.
That isn't to say that hash maps have no place in a data store, they are ideal for memoisation of results in a cache to amortise repetitive queries.
But as a storage mechanism they do not stack up against a tree, particularly once data has to be paged to disk. And as a query mechanism hash maps do not support range and neighbourhood searches.