Instructions
Objective
Write a java assignment program to build a hash table using programming language.
Requirements and Specifications
Source Code
import java.lang.reflect.Array;
public class HashTable {
private final static int DEFAULT_SIZE = 101 ;
private final NGen[] buckets;
private int size = 0;
public HashTable() {
buckets = (NGen[]) Array.newInstance(NGen.class, DEFAULT_SIZE);
}
public void add(T item) {
int bucket = hash(item);
if (addToBucket(bucket, item)) {
size++;
}
}
public void display() {
StringBuilder builder = new StringBuilder();
builder.append("Hash Table").append(System.lineSeparator());
builder.append("Table length: ").append(DEFAULT_SIZE).append(System.lineSeparator());
builder.append("Items in table: ").append(size).append(System.lineSeparator());
builder.append("Load factor: ").append((1.0 * size)/DEFAULT_SIZE).append(System.lineSeparator());
StringBuilder bucketsBuilder = new StringBuilder();
int collisions = 0;
int shortest = -1;
int longest = -1;
for (int i = 0; i int length = getLength(i);
if ((shortest == -1) || (length < shortest)) {
shortest = length;
}
if ((longest == -1) || (length > longest)) {
longest = length;
}
if (length > 0) {
collisions += length - 1;
}
bucketsBuilder.append("Bucket ").append(i).append(": ").append(length).append(" item(s)").append(System.lineSeparator());
}
builder.append("Collisions: ").append(collisions).append(System.lineSeparator());
if (shortest != -1) {
builder.append("Shortest chain: ").append(shortest).append(System.lineSeparator());
}
if (longest != -1) {
builder.append("Longest chain: ").append(longest).append(System.lineSeparator());
}
builder.append(bucketsBuilder);
System.out.println(builder);
}
public T remove(T item) {
int bucket = hash(item);
return removeFromBucket(bucket, item);
}
private int hash(T key) {
int hash = key.hashCode();
if (hash < 0) {
hash -= (hash/DEFAULT_SIZE) * (DEFAULT_SIZE + 1);
}
return hash % DEFAULT_SIZE;
}
private boolean addToBucket(int bucket, T item) {
if (buckets[bucket] == null) {
buckets[bucket] = new NGen<>(item);
}
else {
NGen current = buckets[bucket];
while (current.getNext() != null) {
if (current.getData().equals(item)) {
return false;
}
current = current.getNext();
}
if (current.getData().equals(item)) {
return false;
}
NGen newNode = new NGen<>(item);
current.setNext(newNode);
}
return true;
}
private T removeFromBucket(int bucket, T item) {
if (buckets[bucket] != null) {
NGen current = buckets[bucket];
while (current != null) {
if (current.getData().equals(item)) {
return current.getData();
}
current = current.getNext();
}
}
return null;
}
private int getLength(int cell) {
NGen current = buckets[cell];
int count = 0;
while (current != null) {
count++;
current = current.getNext();
}
return count;
}
private static class NGen {
private final T data;
private NGen next;
public NGen(T data) {
this.data = data;
this.next = null;
}
public T getData() {
return data;
}
public NGen getNext() {
return next;
}
public void setNext(NGen next) {
this.next = next;
}
}
}