Question

create a hash table to implement spell checker in java

1. Create a file of 100 words of varying length (max 8 characters).

2. All the words are in lower case.

3. design a hash table.

4. enter each word in the hash table.

Once the hash table is created, run it as a spell checker.enter a word (interactive), find the word in the hash table. If not found enter an error message. Then prompt for next word. End the session by some control character ctrl-c.

1. use the linear probing first. Count the number of collisions and print it.

2. Then use quadratic probing. Count the number of collisions and print it.

3. Start with a table size that is about 53. So 100 words would still have a load factor of less than .5 Now add 10 more words. The program should automatically determine that table size needs to increase.

Print out - increasing table size to <size>

rehash all the old words also and the new words to the new hash table.

Print the collisions in each case for the new table size.

Answer 1

Linear Probing:

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Y2018.April;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
*
* @author sambh
*/
public class HashTable {
private String[] hashTable;
private int collisions;
private int load;

public HashTable() {
hashTable = new String[50];
for (int i = 0; i < 50; i++)
hashTable[i] = null;
collisions = 0;
load = 0;
}

public HashTable(int n ) {
hashTable = new String[n];
for (int i = 0; i < n; i++)
hashTable[i] = null;
collisions = 0;
load = 0;
}
  
public void load(File file) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String word;
while ((word = br.readLine()) != null)
add(word);
br.close();
}
  
public void add(String word) {
if (load + 1 >= hashTable.length)
expandHashTable();
int hashKey = word.hashCode() % hashTable.length;
while(true) {
if (hashTable[hashKey] == null) {
hashTable[hashKey] = word;
load++;
break;
}
collisions++;
hashKey ++; //linear probing
if (hashKey == hashTable.length)
hashKey = 0;
}
}

private void expandHashTable() {
System.out.println("Increasing table size to " + hashTable.length * 2);
String[] backUpTable = hashTable;
collisions = 0;
load = 0;
hashTable = new String[hashTable.length * 2];
for(int i = 0; i < backUpTable.length; i++)
if (backUpTable[i] != null)
add(backUpTable[i]);
}
  
boolean search(String word) {
int hashKey = word.hashCode() % hashTable.length;
while(true) {
if (hashTable[hashKey] == null) {
return false;
}
else if (hashTable[hashKey].equalsIgnoreCase(word)) {
return true;
}
hashKey ++; //linear probing
if (hashKey == hashTable.length)
hashKey = 0;
if (hashKey == word.hashCode() % hashTable.length)
return false;
}
}
  
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashTable hashOb1 = new HashTable(53);
hashOb1.load (new File("words.txt"));
String word;
while(true) {
System.out.println("Enter a word:");
word = br.readLine();
if (hashOb1.search(word))
System.out.println("Found");
else
System.out.println("Not Found");
}
}
}

Quadratic probing:

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Y2018.April;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
*
* @author sambh
*/
public class HashTable {
private String[] hashTable;
private int collisions;
private int load;

public HashTable() {
hashTable = new String[50];
for (int i = 0; i < 50; i++)
hashTable[i] = null;
collisions = 0;
load = 0;
}

public HashTable(int n ) {
hashTable = new String[n];
for (int i = 0; i < n; i++)
hashTable[i] = null;
collisions = 0;
load = 0;
}
  
public void load(File file) throws IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String word;
while ((word = br.readLine()) != null)
add(word);
br.close();
}
  
public void add(String word) {
if (load + 1 >= hashTable.length)
expandHashTable();
int hashKey = word.hashCode() % hashTable.length;
int probing = 1;
while(true) {
if (hashTable[hashKey] == null) {
hashTable[hashKey] = word;
load++;
break;
}
collisions++;
hashKey += (probing * probing); //quadratic probing
probing ++;
hashKey = hashKey % hashTable.length;
}
}

private void expandHashTable() {
System.out.println("Increasing table size to " + hashTable.length * 2);
String[] backUpTable = hashTable;
collisions = 0;
load = 0;
hashTable = new String[hashTable.length * 2];
for(int i = 0; i < backUpTable.length; i++)
if (backUpTable[i] != null)
add(backUpTable[i]);
}
  
boolean search(String word) {
int hashKey = word.hashCode() % hashTable.length;
int probing = 1;
while(true) {
if (hashTable[hashKey] == null) {
return false;
}
else if (hashTable[hashKey].equalsIgnoreCase(word)) {
return true;
}
hashKey += (probing * probing); //linear probing
probing ++;
hashKey = hashKey % hashTable.length;
if (hashKey == word.hashCode() % hashTable.length || probing == hashTable.length)
return false;
}
}
  
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashTable hashOb1 = new HashTable(53);
hashOb1.load (new File("words.txt"));
String word;
while(true) {
System.out.println("Enter a word:");
word = br.readLine();
if (hashOb1.search(word))
System.out.println("Found");
else
System.out.println("Not Found");
}
}
}

words.txt
a
about
all
also
and
as
at
be
because
but
by
can
come
could
day
do
even
find
first
for
from
get
give
go
have
he
her
here
him
his
how
I
if
in
into
it
its
just
know
like
look
make
man
many
me
more
my
new
no
not
now
of
on
one
only
or
other
our
out
people
say
see
she
so
some
take
tell
than
that
the
their
them
then
there
these
they
thing
think
this
those
time
to
two
up
use
very
want
way
we
well
what
when
which
who
will
with
would
year
you
your