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)
//please find the below code
import java.io.*;
class FoldingHashTable
{
private HashDataItem[] hashArray;
private int arraySize;
private HashDataItem nonItem;
public FoldingHashTable(int size)
{
arraySize = size;
hashArray = new
HashDataItem[arraySize];
nonItem = new HashDataItem(-1);
//deleted item key is -1
}
public void displayTable()
{
System.out.print("Table: ");
for(int j = 0; j < arraySize;
j++)
{
if(hashArray[j]
!= null)
System.out.print(hashArray[j].getKey() + "
");
else
System.out.print("** ");
}
System.out.println("");
}
//folds the key into groups of digits and adds the
groups
public int hashFunc(int key)
{
int groupSize = 1;
int temp = arraySize;
int hashVal = 0;
while(temp > 0)
{
temp /=
10;
groupSize *=
10;
}
while(key > 0)
{
hashVal += key %
groupSize;
key /=
groupSize;
}
return hashVal;
}
public void insert(HashDataItem item)
{
//assumes table not full
int key = item.getKey();
int hashVal = hashFunc(key);
while(hashArray[hashVal] != null
&& hashArray[hashVal].getKey() != -1)
{
++hashVal;
hashVal %=
arraySize;
}
hashArray[hashVal] = item;
}
public HashDataItem delete(int key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal] !=
null)
{
if(hashArray[hashVal].getKey() == key)
{
HashDataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
return temp;
}
++hashVal;
hashVal %=
arraySize;
}
return null;
}
public HashDataItem find(int key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal] !=
null)
{
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal];
++hashVal;
hashVal %=
arraySize;
}
return null;
}
} //end class HashTable
public class FoldingHashTableApp
{
public static void main(String[] args) throws
IOException
{
HashDataItem aDataItem;
int aKey, size, n,
keysPerCell;
System.out.print("Enter size of
hash table: ");
size = getInt();
System.out.print("Enter initial
number of items: ");
n = getInt();
keysPerCell = 10;
HashTable theHashTable = new
HashTable(size);
for(int j=0; j<n; j++)
{
aKey =
(int)(java.lang.Math.random() * keysPerCell * size);
aDataItem = new
HashDataItem(aKey);
theHashTable.insert(aDataItem);
}
while(true)
{
System.out.print("Enter first letter of show, insert, delete, or
find: ");
char choice =
getChar();
switch(choice)
{
case 's':
theHashTable.displayTable();
break;
case 'i':
System.out.print("Enter key value to insert:
");
aKey = getInt();
aDataItem = new HashDataItem(aKey);
theHashTable.insert(aDataItem);
break;
case 'd':
System.out.print("Enter key value to delete:
");
aKey = getInt();
theHashTable.delete(aKey);
break;
case 'f':
System.out.print("Enter key value to find:
");
aKey = getInt();
aDataItem = theHashTable.find(aKey);
if(aDataItem != null)
System.out.println("Found " +
aKey);
else
System.out.println("Could not
find " + aKey);
break;
default:
System.out.println("Invalid entry!");
}
}
}//end main
public static String getString() throws
IOException
{
InputStreamReader isr = new
InputStreamReader(System.in);
BufferedReader br = new
BufferedReader(isr);
String s = br.readLine();
return s;
}
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
} //end HashTableApp
import java.io.*;
class HashDataItem
{
private int iData;
public HashDataItem(int ii)
{ iData = ii; }
public int getKey()
{ return iData; }
}
class HashTable
{
private HashDataItem[] hashArray;
private int arraySize;
private HashDataItem nonItem;
private double numItems; //used to
determine loadFactor
public HashTable(int size)
{
numItems = 0;
arraySize = size;
hashArray = new
HashDataItem[arraySize];
nonItem = new HashDataItem(-1);
//deleted item key is -1
}
public void displayTable()
{
System.out.print("Table: ");
for(int j = 0; j < arraySize;
j++)
{
if(hashArray[j]
!= null)
System.out.print(hashArray[j].getKey() + "
");
else
System.out.print("** ");
}
System.out.println("");
}
public double getLoadFactor()
{ return (numItems / (double)arraySize); }
public HashTable rehash()
{
//create a new table based on the
original one
int newSize =
getPrime(arraySize*2);
HashTable newTable = new
HashTable(newSize);
newTable.setNumItems(numItems);
//transfer numItems from oldtable to newtable
//for all the values in the old
hash table, re-insert them into the new table.
for(int j = 0; j < arraySize;
j++)
{
if(hashArray[j]
!= null && hashArray[j].getKey() != -1)
newTable.rehashInsert(hashArray[j],
newSize);
}
//then return that table
return newTable;
}
private int getPrime(int min) //returns
1st prime > min
{
for(int j = min+1; true; j++)
if( isPrime(j) )
return j;
}
private boolean isPrime(int n)
{
for(int j = 2; (j*j <= n);
j++)
if(n%j ==
0)
return false;
return true;
}
public int hashFunc(int key)
{
return key % arraySize;
}
//used by rehash() to calculate new locations for
keys
private void rehashInsert(HashDataItem item, int
size)
{
//assumes table not full
int key = item.getKey();
int hashVal = key % size;
while(hashArray[hashVal] != null
&& hashArray[hashVal].getKey() != -1)
{
++hashVal;
hashVal %=
arraySize;
}
hashArray[hashVal] = item;
}
private void setNumItems(double number)
{ numItems = number; }
public void insert(HashDataItem item)
{
//assumes table not full
int key = item.getKey();
int hashVal = hashFunc(key);
while(hashArray[hashVal] != null
&& hashArray[hashVal].getKey() != -1)
{
++hashVal;
hashVal %=
arraySize;
}
hashArray[hashVal] = item;
numItems++;
}
public HashDataItem delete(int key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal] !=
null)
{
if(hashArray[hashVal].getKey() == key)
{
HashDataItem temp = hashArray[hashVal];
hashArray[hashVal] = nonItem;
numItems--;
return temp;
}
++hashVal;
hashVal %=
arraySize;
}
return null;
}
public HashDataItem find(int key)
{
int hashVal = hashFunc(key);
while(hashArray[hashVal] !=
null)
{
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal];
++hashVal;
hashVal %=
arraySize;
}
return null;
}
}
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? #java#withcomments please
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...