Creating a basic HASHTABLE java Help! Please show a print out of your sample out
ID: 3845681 • Letter: C
Question
Creating a basic HASHTABLE java Help!
Please show a print out of your sample output, along with the statistics. Thank you
HashTable in Java Help
public class HashTable implements IHashTable {
//You will need a HashTable of LinkedLists.
private int nelems; //Number of element stored in the hash table
private int expand; //Number of times that the table has been expanded
private int collision; //Number of collisions since last expansion
private String statsFileName; //FilePath for the file to write statistics upon every rehash
private boolean printStats = false; //Boolean to decide whether to write statistics to file or not after rehashing
//You are allowed to add more for longest chain, etc.
/**
* Constructor for hash table
* @param Initial size of the hash table
*/
public HashTable(int size) {
//Initialize
}
/**
* Constructor for hash table
* @param Initial size of the hash table
* @param File path to write statistics
*/
public HashTable(int size, String fileName){
//Set printStats to true and statsFileName to fileName
}
@Override
public boolean insert(String value) {
//TODO
}
@Override
public boolean delete(String value) {
//TODO
}
@Override
public boolean contains(String value) {
//TODO
}
@Override
public void printTable() {
//TODO
}
@Override
public int getSize() {
//TODO
}
private void printStatisitcs(){ //printStatistics() to print the statistics after each expansion. This method will be called from insert/rehash only if printStats=true
//TODO
}
private void rehash() { //rehash() to expand and rehash the items into the table when load factor goes over the threshold.
// TODO
}
//TODO - Helper methods can make your code more efficient and look neater.
}
insert (elem): Inserts element elem in the hash table. Your program should return true or false, depending on whether it was inserted or not. Return true if item is inserted, false if it already exists. Throw a NullPointerException if a null value is passed. contains (elem): Uses the hash table to determine if elem is in the hash table. Your program should return true or false, depending on whether the item exists. Throw a NullPointerException if a null value is passed. deleterelem): Use the hash table to determine where elem is, delete it from the hash table. Your program should return true if the item is deleted, false if it can't be deleted (an item can't be deleted if it does not exist in the hash table). Throw a NullPointerException if a null value is passed. print Table 0: Print out the hash table. (see sample output below) getsize(): returns the number of elements currently stored in the hashtable Note that in the contains/delete method, you shouldn't need to search through the entire table to find an element. Sample output format for printTable() 1: 10 2: 11, 1 3: 12, 2 4: 13, 3 5: 14, 4, 5 6: 15 7: 16, 6 8: 17 9: 18, 7 10: 19 11 12: 9 13 14: 8Explanation / Answer
//HashTable.java
import java.util.*;
import java.io.*;
import java.math.RoundingMode;
import java.text.DecimalFormat;
public class HashTable implements IHashTable {
private int nelems; //Number of element stored in the hash table
private int expand; //Number of times that the table has been expanded
private int collision; //Number of collisions since last expansion
private String statsFileName; //FilePath for the file to write statistics upon every rehash
private boolean printStats = false; //Boolean to decide whether to write statistics to file or not after rehashing
private double load; // load factor
private LinkedList<String>[] hashTable;
private LinkedList<String>[] tempTable;
private File output;
private int longest;//the number of longest chain
//You are allowed to add more :)
/**
* Constructor for hash table
* @param size
*/
public HashTable(int size) {
//Initialize
this.hashTable = new LinkedList[size];
for(int i=0;i<hashTable.length;i++) {
hashTable[i] = new LinkedList<String>();
}
}
/**
* Constructor for hash table
* @param size
* @param fileName
*/
public HashTable(int size, String fileName){
//Set printStats to true and statsFileName to fileName
this.printStats = true;
this.statsFileName = fileName;
this.hashTable = new LinkedList[size];
for(int i=0;i<hashTable.length;i++) {
hashTable[i] = new LinkedList<String>();
}
}
/**
* insert a value into hashTable
* @param value value to insert
* @return
*/
@Override
public boolean insert(String value){
if(value == null) {
throw new NullPointerException();
}
if(lookup(value)) {
return false;
}
if(this.load >= 0.67) {
//rehash when load factor is greater than 0.67;
expand++;
if(printStats == true) {
printStatistics();
}//print table only when printStats is true
collision = 0;
longest = 0;
rehash();
}
int index = this.hashFunction(value,tableSize());
//check collision
if(!hashTable[index].isEmpty()) {
collision++;
}
hashTable[index].add(value);
nelems++;
setLoad();
//check longest chain
if(hashTable[index].size() > longest) {
longest = hashTable[index].size();
}
return true;
}
/**
* delete a value from hashTable
* @param value value to delete
* @return
*/
@Override
public boolean delete(String value) {
int index = hashFunction(value,tableSize());
if(value == null) {
throw new NullPointerException();
}
if(!lookup(value)) {
return false;
}else {
hashTable[index].remove(value);
nelems--;
return true;
}
}
/**
* look for a value in hashTable
* @param value value to look up
* @return
*/
@Override
public boolean lookup(String value) {
int index = hashFunction(value,tableSize());
if(hashTable[index].isEmpty()) {
return false;
}else {
for (int i = 0; i < hashTable[index].size(); i++) {
if(hashTable[index].contains(value)){
return true;
}
}
}
return false;
}
/**
* print out the hashTable
*/
@Override
public void printTable() {
if(nelems == 0) {
return;
}else {
for (int i = 0; i < hashTable.length; i++) {
if (hashTable[i].isEmpty()) {
System.out.println(i + ":");
} else {
System.out.print(i + ": ");
System.out.println(hashTable[i].toString());
}
}
}
}
/**
* get the number of elements in the hashTable
* @return
*/
@Override
public int getSize() {
return this.nelems;
}
/**
* algorithm of hashfunction
* @param key
* @param tableSize
* @return
*/
private int hashFunction(String key,int tableSize) {
int hashValue = 0;
for(int i=0;i<key.length();i++) {
int letter = key.charAt(i);
hashValue = (hashValue*27 + letter)%tableSize;
}
return hashValue;
}
/**
* get size of hashTable
* @return
*/
private int tableSize() {
return this.hashTable.length;
}
/**
* rehash function
*/
private void rehash() {
int newTableSize = tableSize()*2;
tempTable = new LinkedList[newTableSize];//doubled size hashTable
for(int i=0;i<newTableSize;i++) {
tempTable[i] = new LinkedList<String>();
}
for(int i=0;i<tableSize();i++) {
LinkedList<String> chain = hashTable[i];//linkedlist of ith position
for(int j=0;j<chain.size();j++) {
int newIndex = hashFunction(chain.get(j),newTableSize);//position in doubled size hashTable
tempTable[newIndex].add(chain.get(j));//add element into new hashTable
}
}
hashTable = tempTable;
}
/**
* print statistic
*/
private void printStatistics() {
DecimalFormat df = new DecimalFormat("#.##");
df.setRoundingMode(RoundingMode.CEILING);
try {
output = new File(statsFileName);
if(!output.exists())
output.createNewFile();
FileWriter writer = new FileWriter(output,true);
BufferedWriter bWriter = new BufferedWriter(writer);
bWriter.write("" + this.expand + " resizes, load factor " + df.format(load) + ", " + this.collision + " collisions, " +
this.longest + " longest chain ");
bWriter.newLine();
bWriter.close();
} catch (IOException e) {
System.out.println("IOExceptions!");
}
}
/**
* calculate load factor
*/
private void setLoad() {
load = 1.0 * this.nelems/tableSize();
}
public double getLoad() {
return this.load;
}
}
===========================================================================
// IHashTable.java
public interface IHashTable
{
boolean insert(String value);
boolean delete(String value);
boolean lookup(String value);
void printTable();
/**
* Return the number of elements currently stored in the hashtable
* @return nelems
*/
int getSize();
}
=========================================================================
// HashTableTester.java
import org.junit.*;
import java.util.*;
import static org.junit.Assert.*;
public class HashTableTester {
private HashTable a;
private HashTable b;
private HashTable c;
@Before
public void setup() {
a = new HashTable(5);
for(int i=0;i<5;i++) {
a.insert(""+i);
}
b = new HashTable(5,"hashTable1.txt");
for(int i=0;i<5;i++) {
b.insert(""+i);
}
c = new HashTable(10);
}
@Test
public void testGetSize() {
assertEquals("number of elements 5",5,a.getSize());
}
@Test
public void testInsert() {
assertTrue("insert 5",a.insert("5"));
assertEquals("number of elements 6",6,a.getSize());
assertFalse("insert 5 twice",a.insert("5"));
try {
a.insert(null);
fail("should throw exception");
} catch(NullPointerException e) {
//normal
}
}
@Test
public void testLookup() {
assertTrue("lookup 1",a.lookup("1"));
assertFalse("lookup 6",a.lookup("6"));
try {
a.lookup(null);
fail("should throw exception");
} catch(NullPointerException e) {
//normal
}
}
@Test
public void testDelete() {
assertTrue("delete 1",a.delete("1"));
assertEquals("number of elements 4",4,a.getSize());
assertFalse("delete 6",a.delete("6"));
try {
a.delete(null);
fail("should throw exception");
} catch(NullPointerException e) {
//normal
}
}
@Test
public void testPrintTable() {
c.insert("the");
c.insert("quick");
c.insert("brown");
c.insert("fox");
c.insert("jumps");
c.insert("over");
c.insert("the");
c.insert("lazy");
c.insert("dog");
}
}
=================================================================================
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.