CC-10 : Implement Hash Search Algorithm.

Description:

The Hash search algorithm uses Hash tables to store and search data elements. The data element is converted to hash value and is stored in an array at an index given by the hash. For searching an element, again we convert the value into a hash Value and check the corresponding index in the array to check if the value is present. Given an input array and an element to be searched, search the required element in the input array using Hash search.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 3, 22, 44, 67, 77, 96, 122, 144, 201,	122 found at index 6 76 found at index -1 3 found at index 0 201 found at index 8

Pseudocode:

Class SearchHashSearch:

Initialize integer variable hashTableSize to 100.

Initialize integer array hastable with size hashTableSize.

Set data values of all indexes of hashtable to -1 in the constructor of the class.

getHash(num):

Set int variable hash to num % hashtable.

Return hash.

insert(num):

Set int variable idx=getHash(num).

While value at index idx is not -1, this means this hash index is already in use, we need to find next possible hash index using below code:

Idx=getHash(idx+1).

Set hashtabel[idx] to num.

hashSearch(num):

Set int variable idx=getHash(num).

While value at index idx is not -1, this means this hash index is in use, we need to check if contains value num:

If hashtable[idx] is equal to num, return idx as num is present at index idx in the hashtable.

If hashtable[idx] not equal to num, we need to find next possible hash index using below code:

Idx=getHash(idx+1).

If we could not find the index of num in the hashtable using above code, then num does not exist in the hashtable, so return -1.

Code:

public class SearchHashSearch {

private int hashTableSize=100;
private int[] hashtable=new int[hashTableSize];

public SearchHashSearch() {
	for (int idx=0;idx < hashtable.length; idx++) {
		hashtable[idx]=-1;
	}
}

public int getHash(int num){
	int hash=num % hashTableSize;
	return hash;
}

public void insert(int num) {
	int idx=getHash(num);
	while (hashtable[idx] != -1) {
		idx=getHash(idx+1);
	}
	hashtable[idx]=num;
}

public int hashSearch(int num) {
	int idx=getHash(num);
	while (hashtable[idx] != -1) {
		if (hashtable[idx]==num) {
			return idx;
		}
		idx=getHash(idx+1);
	}
	return -1;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchHashSearch {

private int hashTableSize=100;
private int[] hashtable=new int[hashTableSize];

public SearchHashSearch() {
	for (int idx=0;idx < hashtable.length; idx++) {
		hashtable[idx]=-1;
	}
}

public int getHash(int num){
	int hash=num % hashTableSize;
	return hash;
}

public void insert(int num) {
	int idx=getHash(num);
	while (hashtable[idx] != -1) {
		idx=getHash(idx+1);
	}
	hashtable[idx]=num;
}

public int hashSearch(int num) {
	int idx=getHash(num);
	while (hashtable[idx] != -1) {
		if (hashtable[idx]==num) {
			return idx;
		}
		idx=getHash(idx+1);
	}
	return -1;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchHashSearch search=new SearchHashSearch();
	int[] nums= { 3,22,44,67,77,96,122, 144, 201};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	for (int idx=0;idx < nums.length; idx++) {
		search.insert(nums[idx]);
	}
		
	int toSearch=122;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n\n"+toSearch + " found at hash "+ retVal);	
	
	toSearch=76;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n"+toSearch + " found at hash "+ retVal);	
	
	toSearch=3;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n"+toSearch + " found at hash "+ retVal);	
	
	toSearch=201;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n"+toSearch + " found at hash "+ retVal);	
	
	toSearch=22;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n"+toSearch + " found at hash "+ retVal);	
	
	toSearch=144;
	retVal=search.hashSearch(toSearch);
	System.out.println("\n"+toSearch + " found at hash "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}


}