Hash function converts string to hash value an integer. Use the above UML diagra

Question

Hash function converts string to hash value an integer.

Use the above UML diagram and descriptions below to write a class that implements a Hash table. Your implementation should use open chaining to resolve collisions. You may provide additional class attributes, as you see fit, to complete the class.

The above class has the following private attributes:

table: This is a pointer to the object's dynamically allocated hash table. Used to create an array of Linked List objects.

size - stores the number of elements in the hash table ( the capacity ).

hash - the hash function. It accepts the key string and returns the hash value.

The class has the following public attributes:

constructor - accepts an integer argument used to determine the number of elements in the hash table. Dynamically allocates the hash table.

destructor - deallocates all dynamically allocated memory.

insert - insert's it's argument into the hash table. calls the hash function to obtain an appropriate hash address. Returns 0 if successful, -1 otherwise.

remove - removes the first key matching it's argument from the hash table. Returns 0 if successful, -1 otherwise.

find - returns true if a key matching it's argument is found, false otherwise.

clear - resets the object to it's initial state.

isFull - returns true if the structure is full, false otherwise.

isEmpty - returns true if the structure has no keys, false otherwise.

print - displays all the keys currently stored in the structure.

Possible sample output from the print method:

Bucket 0: Head -> white->snow->And->went,->go.->NULL

Bucket 1:Head -> was->was->NULL

Bucket 2: Head -> a->fleece->as->lamb->sure->to->NULL

Bucket 3:Head -> lamb->It's->that->that->NULL

Bucket 4:Head -> Mary->little->everywhere->Mary->NULL

The above is what the 5-element hash table looks like after inserting "Mary had a little lamb. It's fleece was white as snow And everywhere that Mary went, that lamb was sure to go."

Hints:

Here's an example of code you might use to invoke the find method from one of the List objects in the table array:

return table[hash(key)].find(key);

If this makes no sense to you, review arrays of objects from Chapter 13 of the text from CS2370.

You need to come up with some scheme for converting letters to characters. In my solution, I found the sum of the ascii codes for each key and then ran modulus on that. Whatever scheme you come with is up to you.

driver.cpp is the file used to produce the sample output.

Hashtable -table:List* -size:int ----------------------------------------------------------------------------------------------------------------- -hash(key:string) : int {query} +HashTable(s:int): +~HashTable(): +clear():void +insert(key:string) : int +remove(key:string) : int +find(key:string) : boolean +isFull():bool{query} +isEmpty():bool{query} +print():void{query}

Explanation / Answer

class HashTableClass {

private static class NodeList {
String key;
String value;
NodeList next;
  
}

private NodeList[] table;

private int count;

public HashTableClass() {
table = new NodeList[64];
}

public HashTableClass(int initialSize) {
if (initialSize <= 0)
throw new IllegalArgumentException("Illegal table size");
table = new NodeList[initialSize];
}

void dump() {
System.out.println();
for (int i = 0; i < table.length; i++) {
  
System.out.print(i + ":");
NodeList list = table[i];
while (list != null) {
System.out.print(" (" + list.key + "," + list.value + ")");
list = list.next;
}
System.out.println();
}
}

public void put(String key, String value) {
  
assert key != null : "The key must be non-null";
  
int bucket = hash(key);
NodeList list = table[bucket];
while (list != null) {

if (list.key.equals(key))
break;
list = list.next;
}
  

  
if (list != null) {
  
list.value = value;
}
else {

if (count >= 0.75*table.length) {

resize();
bucket = hash(key);
}
NodeList newNode = new NodeList();
newNode.key = key;
newNode.value = value;
newNode.next = table[bucket];
table[bucket] = newNode;
count++;
}
}

public String get(String key) {
  
int bucket = hash(key);
NodeList list = table[bucket];
while (list != null) {
  
if (list.key.equals(key))
return list.value;
list = list.next;
}

  
return null;
}

  
public void remove(String key) {
  
int bucket = hash(key);
  
if (table[bucket] == null) {

return;
}
  
if (table[bucket].key.equals(key)) {

table[bucket] = table[bucket].next;
count--;
return;
}
  

NodeList prev = table[bucket];
NodeList 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(String key) {
  
int bucket = hash(key);
NodeList 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() {
NodeList[] newtable = new NodeList[table.length*2];
for (int i = 0; i < table.length; i++) {

NodeList list = table[i];
while (list != null) {

NodeList next = list.next;
int hash = (Math.abs(list.key.hashCode())) % newtable.length;

list.next = newtable[hash];
newtable[hash] = list;
list = next;
}
}
table = newtable;
}
  

}

public class HashTableMain {

public static void main(String[] args){
HashTableClass table = new HashTableClass(2);
String key,value;
while (true) {
System.out.println(" Menu:");
System.out.println(" 1. put(key,value)");
System.out.println(" 2. get(key)");
System.out.println(" 3. containsKey(key)");
System.out.println(" 4. remove(key)");
System.out.println(" 5. total contents of hash table details");
System.out.println(" 6. to EXIT the program");
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(" Mentioned Illegal command.");
break;
}
System.out.println(" the hash table total size is " + table.size());
}
}

}

output :

Menu:
1. put(key,value)
2. get(key)
3. containsKey(key)
4. remove(key)
5. show complete contents of hash table.
6. EXIT
Enter your command: 1

Key = 10
Value = 10

Hash table size is 1

Menu:
1. put(key,value)
2. get(key)
3. containsKey(key)
4. remove(key)
5. show complete contents of hash table.
6. EXIT
Enter your command: 2

Key = 10
Value is 10

Hash table size is 1

Menu:
1. put(key,value)
2. get(key)
3. containsKey(key)
4. remove(key)
5. show complete contents of hash table.
6. EXIT
Enter your command: 5

0:
1: (10,10)

Hash table size is 1

Menu:
1. put(key,value)
2. get(key)
3. containsKey(key)
4. remove(key)
5. show complete contents of hash table.
6. EXIT
Enter your command: 6

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.