Re: Hash tables

> 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

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