Menu
Is there any way to implement hash tables efficiently in a purely functional language? It seems like any change to the hash table would require creating a copy of the original hash table. I must be missing something. Hash tables are pretty darn important data structures, and a programming language would be limited without them.
289
Hashing is implemented in two steps: An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table. The element is stored in the hash table where it can be quickly retrieved using hashed key.
Take an array and use the hash function to hash the 26 possible characters with indices of the array. Then iterate over S and increase the value of the current character of the string with the corresponding index for each character. The complexity of this hashing approach is O(N), where N is the size of the string.
You can implement a Hash Table in JavaScript in three steps: Create a HashTable class with table and size initial properties. Add a hash() function to transform keys into indices. Add the set() and get() methods for adding and retrieving key/value pairs from the table.
Is there any way to implement hash tables efficiently in a purely functional language?
Hash tables are a concrete implementation of the abstract "dictionary" or "associative array" data structure. So I think you really want to ask about the efficiency of purely functional dictionaries compared to imperative hash tables.
It seems like any change to the hash table would require creating a copy of the original hash table.
Yes, hash tables are inherently imperative and there is no direct purely functional equivalent. Perhaps the most similar purely functional dictionary type is the hash trie but they are significantly slower than hash tables due to allocations and indirections.
I must be missing something. Hash tables are pretty darn important data structures, and a programming language would be limited without them.
Dictionaries are a very important data structure (although its worth noting that they were rare in the mainstream until Perl made them popular in the 1990s, so people coded stuff for decades without benefit of dictionaries). I agree that hash tables are also important because they are often by far the most efficient dictionaries.
There are many purely functional dictionaries:
Balanced trees (red-black, AVL, weight-balanced, finger trees etc.), e.g. Map in OCaml and F# and Data.Map in Haskell.
Hash tries, e.g. PersistentHashMap in Clojure.
But these purely functional dictionaries are all much slower than a decent hash table (e.g. the .NET Dictionary).
Beware Haskell benchmarks comparing hash tables to purely functional dictionaries claiming that purely functional dictionaries are competitively performant. The correct conclusion is that Haskell's hash tables are so inefficient that they are almost as slow as purely functional dictionaries. If you compare with .NET, for example, you find that a .NET Dictionary can be 26× faster than Haskell's hash table!
I think to really conclude what you're trying to conclude about Haskell's performance you would need to test more operations, use a non-ridiculous key-type (doubles as keys, what?), not use
-N8for no reason, and compare to a 3rd language that also boxes its parametric types, like Java (as Java has acceptable performance in most cases), to see if its a common problem of boxing or some more serious fault of the GHC runtime. These benchmarks are along these lines (and ~2x as fast as the current hashtable implementation).
This is exactly the kind of misinformation I was referring to. Pay no attention to Haskell's hash tables in this context, just look at the performance of the fastest hash tables (i.e. not Haskell) and the fastest purely functional dictionaries.
163
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
