top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Why we are always prefer implementing the Hashkell maps as balanced binary trees instead of traditional hashtables?

+2 votes
315 views
Why we are always prefer implementing the Hashkell maps as balanced binary trees instead of traditional hashtables?
posted Sep 24, 2013 by Vivek Singh

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+3 votes

Hash tables can not be implemented efficiently without mutable state bcoz they are based on array lookup. The key is hashed and the hash determines the index into an array of buckets. Without mutable state, inserting elements into the hashtable becomes O(n) bcoz the entire array must be copied. Binary-tree implementations can share most of their structure so only a couple pointers need to be copied on doing inserts.

Haskell certainly can support traditional hash tables provided that the updates are in a suitable monad. The hashtables package is probably the most widely used implementation.

One advantage of binary trees and other non-mutating structures is that they are persistent: it is possible to keep older copies of data around with no extra book-keeping. This might be useful in some sort of transaction algorithm for example. They are also automatically thread-safe (although updates won't be visible in other threads).

answer Sep 25, 2013 by Arvind Singh
...