JAVA CODING HELP NEEDED! PLEASE READ THE QUESTION , I WILL GIVE BAD REVIEW IF YO

Question

JAVA CODING HELP NEEDED!

PLEASE READ THE QUESTION , I WILL GIVE BAD REVIEW IF YOU DO NOT FOLLOW (ive wasted so many questions on people who dont pay attention to what im asking/ need)

So i have an integer array of size 900

I need to input the elements of the array into a hastable with Quadratic probing of table-size 1009

I need to calculate the number of probes per insertion, so how many probes for keys 0-99 inserting, 100-199, etc. and then print out those values

I am having trouble finding quadratic probing hastable implementation on line.

PLEASE HELP! I NEED THE CODE

Explanation / Answer

import java.util.Random;
import java.util.Stack;
import java.lang.Math;
import java.util.*;

public class QuadraticProbing
{
public static Integer table[] = new Integer[1009];
public static Integer valueCount = 0;
public static boolean resizing = false;

public static class QuadraticHash
{
//Number of traversals
public Integer traversals = 0;

/**
* Name: hashFunction
* Desc: Calculate the hash of the given value.
*/
private Integer hashFunction(Integer value)
{
return (2 * value + 5) % table.length;
}

/**
* Name: loadFactor
* Desc: Return the load factor of the hash table.
*/
private Float loadFactor()
{
return (float) valueCount / table.length;
}

/**
* Name: probe
* Desc: Given a value and whether or not we're looking for an empty space or a value
* this function will return the index cooresponding to the desired value using
* quadratic probing.
*/
private Integer probe(Integer value, Boolean deleting)
{
//Calculate the hash
Integer hash = hashFunction(value);
//Set the index = 0 for the quadratic traversal
Integer index = 0;
//If we're deleting then we're looking for the table entry the value exists in
//else we're looking for an empty space
if(deleting)
{
//While we haven't found the value we're looking for
while(table[hash] != value)
{
traversals++;
//Calculate the next key to check using quadratic probing c1 = 1/2 and c2 = 1/2
//h(k, i) = (h(k) + i/2 + i^2 / 2) % (length of table)
hash = (int) ((hash + (float)index / 2 + (float)(index * index) / 2) % table.length);
//increment index
index++;
}
}
else
{
//Same thing as above just looking for an empty space instead of the value
while(table[hash] != null)
{
traversals++;
hash = (int) ((hash + (float)index / 2 + (float)(index * index) / 2) % table.length);
index++;
}
}
return hash;
}

/**
* Name: resize
* Desc: Shrinks the table if the load factor drops below 0.25 and is greater than 8 elements.
* Grows the table if the load factor is greater than 0.5.
*/
private void resize()
{
resizing = true;
Integer tempTable[] = table;
if(loadFactor() >= 0.5)
{
table = new Integer[tempTable.length * 2];
for(Integer i = 0; i < tempTable.length; i++)
{
if(tempTable[i] != null)
{
insert(tempTable[i]);
}
}
}
else if(loadFactor() <= 0.25 && tempTable.length > 8)
{
table = new Integer[tempTable.length / 2];
for(Integer i = 0; i < tempTable.length; i++)
{
if(tempTable[i] != null)
{
insert(tempTable[i]);
}
}
}
resizing = false;
}

/**
* Name: insert
* Desc: Given an integer value calculate it's hash and insert it into the table
* at the appropriate location.
*/
public Integer insert(Integer value)
{
Integer hash = probe(value, false);
table[hash] = value;
if(!resizing)
{
valueCount++;
resize();
}
return hash;
}

}

public static void main(String[] args)
{

Integer num[] = new Integer[901];
QuadraticHash quadraticHash = new QuadraticHash();
Random rand = new Random();
Integer probe = 0;

for(int j = 0; j < 900; j=j+100)
{
for(int i = j ; i < 100+j; i++)
{
num[i] = rand.nextInt(100) + 1;
probe += quadraticHash.insert(num[i]);

}
System.out.println("Total number of probes are : " + probe);
}

}
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.