. Create a data set with 100 integer values. Create a program that uses the divi

Question

. Create a data set with 100 integer values. Create a program that uses the division method of hashing to store the data values into hash tables with table sizes of 7, 51, and 151. Use the linear probing method of collision resolution. Print out the tables after the data values have been stored. Search for 10 different values in each of the three hash tables, counting the number of comparisons necessary. Print out the number of comparisons necessary in each case in tabular form. Share a listing of your program and output. Review other program from your classmates and discuss differences.

Explanation / Answer

// Main function

package linearprobehashing;

import java.util.Random;

public class LinearProbeHashing {

public static void main(String[] args) {
//to store 100 integer values.
int dataSet[]=new int[100];
Random randomGenerator = new Random();
int i;
for (i = 0; i < 100; i++)
{
int randomInt = randomGenerator.nextInt(100);
dataSet[i]=randomInt;
}
int tableSize[]={7,51,151};
HashTable H1 = new HashTable(tableSize[0]);
HashTable H2 = new HashTable(tableSize[1]);
HashTable H3 = new HashTable(tableSize[2]);
for(i=0;i<100;i++)
{
H1.insert(dataSet[i]);
H2.insert(dataSet[i]);
H3.insert(dataSet[i]);
}
System.out.println(" Hash Table1: ");
H1.printHashTable();
System.out.println(" Hash Table2: ");
H2.printHashTable();
System.out.println(" Hash Table3: ");
H3.printHashTable();
int searchSet[]=new int[10];
for (i = 0; i < 10; i++)
{
int randomInt = randomGenerator.nextInt(100);
searchSet[i]=randomInt;
}
int count[]=new int[3];
for (i = 0; i < 3; i++)
{
count[i]=0;
}
for (i = 0; i < 10; i++)
{
count[0]+=H1.search(searchSet[i]);
}
System.out.println(tableSize[0]+" "+count[0]);
for (i = 0; i < 10; i++)
{
count[1]+=H2.search(searchSet[i]);
}
System.out.println(tableSize[1]+" "+count[1]);   
for (i = 0; i < 10; i++)
{
count[2]+=H3.search(searchSet[i]);
}
System.out.println(tableSize[2]+" "+count[2]);
System.out.println("Table sizes Vs Comparisions");
for (i = 0; i < 3; i++)
{
System.out.println(tableSize[i]+" "+count[i]);
}
}
}

//=================================================

// HashTable implementation

public class HashTable {
private int currentSize, maxSize;   
private int[] key;

/** Constructor **/
public HashTable(int capacity)
{
currentSize = 0;
maxSize = capacity;
key = new int[maxSize];
for(int i=0;i<maxSize;i++)
key[i] =0;
}

/** Function to get size of hash table **/
public int getSize()
{
return currentSize;
}

/** Function to check if hash table is full **/
public boolean isFull()
{
return currentSize == maxSize;
}

/** Function to check if hash table is empty **/
public boolean isEmpty()
{
return getSize() == 0;
}

/* Function to get hash code of a given key **/
private int hash(int key)
{
return key % maxSize;
}

/** Function to insert key-value pair **/
public void insert(int data)
{
int tmp = hash(data);
int i = tmp;
do
{
if(key[i] == 0)
{
key[i] = data;
currentSize++;
return;
}   
//division method of hashing
i = (i + 1) % maxSize;
} while (i != tmp);   
}

/** Function to get value for a given key **/
public int search(int k)
{
int i = hash(k);
int flag=0, count=0;
while(key[i]!=0)
{
count++;
if(key[i]==k)
{
flag=1;
break;
}
i = (i + 1) % maxSize;
}
return count;
}


/** Function to print HashTable **/
public void printHashTable()
{
for (int i = 0; i < maxSize; i++)
if (key[i] !=0)
System.out.println(i+" "+key[i]);
System.out.println();
}   
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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