For this lab, you are to create a class that implements a dictionary (associative array, hash table), that associates Strings with doubles. It should deal with collisions by chaining (using linked lists).

Begin by creating the ListElements for the linked lists. These must NOT be templated, since Java forbids arrays of templated

objects. It will need a String named "key", a double named "value" and a link. This could, and probably should be an inner class of: a linked list class.

It (HashLinkedList) needs ListElement named head, a method to add an element to the list, a method to remove a specified element from the list, a method to return the value associated with a given key within the list, and a method to replace the value associated with a given key to a different value.

Finally you will build a Dictionary class which contains an array of LinkedLists. It will be convenient to have a memory cell to hold the size of this array.

You will want a constructor which allows the user to specify the hash table size (the size of the array mentioned above), and another constructor that defaults the array size to, say, 100.

You will want a method "insert" to insert a key/value into the hash table, and a method "lookup" which returns the value associated with the given key if that key exists in the table. If you insert a key/value pair and the key value already exists, replace its value field with the new value. If you attempt to lookup a value whose key does not exist, throw a KeyNotPresentException (which you will have to write.)

Finally, you need a private hash function which I shall discuss at the very bottom of this document.

Skeletons of the various classes. Feel free to add other attributes and methods if you find it convenient to do so: 

public class HashLinkedList { private ListElement head; public HashLinkedList() 

 private static int hash(String)  

 public void insert(String key, double value); public double lookup(String key) throws KeyNotPresentException 

 // remove the entry with the specified key public void delete(String key) 

// change the value associated with the key 

public void changeValue(String key) 

 class ListElement //inner class 

 { private String key; private double value; private ListElement link; 

 public ListElement(String key, double value, ListElement link) public ListElement(String key, double value) // defaults link to null 

 public String getKey() public double getValue() public void setValue(double value) 

// Never any need to change the key }}

public class Dictionary 

{ HashLinkedList hashTable[]; private int tablesize;

 public Dictionary(int size) //use a default table size; 

 public Dictionary() 

 public void define(String key, double value) //lookup key, if not present, add key/value pair, // otherwise change value 

 public void lookup(String key) 

 public void undefine(String key) } private static int hash(String key) 

How to hash a String: Normally I don't encourage anybody to write their own hash function. Getting it right is too hard. But for this exercise, I want you to have the experience. 

Use .charAt to retrieve each character in the string, something like a loop continging 

char c = key.charAt(i); //bit by bit and to set all but the least signifiant 8 bits to 0. //(ask me about this in class) int i = (int)c & 0xFF; sum = sum + i; 

After the loop, when all the characters have been processed sum = sum % tableSize; return sum; 

Steps to tackle Lab 6 1. Complete ListElement class 2. Complete HashLinkedList class complete constructor and test it in main(); complete toString() and test in in main(); complete insert method and test it in main(); complete lookup method and test it in main(); complete changeValue method and test it in main(); complete remove method and test it in main(); 3. Complete Dictionary class complete constructors and test them in main(); complete toString() and test in in main(); complete define method and test it in main(); complete lookup method and test it in main(); complete undefine method and test it in main(); 

Dictionary Class

public class Dictionary { HashLinkedList hashTable[]; private int tableSize; public Dictionary(int size) { }

//use a default table size; public Dictionary() { }

public void define(String key, double value) { } //lookup key, if not present, add key/value pair, // otherwise change value public void lookup(String key) { }

public void undefine(String key) { }

private static int hash(String key) { return 0; } @Override public String toString() { return ""; } public static void main(String[] args) { /* create a HashTable that has empty linked list (empty chain); print HashTable; define some(key, value) pairs in the dictionary; print HashTable; lookup some (key); print HashTable; undefine at least one (key) from the dictionary; print HashTable; */ } }

HashLinked Class

public class HashLinkedList {

private ListElement head;

public HashLinkedList() {

}

public void insert(String key, double value) {

}

//public double lookup(String key) throws KeyNotPresentException { //Xli: changed to throw LLException just to give you a demo. // You need to implement KeyNotPresentException // and then have lookup throw KeyNotPresentException public double lookup(String key) throws LLException { return 1.0; }

// remove the entry with the specified key public void delete(String key) {

} // change the value associated with the key public void changeValue(String key) {

}

@Override public String toString() { return ""; } //inner class class ListElement { private String key; private double value; private ListElement link;

public ListElement(String key, double value, ListElement link) {

}

// defaults link to null public ListElement(String key, double value) {

} public String getKey() { return ""; }

public double getValue() { return 0.0; }

public void setValue(double value) {

} // Never any need to change the key } public static void main(String[] args) { /* create an empty HashLinkedList object; print the HashLinkedList object content; insert some(key, value) pairs into the linked list; print the HashLinkedList object content; lookup some (key, value); //print the HashLinkedList object content; change value for a given key; print the HashLinkedList object content; remove at least one (key) from the linked list; print the HashLinkedList object content; */ } }