Re: Hash tables

Victor Eijkhout wrote:


> Knuth (AoCP 6.4) more or less waves away the `open hashing' strategy,
> where you resolve conflicts by allocating a linked list outside the hash
> table. He devotes almost all of that section to `closed hashing',
> investigating linear probing and chaining as ways of storing the
> conflicting items elsewhere in the table.
>
> Personally, I don't see the problem with open hashing.


Me neither, most of my tools use some form of open hashing, though I
normally use a binary tree rather than a linked list. Though I have
not read AoCP, maybe Knuth ignored this more because it is trivial to
implement and largely covered in other areas of the book?


[ He covers both in section 6.4. -John]


> So, was closed hashing born of necessity in the days when memory was
> at a premium and you needed to keep track of every last byte
> yourself?


Well, closed hashing does use less memory, but this is only a matter
of between one and three pointers -- I doubt anyone would quibble over
a few bytes on a modern PC. (Incidentally my solution typically uses
three pointers; the hash table being a list of pointers and two for
the binary tree -- this is necessary as the objects hashed are of
variable size.)


On the other hand, where a hash table is likely to be sparse closed
hashing is a better solution as collisions are likely to be rare
anyway. Finally in some embedded systems where memory is at a
premium, such solutions may be necessary.


As to what I would use, well as with any algorithm, it depends
entirely on the data I expect to be processed.


C
2004-10-02

Return to the comp.compilers page.
Search the comp.compilers archives again.