class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
// Each MapEntry object is a pair consisting of a key (a Comparable
// object) and a value (an arbitrary object).
K key;
E value;
public MapEntry (K key, E val) {
this.key = key;
this.value = val;
}
public int compareTo (K that) {
// Compare this map entry to that map entry.
@SuppressWarnings("unchecked")
MapEntry<K,E> other = (MapEntry<K,E>) that;
return this.key.compareTo(other.key);
}
public String toString () {
return "<" + key + "," + value + ">";
}
}
public class CBHT<K extends Comparable<K>, E> {
private SLLNode<MapEntry<K,E>>[] buckets;
@SuppressWarnings("unchecked")
public CBHT(int m) {
// Construct an empty CBHT with m buckets.
buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
}
private int hash(K key)
public SLLNode<MapEntry<K,E>> search(K targetKey)
public void insert(K key, E val)
public void delete(K key)
}
private int hash(K key) {
// Translate key to an index of the array buckets.
return Math.abs(key.hashCode()) % buckets.length;
}
public SLLNode<MapEntry<K,E>> search(K targetKey) {
// Find which if any node of this CBHT contains an
// entry whose key is equal to targetKey.
// Return a link to that node (or null if there is none).
int b = hash(targetKey);
for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr =
curr.succ) {
if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
return curr;
}
return null;
}
public void insert(K key, E val) {
// Insert the entry <key, val> into this CBHT.
MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
int b = hash(key);
for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr =
curr.succ) {
if (key.equals(((MapEntry<K, E>) curr.element).key)) {
// Make newEntry replace the existing entry ...
curr.element = newEntry;
return;
}
}
// Insert newEntry at the front of the 1WLL in bucket b ...
buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
}
public void delete(K key) {
// Delete the entry (if any) whose key is equal
// to key from this CBHT.
int b = hash(key);
for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b];
curr != null; pred = curr, curr = curr.succ) {
if (key.equals(((MapEntry<K,E>) curr.element).key)) {
if (pred == null)
buckets[b] = curr.succ;
else
pred.succ = curr.succ;
return;
}
}
}
