Java Quadratic Probing and Lazy Deletion You will be implementing hashtable whic

Question

Java Quadratic Probing and Lazy Deletion

You will be implementing hashtable which uses quadratic probing with Lazy Deletion strategy. If the hash table reachese/exceeds 40% full, you will have to rehash it

public class QuadraticProbing private static final int DEFAULT-TABLE-SIZE = 13; private HashEntry[ array; I/ The array of elements public static class HashEntrycAnyTypex /* initialize the entries here. You can write a constructor for the same */ public AnyType element; public boolean isActive For Lazy deletion public String toString0x if(this.element!-null) return (String) element; else return "NULL"; Construct the hash tablel public QuadraticProbing() this( DEFAULT_TABLE_SIZE); Construct the hash tablel public QuadraticProbing( int size)f allocate memory to hash table '/ * Return true if currentPos exists and is active - Lazy Deletion' public boolean isActive(int position) f return false Find an item in the hash table. " public boolean contains(AnyType x) Should return the active status of key in hash table return false Insert into the Hash Table */ public void insert(AnyType x X Insert an element */ Remove from the hash table. public void remove( AnyType x X Lazy Deletion/ * Rehashing for quadratic probing hash table/ private void rehash(X Resize the hashtable such that the new size is the first prime number greater than two times the current size For example, if current size is 5, then the new size would be 11 Hash Function public int hash( String key, int tableSize X Make sure to type cast "AnyType" to string before calling this method ex: if "x" is of "AnyType you should invoke this function as hash((.toString()), tableSize) int hashVal = 0; P Compute the hash code return hashVal public int probe(AnyType xX Return the number of probes encountered for a key / int num_ of probes 0; return num_of probes

Explanation / Answer

Please give thumb up, thanks

code:

/**
*
* @author VISHAL
*/
public class QuadraticProbing<AnyType>{
private static final int DEFAULT_TABLE_SIZE=13;
private HashEntry<AnyType>[]array;
  
public static class HashEntry<AnyType>
{
public AnyType element;
public boolean isActive;
public String toString()
{
if(this.element!=null)
return (String) element;
else
return "NULL";
}
}
public QuadraticProbing()
{
this(DEFAULT_TABLE_SIZE);
}
public QuadraticProbing(int size)
{
this.array=new HashEntry[size];
for(int i=0; i<array.length; i++)
{
array[i].element=null;
array[i].isActive=false;
}
}
public boolean isActive(int position)
{
if(position>=array.length)
return false;
else
return array[position].isActive;
}
public boolean contains(AnyType x)
{
for(int i=0; i<array.length;i++)
{
if(array[i].element==x)
return true;
}
return false;
}
public void insert(AnyType x)
{
boolean flag=false;
for(int i=0;i<array.length;i++)
{
if(!isActive(i))
flag=false;
}
if(flag==true)
{
rehash();
}
int i=0;
while(true)
{
int y=(hash(x.toString(),array.length));
int hashval=hash(String.valueOf(y+i),array.length);
if(array[hashval].isActive==false)
{
array[hashval].element=x;
array[hashval].isActive=true;
System.out.println("Inserted at "+hashval);
return;
}
i++;
}
}
public void remove(AnyType x)
{
int i=0;
while(true)
{
int y=(hash(x.toString(),array.length));
int hashval=hash(String.valueOf(y+i),array.length);
if(array[hashval].element==x)
{
array[hashval].element=null;
array[hashval].isActive=false;
System.out.println("Deleted from"+hashval);
return;
}
i++;
}
  
}
private void rehash()
{
HashEntry<AnyType> Temp[]=array;
array=new HashEntry[array.length*2];
for(int i=0;i<Temp.length;i++)
{
insert((AnyType) Temp[i]);
}
System.out.println("Table rehashed");
}
public int hash(String key,int tableSize)
{
String x=(String)key;
int hashVal=0;
for(int i=0; i<x.length(); i++)
{
hashVal=(hashVal+x.charAt(i))%tableSize;
}
return hashVal;
}
public int probe(AnyType x)
{
int count=0;
for(int i=0; i<array.length; i++){
if(array[i].element==x)
count++;
}
return count;
}
public static void main(String []args)
{
QuadraticProbing<String> Q=new QuadraticProbing(5);
for(int i=0; i<40; i++)
{
Q.insert(String.valueOf(i));
}
}
  
}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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