Created
December 31, 2016 13:34
-
-
Save anonymous/cec58a2ad9f122874ef11c50cad8b3ea to your computer and use it in GitHub Desktop.
HashTable implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package myHashTable; | |
import java.util.Arrays; | |
public class myHash { | |
private int capacity; | |
private double max_load_factor; | |
private int resize_factor = 2; | |
private int search_limit = 0; | |
private int probing_type; | |
private int[] HT_1; | |
private int locationUsed = 0; | |
public myHash(int capacity, double max_load_factor, int resize_factor, int PROBING_TYPE){ | |
this.capacity = capacity; | |
this.max_load_factor = max_load_factor; | |
this.resize_factor = resize_factor; | |
this.probing_type = PROBING_TYPE; | |
HT_1 = new int[capacity]; | |
} | |
public void add(int key){ | |
int hashIndex = hashFunction(key); | |
if(probing_type == 1){ | |
while(HT_1[hashIndex] != 0 ){ | |
hashIndex++; | |
hashIndex %= capacity; | |
} | |
HT_1[hashIndex] = key; | |
locationUsed++; | |
} | |
else{ | |
int i = 0; | |
while(HT_1[hashIndex] != 0 && search_limit < 100){ | |
hashIndex = hashIndex + i * i; | |
hashIndex %= capacity; | |
i++; | |
search_limit++; | |
} | |
HT_1[hashIndex] = key; | |
locationUsed++; | |
i = 0; | |
} | |
if(isHTFull()){ | |
rehash(); | |
} | |
} | |
private void rehash(){ | |
int[] oldvalues = HT_1; | |
HT_1 = new int[capacity * resize_factor]; | |
for(int i = 0; i < 2; i++){ | |
this.add(oldvalues[i]); | |
} | |
System.out.println(Arrays.toString(oldvalues)); | |
// System.out.println(Arrays.toString(HT_1)); | |
} | |
public int hashFunction(int key){ | |
return key % capacity; | |
} | |
private boolean isHTFull() | |
{ | |
return locationUsed > max_load_factor * capacity; | |
} | |
public void printHashTable() | |
{ | |
System.out.println(Arrays.toString(HT_1)); | |
// System.out.println(Arrays.toString(HT_2)); | |
// System.out.print(capacity * resize_factor); | |
System.out.print(locationUsed); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment