, , , , , , , , ,

Course: Berkeley’s CS 61B: Data Structures.

Homework 6: Hash Tables, Hash Functions, Compression Functions

Homework 6 (mirror) is due before lecture 25: Binary Search Trees.

This assignment asks you to implement a Chained Hash Table, and create a Hash Function for a game board object. You get to re-use the solution of hw5 here to act as the Chained part of the Chained Hash Table.

My previous post, Hash Functions, Prime numbers, Compression Functions and HashGraph, revolves around this assignment’s topic and was in fact inspired by it.

Apart from HashGraph’s indication of ‘hits per bucket’, the collision probability function mentioned in the assignment’s spec is another good measure of testing how good a hash function is, so I implemented it in my test code for hw6. If the collisions met in your test results are close to the figure returned by the collision probability function then you have a sufficiently good solution.

Part 1: Implement HashTableChained

The one thing of interest here is the more sophisticated compression function mentioned in the spec. You can choose to use it, or not use it.

Only by writing sufficient test code to see how each behaves, can an informed decision be made. Some tests will behave equally well with either function, some will show significant improvement with the more sophisticated one.

The keyset and the hash function used makes a difference. It so happens that Java’s String class has a pretty good hashCode() method. So, testing with String keys and relying on the default hashCode() methods will not make the utility of the more sophisticated compression function apparent.

dict/HashTableChained.java (view | download)

Part 2: create a hash function for a game board object

I chose the simplest possible hash function here. My logic was simple, the game board’s tiles have an ‘alphabet’ of 3 characters (0, 1, 2), so use a hash function that has a constant of 3.

 hash = hash * 3 + value of tile;

This seems to work rather well with my tests.

SimpleBoard.java (view | download)

Test code

Writing test code is part of the assignment so the supplied Homework6Test.java leaves much to be desired.

My test extends HashTableChained.java with an investigate() method that, well, investigates.Tests are run using three different key types:

  • Strings (from two wordlists, one from cs50, another from cs106a).
  • Series of integers.
  • Randomized instances of SimpleBoard objects.
HashTest.java (view | download)
Here’s a sample output from HashTest: HashTestResults.txt

All of the above, and the dependencies: gotfu_hw6.zip