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).
