4 Oct 2004 00:52:44 -0400

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) |

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.