Re: Better Hash Tables?

[Anonymous Monk]

IMO this doesn't apply to perl at all because the whole concept of this paper is based on having a fixed size array that you are finding an unoccupied slot to push into. This is really more useful in memory contained environments and hardware / logic design.

A recent example of this I faced is: I had 600million key:value records on disk. You cannot load these into a perl hash because of the memory requirements. However: You can store the disk offset in array, where the offset of the array is determined by hashing the key. This allows you to fit a hash table within a few gigabytes of RAM. To fetch an item you hash the key to get the offset, and jump to that offset to fetch the disk location and read the key:value and confirm the key.

The only question is: How big should the array be? If its close to 600m you are endlessly dealing with hash collisions. But if you make it bigger, say 1200million, half your RAM is wasted. If you have a hash collision, you have no option but to re-hash, which determines a new random position. To fetch, you have to try the first candidate, load from disk, and see if the key matched, else hash again and fetch the next candidate as there must have been a collision.

What this paper shows is that there is a better method than the above that can boost performance when the array is closer to 600m than simply randomly trying a new hash.

It would be useful in situations like mine, but I don't see how its useful to perl which has dynamical linked lists of variable size.