class Fruit{
private String fruitName;
private int key;
private boolean isDeleted;
public Fruit(){
}
public Fruit(String name, int k, boolean
isDel){
fruitName = name;
isDeleted = isDel;
key = k;
}
public String getFruitName(){
return fruitName;
}
public int getKey(){
return key;
}
public boolean isDeleted(){
return isDeleted;
}
public void setFruitName(String name){
fruitName = name;
}
public void setKey(int k){
key = k;
}
public void setDeleted(boolean b){
isDeleted = b;
}
}
class fruitHash{
private Fruit[] fruitTable;
private int tableSize;
public fruitHash(int size){
fruitTable = new
Fruit[size];
tableSize = size;
for(int i = 0; i <
tableSize; i++)
fruitTable[i] = null;
}
public int size(){
return tableSize;
}
public void insert(int key, String data){
int k =
hashFunction(key);
if(fruitTable[k] !=
null){
int k2 = doubleHash(key);
if(fruitTable[k2] != null){
int k3 = linearHash(key);
if(k3 == -1){
System.out.println("Error: Table is full, cannot insert
'"+data+"'");
return;
}
fruitTable[k3] = new Fruit(data, key, false);
}else{
fruitTable[k2] = new Fruit(data, key, false);
}
}else{
fruitTable[k] = new Fruit(data, key, false);
}
}
String find(int key){
int k =
hashFunction(key);
if(fruitTable[k] ==
null){
int k2 = doubleHash(key);
if(fruitTable[k2] == null){
int k3 = linearHash(key);
if(k3 == -1){
return null;
}
if(fruitTable[k3].isDeleted())
return null;
if (fruitTable[k3].getKey() == key) {
return fruitTable[k3].getFruitName();
}
return null;
}else{
if(fruitTable[k2].isDeleted())
return null;
if (fruitTable[k2].getKey() == key) {
return fruitTable[k2].getFruitName();
}
return null;
}
}else{
if(fruitTable[k].isDeleted())
return null;
if (fruitTable[k].getKey() == key) {
return fruitTable[k].getFruitName();
}
return null;
}
}
public void rehash(){
tableSize *= 2;
Fruit[] newtable = new
Fruit[tableSize];
for(int i = 0; i <
tableSize; i++)
newtable[i] = null;
for(int i = 0; i <
tableSize/2; i++){
if(fruitTable[i] != null &&
!fruitTable[i].isDeleted()){
int key = fruitTable[i].getKey();
int k = hashFunction(key);
if (newtable[k] != null) {
int k2 = doubleHash(key);
if (newtable[k2] != null) {
int k3 = linearHash(key);
if (k3 == -1) {
System.out.println("Error: Table is full!");
return;
}
newtable[k3] = new Fruit(fruitTable[i].getFruitName(), key,
false);
} else {
newtable[k2] = new Fruit(fruitTable[i].getFruitName(), key,
false);
}
} else {
newtable[k] = new Fruit(fruitTable[i].getFruitName(), key,
false);
}
}
}
fruitTable =
newtable;
}
public void printTable(){
System.out.println("FruitTable:");
for(int i = 0; i <
tableSize; i++){
if(fruitTable[i] != null &&
!fruitTable[i].isDeleted()){
System.out.println(" key: " + fruitTable[i].getKey() + ", value: "
+ fruitTable[i].getFruitName());
}
}
}
public void delete(int key){
int k =
hashFunction(key);
if(fruitTable[k] ==
null){
int k2 = doubleHash(key);
if(fruitTable[k2] == null){
int k3 = linearHash(key);
if(k3 > 0){
fruitTable[k3].setDeleted(true);
}
}else{
fruitTable[k2].setDeleted(true);
}
}else{
fruitTable[k].setDeleted(true);
}
}
private int hashFunction(int key){
return key %
tableSize;
}
private int linearHash(int key){
int k = key %
tableSize;
int index = k;
while(index <
tableSize){
if(fruitTable[index] == null)
return index;
if(fruitTable[index] != null &&
fruitTable[index].isDeleted())
return index;
index++;
}
index = 0;
while(index <
k){
if(fruitTable[index] == null)
return index;
if(fruitTable[index] != null &&
fruitTable[index].isDeleted())
return index;
index++;
}
return -1;
}
private int doubleHash(int key){
int k = key %
tableSize;
int k2 = 7 - (key %
7);
int k2temp = k2, index =
k;
while(k2temp >
0){
index++;
if(index >= tableSize)
index = 0;
k2temp--;
}
return index;
}
}
public class FruitTable {
public static void main(String[] args)
{
fruitHash fhash = new
fruitHash(10);
System.out.println("Table size: "+fhash.size());
fhash.insert(4514,
"alfafa sprouts");
fhash.insert(4131,
"apple fuji");
fhash.insert(4133,
"apple gala");
fhash.insert(4017,
"apple granny smith");
fhash.insert(4218,
"apricots");
fhash.insert(4525,
"asparagus");
fhash.insert(4225,
"avocado large hass");
fhash.insert(4227,
"avocado small");
fhash.insert(4234,
"banana leaf");
fhash.insert(4011,
"banana");
fhash.insert(4232,
"banana baby");
fhash.insert(4229,
"banana burro");
fhash.insert(4235,
"banana macho");
fhash.insert(4885,
"basil");
fhash.insert(4536, "bean
sprouts");
fhash.insert(3176,
"beans black");
fhash.insert(3196,
"beans back eye");
fhash.insert(3174,
"beans garbanzo");
fhash.insert(4066,
"beans green");
fhash.insert(3175,
"beans haba dry");
fhash.printTable();
System.out.println("Find
4131: "+fhash.find(4131));
System.out.println("Find
4011: "+fhash.find(4011));
System.out.println("Find
4525: "+fhash.find(4525));
}
}
please use Java!! We are storing the inventory for our fruit stand in a hash table....
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...
5. Hashing (a) Consider a hash table with separate chaining of size M = 5 and the hash function h(x) = x mod 5. i. (1) Pick 8 random numbers in the range of 10 to 99 and write the numbers in the picked sequence. Marks will only be given for proper random numbers (e.g., 11, 12, 13, 14 ... or 10, 20, 30, 40, .. are not acceptable random sequences). ii. (2) Draw a sketch of the hash table...
#3 [3 points] Sketch a hash table of size N=11, where the hash function is hash(key) = key mod N and quadratic probing is used to resolve collisions, after the following elements are inserted: 20, 42, 45, 49, 62, 72, 95. The probes are based on this equation: (H+c1∗i+c2∗i2)mod(N) and c1=1, c2=1. If direct hashing was used to store the same elements as the previous problems (20, 42, 45, 49, 62, 72, 95), what should be the minimum size of...
Suppose you have the following hash table, implemented using linear probing. The hash function we are using is the identity function, h(x) = x. 0 1 2 3 4 5 6 7 8 9 8 12 3 14 4 21 In which order could the elements have been added to the hash table? There are more than one correct answers, and you should give all of them. Assume that the hash table has never been resized, and no elements have...
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...
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers keys in post-order - Retrieve the integers keys in pre-order - Draw a binary search tree after node 58 is deleted b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that...
Java using data structures The objective is to create your own Hash Table class to hold a list of employees and their ID numbers. I've provided the TableEntry class which will be each data object in the hash table. The list of employees will be provided as a .txt file and must be read with the code. please create a .txt file called Employees.txt with the info provided so that the java code can read it in. Employees.txt: (No WhiteSpace...
C programming Problem 3 [Set via Hashing] As mentioned in the lecture, a hash table can be used to implement a Set ADT. Let's try to use the template below to implement a Set with double hashing. Here we assume the Set contains names with 3 characters long. Since it is a Set, we do not need to have an explicit value for each key. We will use a token value of 1 if a name belongs to the Set....
Tree & Hash Table & Heap Use the following integer keys 73, 58, 91, 42, 60, 130, 64, 87 to perform the followings: a) Binary Search Tree - Draw a binary search tree - Retrieve the integers keys in post-order - Retrieve the integers keys in pre-order - Draw a binary search tree after node 58 is deleted b) Create a Hash Table using the methods described below. Show the final array after all integer keys are inserted. Assumes that...