need by march 25, 5 pm Eastern time US
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 = [login to view URL](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
Hello
My name is Ahmed, i'm a top rated freelancer.
i worked over 150 projects and over 250 hours doing java projects.
plus i passed freelancer java exam with top 20%
plus i got 2 java certificate 1Z0-803 and 1Z0-804 with 3+ years experience.
small overview of feedback on my profile
"you want to get your projects completed with quality? Hire Ahmed. Highly recommended."
"Thoroughly satisfied with Ahmed, and would recommend him to anyone looking for an excellent java developer!"
"Highly recommended. Very smart and well experience"
looking forward to work with you
Regards