Hash Tables


PowerPoint presentations:  Locally maintained    From another text book   Koffman&Wolfgang, Ch. 9     Sahni’s Lecture 16  Sahni’s Lecture 17
Slide for Sahni's Lecture 17

Topic coverage in lecture will be based on the above PowerPoint presentations — Sedgewick’s Chapter 14 (Hashing) goes into significantly more detail that we will be doing.  Sedgewick’s code for Chapter 14 is available through this link.

Note:  Sahni, in his implementations, makes the client of the hash table responsible for the hash key — the hash table receives two parameters, "public Object put(Object theKey, Object theElement)", and the array subscript is determined by "Math.abs(theKey.hashCode()) % divisor".  Note that in the programming assignment, you are expressly forbidden from using java.lang.Object.hashCode() or its overriden version in a subclass.        Sahni’s hash table using linear open addressing and division  [.txt]       Slightly edited version of the above for class discussion.  [.txt]  [.rtf]      Sahni’s hash table using linked lists / chains  [.txt]   Note:  this requires      Bundle of HashChains and SortedChain.  Output from running the program      Demonstration of Horner’s method to generate a String hashCode.   [.txt]    [.exe]     Demonstration program:  for the current class, generate two hash values (from EWUID and lastName.hashCode())
StudentHash.txt        Same as a .txt file
Roster37.txt             Results if the hash table has size 37
Roster31.txt             Results if the hash table has size 31
Roster29.txt             Results if the hash table has size 29
Roster23.txt             Results if the hash table has size 23
Roster19.txt             Results if the hash table has size 19

AlphaZulu.html        Another example:  alpha/bravo/charlie/.../zulu, with linear probe statistics
ArmyNavy.html       Yet another:  able/baker/charlie/.../zebra, with linear probe statistics

Hash Table Drill Program — this uses open addressing / linear probing to handle hash function collisions

 * Hash table drill program.
 * Generate 10 random values with a random number of digits:
 * between 1 and 4 digits.
 * Within each number, the highest-order digit is d1, and the
 * lowest order digit is d0.
 * Hash functions currently available:
 *    option 0:  (d1*10 + d0) % size
 *    else:      (d1 * d0) % size
 * Language:  Java version 5 --- uses Scanner and printf
 * Author:  Timothy Rolfe
 */     Java program  —  the same thing as a .txt file
HashDrillJ.exe     Executable wrapper for the jar file

HashDrill.c         Translated into C — DOS window resized via “mode con lines=43
HashDrill.exe      Executable file (under Windows)

Link to the assignment exercising a hash table