I saw the question somewhere "Binary tree vs hash table, which one is better?"

And then I thought - "Why not both? Why not combine the two and create a binary tree where each node contains a 'number' that is actually a hash of a string or other type of data?"

Not exactly sure if the Merkle tree is the same thing.

  • $\begingroup$ Actually, now that I think of it, if I invented this design, I invented the worst design ever. Problem # 1: Good luck removing ONE node without having to rearrange everything else. Problem # 2: All that overhead for what? Slightly faster lookup time? $\endgroup$ – Stephanus Tavilrond Mar 23 '18 at 6:26

You would have invented hash trie, a functional data structure.

The Achilles' heel of hash table is that it requires modifying an array entry (or insert to the overflow list) by modifying it. This is not functional language friendly.

But we still love to have the expected constant time lookup/insert/remove, so we compute the hash code of the item as usual, and then we insert it into a binary tree by following the binary digits. For example, '0' goes left and '1' goes right.

But isn't inserting into a binary tree also a modification - yes, it could be - but with smartness, one can simply return a clone of the node with a new sub-tree, that way we can avoid the problem of modification by returning a new tree instead. If we use the same trick for the hash table, we would have to copy the hash table, but all we have to do now is to clone the path (which is a constant size)

No modification turns out is a big deal even without the constraint of functional languages. For example, such a data structure is "persistent", if you are willing to save all the previous versions, we can go back in time to see what it was. We can also freely parallelize it because all memories are write only once and stay there forever (until it is garbage collected of course)

Merkle tree is not the same thing.

| cite | improve this answer | |

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.