Saturday, October 8, 2016

HashTrie

Description:

Ever wonder how would one write a hash table in a pure functional programming settings? The simple answer is that you basically can't, because it relies critically on mutating the array. But if all we wanted is a data structure that can give expected $ O(1) $ access, then it is quite feasible.

The basic idea is to have a trie that store the hash code as if it is a binary string. Assuming a good hash function, that should give us the behavior we wanted. As an added advantage in the functional settings, one can easily make such a data structure persistent, meaning that we can go back in time to look at the data structure as we wished.

Code:

No comments :

Post a Comment