Write a hash function to implement a digit-folding
approach in the hash
function. Your program should work for any array size and any key
length.
Use linear probing. Accessing a group of digits in a number may be
easier
than you think. Does it matter if the array size is not a multiple
of 10?
#java#withcomments please
import java.io.*;
// Defines a class Items
class Items
{
// Instance variable to store string data
private String stringData;
// Parameterized constructor to assign parameter data to instance variable
public Items(String str)
{
stringData = str;
}// End of method
// Method to return data
public String getKeyData()
{
return stringData;
}// End of method
}// End of class Items
// Defines class to CreateHashTable
class CreateHashTable
{
private Items[] hashArray;
private int arraySize;
private Items nonAvailableItem;
// Parameterized constructor to create hash table
public CreateHashTable(int newSize)
{
arraySize = newSize;
hashArray = new Items[arraySize];
// Deleted item key is a dash
nonAvailableItem = new Items("-");
// Loops till size
for(int counter = 0; counter < newSize; counter++)
hashArray[counter] = new Items(nonAvailableItem.getKeyData());
}// End of constructor
// Method to display hash table
public void displayHahsTable()
{
System.out.print("Table: \n");
// Loops till array size
for(int counter = 0; counter < arraySize; counter++)
{
// Checks if current counter index position value is not null
if(hashArray[counter] != null)
System.out.println(hashArray[counter].getKeyData() + " ");
// Otherwise it is null
else
System.out.print("** ");
}// End of for loop
System.out.println();
}// End of method
// Method to generate a hash and return hash value from a given string
// passed as parameter
public int hashFunction(String currentKey)
{
int hashValue = 0;
// Loops till key size
for(int counter = 0; counter < currentKey.length(); counter++)
{
int letter = currentKey.charAt(counter);
hashValue = (hashValue * 27 + letter) % arraySize;
}// End of for loop
return hashValue;
}// End of method
// Method to insert an item to hash table
public void insertItem(Items newItem)
{
// Assumes table not full
// Calls the method to get the data
String currentKey = newItem.getKeyData();
// Calls the method to get the hash value
int hashValue = hashFunction(currentKey);
// Loops till current hashValue index position value is not "-"
while(hashArray[hashValue].getKeyData() != "-")
{
// Increase the hash value by one
++hashValue;
// Calculates the hash value by getting remainder of array size
hashValue %= arraySize;
}// End of while loop
// Assigns the parameter newItem at hashValue index position
hashArray[hashValue] = newItem;
}// End of method
// Method to delete an item from hash table
public Items deleteItem(String currentKey)
{
// Calls the function to get the hash value of the parameter currentKey
int hashValue = hashFunction(currentKey);
// Loops till current hashValue index position value is not "-"
// and current hashValue index position value is not null
while(hashArray[hashValue].getKeyData() != "-" &&
hashArray[hashValue].getKeyData() != null)
{
// Checks current hashValue index position value is equals
// to the parameter currentKey value
if(hashArray[hashValue].getKeyData().equals(currentKey))
{
// Assigns the data to temporary key
Items tempKey = hashArray[hashValue];
// Assigns the nonAvailableItem i.e., "-" at
// hash value index position
hashArray[hashValue] = nonAvailableItem;
return tempKey;
}// End of if condition
// Increase the hash value by one
++hashValue;
// Calculates the hash value by getting remainder of array size
hashValue %= arraySize;
}// End of while loop
return null;
}// End of method
// Method to search an item from the hash table
public Items searchItem(String currentKey)
{
// Calls the function to get the hash value of the parameter currentKey
int hashValue = hashFunction(currentKey);
// Loops till current hashValue index position value is not "-"
// and current hashValue index position value is not null
while(hashArray[hashValue].getKeyData() != "-" &&
hashArray[hashValue].getKeyData() != null)
{
// Checks current hashValue index position value is equals
// to the parameter currentKey value
if(hashArray[hashValue].getKeyData().equals(currentKey))
return hashArray[hashValue];
// Increase the hash value by one
++hashValue;
// Calculates the hash value by getting remainder of array size
hashValue %= arraySize;
}// End of while loop
return null;
}// End of method
}// End class CreateHashTable
// Driver class FoldingHashTableLinearProbing definition
public class FoldingHashTableLinearProbing
{
// Method to accept and return a string
public static String getString() throws IOException
{
InputStreamReader inpStrRed = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(inpStrRed);
String str = br.readLine();
return str;
}// End of method
// Method to accept a string and return a character
public static char getCharacter() throws IOException
{
String str = getString();
return str.charAt(0);
}// End of method
// Method to accept a string and return a integer
public static int getInteger() throws IOException
{
String str = getString();
return Integer.parseInt(str);
}// End of method
// main method definition
public static void main(String[] args) throws IOException
{
// Declares an object of class Items
Items newDataItem;
int maximumSize, initialNum, keysPerCell;
String currentKey;
// Accepts the table size
System.out.print("Enter size of hash table: ");
maximumSize = getInteger();
// Accepts initial number of items
System.out.print("Enter initial number of items: ");
initialNum = getInteger();
keysPerCell = 20;
// Creates an object of the class CreateHashTable with maximum size
CreateHashTable theHashTable = new CreateHashTable(maximumSize);
// Loops till initial numbers entered by the user
for(int counter = 0; counter < initialNum; counter++)
{
currentKey = Double.toString((java.lang.Math.random() *
keysPerCell * maximumSize));
newDataItem = new Items(currentKey);
theHashTable.insertItem(newDataItem);
}// End of for loop
// Loops infinite times
while(true)
{
// Displays menu
System.out.print("\n\n ********* MENU *********" +
"\n (S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data " +
" (Q)uit." +
"\n Enter first letter: ");
// Accepts user choice
char userChoice = getCharacter();
// Checks user choice and calls appropriate method
switch(userChoice)
{
case 'S':
case 's':
theHashTable.displayHahsTable();
break;
case 'I':
case 'i':
System.out.print("Enter string to Insert: ");
currentKey = getString();
newDataItem = new Items(currentKey);
theHashTable.insertItem(newDataItem);
break;
case 'D':
case 'd':
System.out.print("Enter string to Delete: ");
currentKey = getString();
theHashTable.deleteItem(currentKey);
break;
case 'F':
case 'f':
System.out.print("Enter string to Search: ");
currentKey = getString();
newDataItem = theHashTable.searchItem(currentKey);
if(newDataItem != null)
System.out.println("Found " + currentKey);
else
System.out.println("Could not find " + currentKey);
break;
case 'Q':
case 'q':
System.exit(0);
default:
System.out.println("Invalid choice..........");
}// End of switch - case
}// End of while loop
}// End of main method
}// End of class CreateHashTable
Sample Output:
Enter size of hash table: 10
Enter initial number of items: 2
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: i
Enter string to Insert: this
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
-
-
-
184.4919594690628
this
-
143.5796767054561
-
-
-
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: i
Enter string to Insert: those
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
-
-
-
184.4919594690628
this
those
143.5796767054561
-
-
-
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: i
Enter string to Insert: that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
-
-
-
184.4919594690628
this
those
143.5796767054561
-
-
that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: i
Enter string to Insert: There
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: S
Table:
-
-
-
184.4919594690628
this
those
143.5796767054561
There
-
that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: I
Enter string to Insert: Them
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
-
-
-
184.4919594690628
this
those
143.5796767054561
There
Them
that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: i
Enter string to Insert: Apple
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
Apple
-
-
184.4919594690628
this
those
143.5796767054561
There
Them
that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: F
Enter string to Search: babana
Could not find babana
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: f
Enter string to Search: Apple
Found Apple
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: d
Enter string to Delete: Apple
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: s
Table:
-
-
-
184.4919594690628
this
those
143.5796767054561
There
Them
that
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: m
Invalid choice..........
********* MENU *********
(S)how Result, (I)nsert Data, (D)elete Data, (F)ind Data
(Q)uit.
Enter first letter: q
Write a hash function to implement a digit-folding approach in the hash function. Your program should...
Write a hash function to implement a digit-folding approach in the hash function. Your program should work for any array size and any key length. Use linear probing. Accessing a group of digits in a number may be easier than you think. Does it matter if the array size is not a multiple of 10?(Written in Java)
This should be in Java Create a simple hash table You should use an array for the hash table, start with a size of 5 and when you get to 80% capacity double the size of your array each time. You should create a class to hold the data, which will be a key, value pair You should use an integer for you key, and a String for your value. For this lab assignment, we will keep it simple Use...
The task of this project is to implement in Java Hash Table structure using Linear Probing Collision Strategy. You can assume that no duplicates or allowed and perform lazy deletion (similar to BST). Specification Create a generic class called HashTableLinearProbe <K,V>, where K is the key and V is the value. It should contain a private static class, HashEntry<K,V>. Use this class to create array to represent Hashtable: HashEntry<K,V> hashtable[]; Implement all methods listed below and test each method...
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...
Write a program in Java to implement a recursive boolean function that returns True if the given array contents remain the same when the array is reversed. Otherwise function must return False.
IN JAVA USING ECLIPSE The objective of this assignment is to create your own hash table class to hold employees and their ID numbers. You'll create an employee class to hold each person's key (id number) and value (name). Flow of the main program: Create an instance of your hash table class in your main method. Read in the Employees.txt file and store the names and ID numbers into Employee objects and store those in your hash table using the...
Write a program to subtract large unsigned integers. Your program should prompt and read in two large unsigned integers. The two large integers should be stored arrays, one array for each integer. The integers should be stored with one digit per location in the two arrays. The first integer should be no smaller than the second. Your program should subtract the second integer from the first. The result should be stored in an array, again one digit per location in...
Write a c++ program that does the following Create an integer array of size 30. Assign -1 to each location in the array indicating that the array is empty. Populate half of the array with random integer values between 100 and 500 inclusive. Use the following formula in order to hash and store each number in its proper position/location. Generated Number Table Size: Should a collision occurs, use linear probing to find next available position location. Use the following probing...
** C++ LANGUAGE ** Write a function that will implement each Fibonacci number with the help of an integer array of size 100 (elements of this array will be digits of the Fibonacci number). When the function is called to find , it will calculate all Fibonacci numbers from to using the basic formula . To add two Fibonacci numbers, the function will add elements of two arrays corresponding to and and store their sums in the array corresponding to...
please use Java!! We are storing the inventory for our fruit stand in a hash table. The attached file shows all the possible key/fruit combinations that can be inserted into your hash table. These are the real price lookup values for the corresponding fruit. Problem Description In this programming assignment, you will implement a hash table class fruitHash. Your hash table must include the following methods: 1) hashFunction(key) This method takes a key as an argument and returns the address...