JAVA** I need help with the following code; I am completely lost when it comes t

Question

JAVA** I need help with the following code; I am completely lost when it comes to HashTables and I simply can't figure out how to do 3-5.

Also, the very last part; ANY help would be very appreciated

b.) (For hash tables) The number of hash collisions that occurred during spell checker creation

c.) (For hash tables) The percentage of indices in the final table that are occupied

In this project you will implement and explore the performance of different kinds of spell checkers. I have provided a text file containing about l 10,000 English words on eCourseware for you to use. You can assume that all words contain only lower-case letters. Approach i: Binary Search Tree One easy way of implementing a spell checker is to use a binary search tree. Given a list of valid words, you can insert them into a BST. Checking whether a word is spelled correctly simply involves searching the tree for that word. Ifthe word is found, great -if not, it must be misspelled! Remember that finding items in a BST takes O(log n) time on average, where n is the number of elements in the tree. Thus, the expected time cost of using this spell checker depends on the number of words that it's storing. 1. (14 pts) Write a BSTSpellChecker class. This class should have an instance variable of type Binarysearch Tree

Explanation / Answer

implemented 3rd question. Writen interface for 4th question and also a class to implement the first hash function similarly implement the remaing two classes and finally written HashTableSpellChecker with very basic implemtation just extend it almost same as BSTspellchecker

For the final two a,b

a. The number of hash collisions that occurred during spell checker creation - Add a function in HashTable getCollisionCount() just call that it will display the collision count

b. The percentage of indices in the final table that are occupied -  Add a function in HashTable getIndiciesPercentage() just call that it will display the percentage.

3rd question HashTable Code :

// Java program to demonstrate implementation of our
// own hash table with chaining for collision detection
import java.util.ArrayList;

// A node of chains
class HashNode<K, V>
{
K key;
  

// Reference to next node
HashNode<K> next;

// Constructor
public HashNode(K key)
{
this.key = key;
  
}
}

// Class to represent entire hash table
class HashTable<K>
{
// bucketArray is used to store array of chains
private ArrayList<HashNode<K>> bucketArray;

// Current capacity of array list
private int numBuckets;

// Current size of array list
private int size;
  
   //store collision count
   int collision;
  
   //get the StringHasher;
   private StringHasher sHash;

// Constructor (Initializes capacity, size and
// empty chains.
public HashTable(StringHasher sHash)
{
bucketArray = new ArrayList<>();
numBuckets = 5;
size = 0;
       collision = 0;
      
       this.sHash = sHash;

// Create empty chains
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
}

public int size() { return size; }
public boolean isEmpty() { return size() == 0; }

// This implements hash function to find index
// for a key
private int getBucketIndex(K key)
{
int hashCode = sHash.hash(key);
int index = hashCode % numBuckets;
return index;
}

// Returns value for a key
public K get(K key)
{
// Find head of chain for given key
int bucketIndex = getBucketIndex(key);
HashNode<K> head = bucketArray.get(bucketIndex);

// Search key in chain
while (head != null)
{
if (head.key.equals(key))
return head.key;

// If key not found
return null;
}

// Adds a key value pair to hash
public void add(K key, V value)
{
// Find head of chain for given key
int bucketIndex = getBucketIndex(key);
HashNode<K> head = bucketArray.get(bucketIndex);
      
       if(head!=null)
       {
           collision++;
       }
// Check if key is already present
while (head != null)
{
if (head.key.equals(key))
{
return;
}
head = head.next;
}

// Insert key in chain
size++;
head = bucketArray.get(bucketIndex);
HashNode<K> newNode = new HashNode<K>(key);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);

// If load factor goes beyond threshold, then
// double hash table size
if ((1.0*size)/numBuckets >= 1.0)
{
ArrayList<HashNode<K, V>> temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets + 1;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);

for (HashNode<K> headNode : temp)
{
while (headNode != null)
{
add(headNode.key);
headNode = headNode.next;
}
}
}
}
  
   public int getCollisionsCount()
   {
       return collision;
   }
  
   public int getIndicesPercentage()
   {
       return ((1.0*size)/numBuckets) * 100;
   }
}

4th. StringHasher interface

public interface StringHasher
{
   int hash(String s);
}

Following a implimentation of fisrt hash Function

public class FirstHashFunction implements StringHasher
{
   int hash(String s)
   {
       return 0;
   }
}

Finally implementation of HashtableSpellChecker

public class HashTableSpellChecker
{
   //implement the code to get the type of hashfuction required and assign it to HahTable
   StringHasher sh;
  
   HashTable<String> hs = new HashTable<>(sh);
  
   //all the other methes are same as BSTSpell checker
  
   public void add(String s)
   {
       //just call add in HAshTable
       hs.add(s);
   }
  
   //similarly implement all other methods
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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