Algorithmic complexity of Data.Hashtable <p>I am attempting to write a function that utilizes hashes (for an implementation of A*).</p> <p>After a little bit of research, I have found that the defacto standard is <code>Data.Map</code>.</p> <p>However, when reading the API documentation, I found that: <code>O(log n). Find the value at a key.</code></p> <p><a href="https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html">https://downloads.haskell.org/~ghc/6.12.2/docs/html/libraries/containers-0.3.0.0/Data-Map.html</a></p> <p>In fact the documentation generally suggests big O times significantly inferior to the O(1) of a standard Hash.</p> <p>So then I found <code>Data.HashTable</code>. <a href="https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html">https://hackage.haskell.org/package/base-4.2.0.2/docs/Data-HashTable.html</a> This documentation does not mention big O directly, leading me to believe that it probably fulfills my expectations.</p> <p>I have several questions: 1) Is that correct? Is O(lookupInDataHashTable) = O(1)? 2) Why would I ever want to use <code>Data.Map</code> given its inefficiency? 3) Is there a better library for my data structure needs?</p>