|Hash tables email@example.com (2004-10-02)|
|Re: Hash tables firstname.lastname@example.org (2004-10-02)|
|Re: Hash tables email@example.com (C) (2004-10-02)|
|Re: Hash tables firstname.lastname@example.org (2004-10-04)|
|Re: Hash tables email@example.com (John Slimick) (2004-10-04)|
|Date:||2 Oct 2004 16:22:31 -0400|
|Posted-Date:||02 Oct 2004 16:22:31 EDT|
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
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
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.
Return to the
Search the comp.compilers archives again.