(just be done in java;eclipse compatible) Objective: Create a hash table of phob
ID: 3691726 • Letter: #
Question
(just be done in java;eclipse compatible)
Objective: Create a hash table of phobias where each entry the key is the name of the phobia, and the data is the explanation.
Create a class Phobia
Instance variables
Name
Description
Methods
toString: overrides the base toString and returns the name plus the description
equals: returns true only if both the name and the description match
Create a hash table PhobiaHashTable where each of the buckets corresponds to letters in the English alphabet.
Each index corresponds to a letter of the alphabet, and a hash method should be implement where a phobia given will return the index
Every time there is a phobia that starts with the same letter simply add it to the end of the bucket
It is a good idea to make an array of ArrayLists
Methods
add: Adds a new phobia to the hash table
remove: if the phobia’s name and description matches then remove it. Get over that fear.
lookup: given the phobia’s name return the description
printHashTable: prints out all entry in the hash table
Create a front end where users can add, remove, look up, and print out their fears.
Explanation / Answer
public class HashTable {
static private class ListNode {
Object key;
Object value;
ListNode next; // Pointer to next node in the list;
// A null marks the end of the list.
}
private ListNode[] table; // The hash table, represented as
// an array of linked lists.
private int count; // The number of (key,value) pairs in the
// hash table.
public HashTable()
table = new ListNode[64];
}
public HashTable(int initialSize) {
table = new ListNode[initialSize];
}
void dump() {
System.out.println();
for (int i = 0; i < table.length; i++) {
// Print out the location number and the list of
System.out.print(i + ":");
ListNode list = table[i];
while (list != null) {
System.out.print(" (" + list.key + "," + list.value + ")");
list = list.next;
}
System.out.println();
}
} // end dump()
public void put(Object key, Object value) {
int bucket = hash(key); // Which location should this key be in?
ListNode list = table[bucket]; // For traversing the linked list
// at the appropriate location.
while (list != null) {
if (list.key.equals(key))
break;
list = list.next;
}
if (list != null) {
list.value = value;
}
else {
// Since list == null, the key is not already in the list.
if (count >= 0.75*table.length) {
// The table is becoming too full. Increase its size
// before adding the new node.
resize();
}
ListNode newNode = new ListNode();
newNode.key = key;
newNode.value = value;
newNode.next = table[bucket];
table[bucket] = newNode;
count++; // Count the newly added key.
}
}
public Object get(Object key) {
int bucket = hash(key);
ListNode list = table[bucket];
while (list != null) {
if (list.key.equals(key))
return list.value;
list = list.next;
}
return null;
}
public void remove(Object key) {
int bucket = hash(key);
if (table[bucket] == null) {
return;
}
if (table[bucket].key.equals(key)) {
table[bucket] = table[bucket].next;
count--;
return;
}
ListNode prev = table[bucket];
ListNode curr = prev.next;
while (curr != null && ! curr.key.equals(key)) {
curr = curr.next;
prev = curr;
}
if (curr != null) {
prev.next = curr.next;
count--;
}
public boolean containsKey(Object key) {
int bucket = hash(key);
ListNode list = table[bucket];
while (list != null) {
if (list.key.equals(key))
return true;
list = list.next;
}
return false;
}
public int size() {
return count;
}
private int hash(Object key) {
return (Math.abs(key.hashCode())) % table.length;
}
private void resize() {
ListNode[] newtable = new ListNode[table.length*2];
for (int i = 0; i < table.length; i++) {
ListNode list = table[i];
while (list != null) {
ListNode next = list.next;
int hash = (Math.abs(list.key.hashCode())) % newtable.length;
list.next = newtable[hash];
newtable[hash] = list;
list = next;
}
}
table = newtable;
}
}
A Program for Testing HashTable:
public class TestHashTable {
public static void main(String[] args){
HashTable table = new HashTable(2);
String key,value;
while (true) {
System.out.println(" Menu:");
System.out.println(" 1. test put(key,value)");
System.out.println(" 2. test get(key)");
System.out.println(" 3. test containsKey(key)");
System.out.println(" 4. test remove(key)");
System.out.println(" 5. show complete contents of hash table.");
System.out.println(" 6. EXIT");
System.out.print("Enter your command: ");
switch ( TextIO.getlnInt()) {
case 1:
System.out.print(" Key = ");
key = TextIO.getln();
System.out.print(" Value = ");
value = TextIO.getln();
table.put(key,value);
break;
case 2:
System.out.print(" Key = ");
key = TextIO.getln();
System.out.println(" Value is " + table.get(key));
break;
case 3:
System.out.print(" Key = ");
key = TextIO.getln();
System.out.println(" containsKey(" + key + ") is "
+ table.containsKey(key));
break;
case 4:
System.out.print(" Key = ");
key = TextIO.getln();
table.remove(key);
break;
case 5:
table.dump();
break;
case 6:
return;
default:
System.out.println(" Illegal command.");
break;
}
System.out.println(" Hash table size is " + table.size());
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.