[Haskell-cafe] Very imperfect hash function
haberg at math.su.se
Thu Jan 28 14:41:20 EST 2010
On 28 Jan 2010, at 20:07, Steve Schafer wrote:
> The data are currently in a large lookup table. To save space, I'd
> to convert that into a sort of hash function:
> hash :: key -> value
> My question is this: Is there any kind of generic approach that can
> use of the knowledge about the internal redundancy of the keys to come
> up with an efficient function?
There are minimal perfect hash functions; there are some libraries
mentioned here, though they are not in Haskell code:
This is suitable when you do a lot of lookups with few key updates. An
alternative might be Data.Map, where lookups have time complexity
O(log n), n = size of map.
More information about the Haskell-Cafe