1

I was watching the Coursera algorithms lecture series' portion on tries. R-way tries are introduced first, where each node has an array the size of the possible character space (R) with potential children -- for instance, an ASCII R-way trie would need 256-element arrays. It is then explained that for many applications, such as Unicode strings, this approach is prohibitively expensive in terms of memory.

I imagined the suggested change would be using a hashmap rather than an array -- something real-world implementations do seem to do from a quick search -- but instead a ternary search trie was introduced, using a strategy something like a binary tree, where new nodes might go to the left, right, or center of an existing one, depending on comparison.

What is the advantage of this somewhat less obvious approach? Is it reduced memory consumption because you're avoiding constructing so many hashmaps? Would the hashmap-based r-way trie be preferable in some situations?

2

Data Stores

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.