COMP 9024, Assignment 4, 11s2
John Plaice
Wed Oct 19 09:57:50 EST 2011
You are to implement a perfect hash table according to the specification given below.
To find out the details of how perfect hash tables and universal hashing works, see the
definitions in the course notes in file class8.pdf.
You are to write two files, and then you will submit the using the following command.
give cs9024 assn4 HashUniversalTableMap.java HashPerfectTableMap.java
The submission is due Monday, 24 October, 08:00:00.
All submitted Java files should begin with the line
package chapter9;
and should import the class6 and class8 types as needed.
In order to do this assignment, you can look at file chapter9/HashTableMap.java for
inspiration. In that file, you can see
• HashTableMap implements Map.
In this assignment, the setup will be:
• HashUniversalTableMap implements Map.
• HashPerfectTableMap implements Map.
1 HashUniversalTableMap.java
The HashUniversalTableMap class is a hash table using universal hashing.
There are five fields:
protected int m;
protected int p;
protected int a;
protected int b;
protected ArrayList>[] table;
1
where
• m is the number of slots in the table;
• p is a large prime number;
• a is a number between 1 and p-1, inclusive;
• b is a number between 0 and p-1, inclusive;
• table is a table of size m of buckets, each a list of entries.
You will write a nested class as follows:
protected static class MyEntry implements Entry { ... }
You may adapt the one in HashTableMap.java as needed.
The functionality that you must provide is:
public HashUniversalTableMap
(int m_in, int p_in, int a_in, int b_in) { ... }
public void checkKey(K key) throws InvalidKeyException { ... }
public int hashValue(K key) { ... }
public int size() { ... }
public boolean isEmpty() { ... }
public V get(K key) throws InvalidKeyException { ... }
public V put(K key, V value) throws InvalidKeyException { ... }
public V remove(K key) throws InvalidKeyException { ... }
public Iterable keySet() { ... }
public Iterable values() { ... }
public Iterable> entrySet() { ... }
public String toString() { ... }
public ArrayList> getBucket(int bucket) { ... }
• There is no default constructor:
public HashUniversalTableMap() { ... }
• The method checkKey raises an exception if the key is null.
• The value returned by get is the current value for that key, if it exists, null otherwise.
• The value returned by put is the previous value for that key, if it existed, null
otherwise.
• The string generated for toString would look something like this:
2
Universal(11,41,13,14)[
1:[3 7]
3:[4 8]
5:[1 5]
7:[2]
8:[9]
10:[6]
]
Here m = 11, p = 41, a = 13, b = 14, bucket 1 contains keys 3 and 7, bucket 3
contains keys 4 and 8, bucket 5 contains keys 1 and 5, bucket 7 contains key 2,
bucket 8 contains key 9, and bucket 10 contains key 6.
2 HashPerfectTableMap.java
The HashPerfectTableMap replaces the definition of table. Instead of each slot being a
ArrayList, it becomes a HashUniversalTableMap.
The functionality that you must provide is:
public HashPerfectTableMap
(int m_in, int p_in, int a_in, int b_in,
Iterable> entries) { ... }
public void checkKey(K key) throws InvalidKeyException { ... }
public int hashValue(K key) { ... }
public int size() { ... }
public boolean isEmpty() { ... }
public V get(K key) throws InvalidKeyException { ... }
public Iterable keySet() { ... }
public Iterable values() { ... }
public Iterable> entrySet() { ... }
public String toString() { ... }
All of the entries are passed as an input to the constructor. There is no put or remove, as
the data structure cannot be modified once it is created.
3 Modifications to specification
These modifications are dated 19 October, 2011.
• The due date has been changed to Monday, 24 October, 08:00:00.
• In both classes, method
3
public Iterable valueSet() { ... }
should read
public Iterable values() { ... }
• For class HashUniversalTableMap, add the following method
public ArrayList> getBucket(int bucket) { ... }
• The example output for HashUniversalTableMap has been corrected. It is
Universal(11,41,13,14)[
1:[3 7]
3:[4 8]
5:[1 5]
7:[2]
8:[9]
10:[6]
]
• The output from toString() for HashPerfectTableMap should be of the following
form (here m = 19, p = 41, a = 20, b = 17, and the entered keys are 1 through 14).
Perfect(19,41,20,17)[
10:
Universal(1,41,1,0)[
0:[14]
]
11:
Universal(1,41,1,0)[
0:[12]
]
12:
Universal(4,41,1,0)[
1:[13]
2:[10]
]
13:
Universal(4,41,1,0)[
0:[8]
3:[11]
]
4
14:
Universal(4,41,1,0)[
1:[9]
2:[6]
]
15:
Universal(4,41,1,0)[
0:[4]
3:[7]
]
16:
Universal(4,41,1,0)[
1:[5]
2:[2]
]
17:
Universal(1,41,1,0)[
0:[3]
]
18:
Universal(1,41,1,0)[
0:[1]
]
5
