[go: up one dir, main page]
Scribd
Upload
59 views4 pages

CS 1103 Learning Journal Exercise 5

This document defines a hash table class that stores key-value pairs using separate chaining. The class implements methods for putting, getting, removing, and checking for keys. It uses a resize method to dynamically increase the table size when load reaches 75% capacity. Main provides a menu driver for testing the hash table operations.

Uploaded by

lumstrylmoxyfgrhvd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
59 views4 pages

CS 1103 Learning Journal Exercise 5

This document defines a hash table class that stores key-value pairs using separate chaining. The class implements methods for putting, getting, removing, and checking for keys. It uses a resize method to dynamically increase the table size when load reaches 75% capacity. Main provides a menu driver for testing the hash table operations.

Uploaded by

lumstrylmoxyfgrhvd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 4

import java.util.

Hashtable;

public class Main {

private static class ListNode {


String key;
String value;
ListNode next;
}

private ListNode[] table;


private int count;

public void HashTable(){


table = new ListNode[64];
}

public void HashTable(int initalSize) {


table = new ListNode[initalSize];
}

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

public void put(String key, String value){


assert key != null: "Key cannot be null";
int bucket = hash(key);
ListNode 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();
}
ListNode newNode = new ListNode();
newNode.key = key;
newNode.value = value;
newNode.next = table[bucket];
table[bucket] = newNode;
count++;
}
}

public String get(String 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(String 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(String 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;
}

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 HashTable.");
System.out.println("- 6. Quit.");
System.out.println("Enter Number: ");

switch (TextIO.getlnInt()){
case 1:
System.out.println("Key = ");
key = TextIO.getln();
System.out.println("Value = ");
value = TextIO.getln();
table.put(key, value);
break;

case 2:
System.out.println("Key = ");
key = TextIO.getln();
System.out.println("Value is " + table.get(key));
break;

case 3:
System.out.println("Key = ");
key = TextIO.getln();
System.out.println("containsKey(" + key + ") is " +
table.containsKey(key));
break;

case 4:
System.out.println("Key = ");
key = TextIO.getln();
table.remove(key);
break;

case 5:
table.get(table);
break;
case 6:
return;

default:
System.out.println("Error: Command isn't valid.");
break;
}
System.out.println("Hash Table size is: " + table.size());
}
}
}

You might also like