Re: [Haskell-cafe] can there be (hash-table using) O(n) version of this (I think currently) n log n algo?

However you can use the wider idea of hashing: A nesting of two finite maps. One fast, but approximative map. And one slow, but exact map. The quintessential example is an array indexed with some hash function for the first map. And linked lists of (key,value) pairs as the latter. In Haskell you might want to use IntMap and a the mentioned list of pairs (combined with the lookup functions from Data.List). Of course you need to supply a function to hash your keys to Int for the IntMap.