Re: Hash tables

C <>
2 Oct 2004 16:22:31 -0400

          From comp.compilers

Related articles
Hash tables (2004-10-02)
Re: Hash tables (2004-10-02)
Re: Hash tables (C) (2004-10-02)
Re: Hash tables (2004-10-04)
Re: Hash tables (John Slimick) (2004-10-04)
| List of all articles for this month |

From: C <>
Newsgroups: comp.compilers
Date: 2 Oct 2004 16:22:31 -0400
Organization: NTL
References: 04-10-011
Keywords: performance
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
> 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.


Post a followup to this message

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