Re: Hash tables

John Slimick <slimick@venango.upb.pitt.edu>
4 Oct 2004 00:52:44 -0400

          From comp.compilers

Related articles
Hash tables victor@eijkhout.net (2004-10-02)
Re: Hash tables nmm1@cus.cam.ac.uk (2004-10-02)
Re: Hash tables cc-news@hermes.mirlex.com (C) (2004-10-02)
Re: Hash tables vbdis@aol.com (2004-10-04)
Re: Hash tables slimick@venango.upb.pitt.edu (John Slimick) (2004-10-04)
| List of all articles for this month |

From: John Slimick <slimick@venango.upb.pitt.edu>
Newsgroups: comp.compilers
Date: 4 Oct 2004 00:52:44 -0400
Organization: University of Pittsburgh
References: 04-10-011 04-10-027
Keywords: design
Posted-Date: 04 Oct 2004 00:52:43 EDT

> Victor Eijkhout <victor@eijkhout.net> 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.


I have always preferred open hash ("chaining", "hash buckets"), and,
except in cases where memory was at premium, I have never found a
reason to use closed hashing instead of open.


In my data structures course when I talk about hashing, I feature
open, along with one closed and one extensible method. But like the
countless sorting algorithms that populate data structures textbooks
these days, it seems that one must include several closed
methods. Apart from showing off what the computational complexity
people can do with algorithms, I can't think of a single reason to
spend time on:


                Random rehash
                Add-the-hash rehash
                Quadratic hashing
                etc.


What I focus on these days is how to construct a hash computation. In
my lecture notes for the Data Structures course I give at least three
with examples, as well as three others, plus a note for the SHA.


john slimick
slimick@pitt.edu


Post a followup to this message

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