In JAVA I am using Data Structure and algorithms in Java Second Edition Program
ID: 3700536 • Letter: I
Question
In JAVA
I am using Data Structure and algorithms in Java Second Edition
Program Must Compile and run!
Write a hash function to implement a digit-folding approach in the hash function
(as described in the “Hash Functions” section of this chapter). 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?
MUST COMPILE AND RUN ,PLEASE DISPLAY OUTPUT
Please include main method below with program
public static void main(String[] args) throws IOException
{
DataItem aDataItem;
int aKey, size, n, maxKeyVal;
// get sizes
System.out.println("(Try size=1000, N=3, max=1000000)");
System.out.print("Enter size of hash table: ");
size = getInt();
System.out.print("Enter number of items: ");
n = getInt();
System.out.print("Enter max key value: ");
maxKeyVal = getInt();
// make table
HashTable theHashTable = new HashTable(size);
for(int j=0; j<n; j++) // insert data
{
aKey = (int)(java.lang.Math.random() * maxKeyVal);
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
}
while(true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("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 DataItem(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.print("Invalid entry ");
} // end switch
} // end while
} // end main()
Output may look like:
(Try size=1000, N=3, max=1000000)
Enter size of hash table: 10
Enter number of items: 4
Enter max key value: 1000000
key=889845, groups are 5+4+8+9+8+8, hashValue is 42, trimmed to 2
key=964039, groups are 9+3+0+4+6+9, hashValue is 31, trimmed to 1
key=806169, groups are 9+6+1+6+0+8, hashValue is 30, trimmed to 0
key=265774, groups are 4+7+7+5+6+2, hashValue is 31, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** ** ** ** ** **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 65789
key=65789, groups are 9+8+7+5+6, hashValue is 35, trimmed to 5
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** 65789 ** ** ** **
Enter first letter of show, insert, delete, or find: i
Enter key value to insert: 98765
key=98765, groups are 5+6+7+8+9, hashValue is 35, trimmed to 5
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 265774 ** 65789 98765 ** ** **
Enter first letter of show, insert, delete, or find: d
Enter key value to delete: 265774
key=265774, groups are 4+7+7+5+6+2, hashValue is 31, trimmed to 1
Enter first letter of show, insert, delete, or find: s
Table: 806169 964039 889845 -1 ** 65789 98765 ** ** **
Enter first letter of show, insert, delete, or find:
Explanation / Answer
I have implemented Hashing with Digital Folding in the following classes along with a driver class to test the Hash Function. Please find the code below and place all public classes in appropriate folders. DataItem class is part of LinearProbingDigitFolding.java. I have written few Exception classes also.
Place the below code in LinearProbingDigitFolding.java file
import java.io.IOException;
import java.lang.annotation.Retention;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class LinearProbingDigitFolding<K,V> {
int tableSize;
DataItem<K, V> table[];
int n;
int foldLength;
/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
@SuppressWarnings("unchecked")
public LinearProbingDigitFolding(int tableSize) {
this.tableSize=tableSize;
n=0;
table=new DataItem[tableSize];
foldLength = String.valueOf(tableSize-1).length();
// for(int i=0;i<tableSize;i++)
// table[i]=(V) new Object();
}
/**
* @param element
* @return Hash address for the given key.
*/
int hash(K key)
{
int address=0;
String k=String.valueOf((Integer)key);
ArrayList<Integer> groups = new ArrayList<Integer>();
int i;
for(i=0;i+foldLength-1< k.length();i+=foldLength)
{
address+=Integer.parseInt(k.substring(i,i+foldLength));
groups.add(Integer.parseInt(k.substring(i,i+foldLength)));
}
if(i<k.length()-1) {
address+=Integer.parseInt(k.substring(i));
groups.add(Integer.parseInt(k.substring(i)));
}
System.out.println("Key = "+key);
System.out.println("Groups are: ");
for (Integer integer : groups) {
System.out.println(integer);
}
System.out.println("Address = "+ address);
address%=tableSize;
System.out.println("Trimmed to = "+ address);
return address%tableSize;
}
private boolean isFreeAddress(int address) {
return table[address]==null;
}
/**
* @param key
* @param value
* @throws HashTableFullException
*/
public void put(K key, V value) throws HashTableFullException
{
DataItem<K, V> entry=new DataItem<K,V>(key,value);
int address=hash(key);
if(isFreeAddress(address))
table[address]=entry;
else
{
int t=address;
address=(address+1)%tableSize;
if(t==address)
throw new HashTableFullException("Table is full. Unable to insert.");
while(!isFreeAddress(address))
{
address=(address+1)%tableSize;
if(t==address)
throw new HashTableFullException("Table is full. Unable to insert.");
}
table[address]=entry;
}
n++;
}
/**
* @param key
* @return Value mapped to the given key otherwise null
* @throws ElementNotFoundException
*/
@SuppressWarnings("unchecked")
public V get(K key) throws ElementNotFoundException
{
DataItem<K, V> entry;
int address=hash(key);
entry=table[address];
if(entry.key.equals(key))
return entry.value;
else
{
int t=address;
address=(address+1)%tableSize;
if(t==address)
return null;
entry=table[address];
while(!entry.key.equals(key))
{
address=(address+1)%tableSize;
if(t==address)
return null;
entry= table[address];
}
return entry.value;
}
}
/**
* @param key
* @return true if any key matches with key otherwise false.
*/
@SuppressWarnings("unchecked")
public boolean containsKey(K key)
{
DataItem<K, V> entry;
int address=hash(key);
entry= table[address];
if(entry.key.equals(key))
return true;
else
{
int t=address;
address=(address+1)%tableSize;
if(t==address)
return false;
entry= table[address];
while(!entry.key.equals(key))
{
address=(address+1)%tableSize;
if(t==address)
return false;
entry= table[address];
}
return true;
}
}
/**
* @param value
* @return true if any key is mapped with given value otherwise false.
*/
@SuppressWarnings("unchecked")
public boolean containsValue(V value)
{
for(int i=0;i<tableSize;i++)
{
if(table[i]!=null)
{
DataItem<K, V> entry=table[i];
if(entry.value.equals(value))
return true;
}
}
return false;
}
/**
* @return all keys as set.
*/
public Set<K> keySet()
{
Set<K> ketSet=new HashSet<K>();
for(int i=0;i<tableSize;i++)
{
if(table[i]!=null)
{
DataItem<K, V> entry=table[i];
ketSet.add(entry.key);
}
}
return ketSet;
}
/**
* @return number of the keys mapped.
*/
public int size() {
// TODO Auto-generated method stub
return n;
}
/**
* @return size of the table.
*/
public int tableSize()
{
return tableSize;
}
/**
* @param i
* @param j
* @param k
* @return true if i is cyclically between j and k otherwise false.
*/
public boolean between(int i,int j,int k)
{
if((i<j&&i<k)||(i>j&&i>k)||(i<j&&i>k))
return false;
else
return true;
}
/**
* @param key
* @return
*/
public V remove(K key)
{
DataItem<K, V> entry;
int address=hash(key);
entry=table[address];
if(entry.key.equals(key))
{
V v=entry.value;
adjustTable(address);
return v;
}
else
{
int t=address;
address=(address+1)%tableSize;
if(t==address)
return null;
entry=table[address];
while(!entry.key.equals(key))
{
address=(address+1)%tableSize;
if(t==address)
return null;
entry= table[address];
}
V v=entry.value;
adjustTable(address);
return v;
}
}
/**
* @param address
*/
private void adjustTable(int address) {
// TODO Auto-generated method stub
table[address]=null;
int deletedAddress=address;
address=(address+1)%tableSize;
while(table[address]!=null)
{
DataItem<K, V> entry=table[address];
int hashAddress=hash(entry.key);
if(hashAddress<=deletedAddress)
{
if(between(deletedAddress, hashAddress, address))
{
table[deletedAddress]=table[address];
table[address]=null;
deletedAddress=address;
address=(address+1)%tableSize;
}
}
else
address=(address+1)%tableSize;
}
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
String s="";
for(int i=0;i<tableSize;i++)
{
if(table[i]!=null)
{
DataItem<K, V> entry=table[i];
s+="Address: "+i+" Key : "+entry.key.toString()+" Value: "+entry.value.toString()+" ";
}
}
return s;
}
}
class DataItem<K, V>
{
K key;
V value;
public DataItem() {
// TODO Auto-generated constructor stub
}
public DataItem(K key, V value) {
this.key = key;
this.value = value;
}
}
Place belo code in LinearProbingDigitFoldingDriver.java file
import java.io.IOException;
import java.util.Scanner;
public class LinearProbingDigitFoldingDriver {
public static void main(String[] args) throws IOException, HashTableFullException
{
DataItem<Integer, Integer> aDataItem;
int aKey, size, n, maxKeyVal;
Scanner sc = new Scanner(System.in);
// get sizes
System.out.println("(Try size=1000, N=3, max=1000000)");
System.out.print("Enter size of hash table: ");
size = sc.nextInt();
System.out.print("Enter number of items: ");
n = sc.nextInt();
System.out.print("Enter max key value: ");
maxKeyVal = sc.nextInt();
// make table
LinearProbingDigitFolding<Integer, Integer> theHashTable = new LinearProbingDigitFolding<Integer, Integer>(size);
for (int j = 0; j < n; j++) // insert data
{
aKey = (int) (java.lang.Math.random() * maxKeyVal);
aDataItem = new DataItem<Integer, Integer>(aKey,aKey);
theHashTable.put(aKey, aKey);
}
while (true) // interact with user
{
System.out.print("Enter first letter of ");
System.out.print("show, insert, delete, or find: ");
char choice = sc.next().charAt(0);
switch (choice)
{
case 's':
System.out.println(theHashTable.toString());
break;
case 'i':
System.out.print("Enter key value to insert: ");
aKey = sc.nextInt();
aDataItem = new DataItem<Integer, Integer>(aKey,aKey);
theHashTable.put(aKey,aKey);
break;
case 'd':
System.out.print("Enter key value to delete: ");
aKey = sc.nextInt();
theHashTable.remove(aKey);
break;
case 'f':
System.out.print("Enter key value to find: ");
aKey = sc.nextInt();
Integer value;
try {
value = theHashTable.get(aKey);
} catch (ElementNotFoundException e) {
// TODO Auto-generated catch block
System.out.println("Could not find " + aKey);
}
System.out.println("Found " + aKey);
break;
default:
System.out.print("Invalid entry ");
} // end switch
} // end while
} // end main()
}
Place below code in ElementNotFoundException.java
public class ElementNotFoundException extends Exception {
public ElementNotFoundException() {
// TODO Auto-generated constructor stub
}
public ElementNotFoundException(String s){
super(s);
}
}
Place below code in HashTableEmptyException.java
public class HashTableEmptyException extends Exception {
public HashTableEmptyException() {
// TODO Auto-generated constructor stub
}
public HashTableEmptyException(String s){
super(s);
}
}
Place below code in HashTableFullException.java
public class HashTableFullException extends Exception {
public HashTableFullException() {
// TODO Auto-generated constructor stub
}
public HashTableFullException(String s){
super(s);
}
}
I hope this helps you. Please comment if you have any more doubts.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.