Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Naive implementation of a hash table.
import java.util.Arrays;
/**
* Author: Phillip Johnson
* Date: 3/15/14.
*/
public class NaiveHashTable {
private Object[][] hashTable;
private static final int MAX_EQUAL_HASHES = 8;
public NaiveHashTable(){
hashTable = new Object[32][1];
}
public void add(Object o){
hashTable = add(o,hashTable,true);
}
private int findSlot(Object o, Object[][] home){
return o.hashCode() & (home.length - 1);
}
private Object[][] add(Object o, Object[][] home, boolean checkRehash){
insertItem(o,home);
if(checkRehash){
int justInsetertedSlot = findSlot(o,home);
Object[] objects = home[justInsetertedSlot];
if (objects.length > MAX_EQUAL_HASHES) {
home = rehash(home);
}
}
return home;
}
private boolean insertItem(Object o, Object[][] home){
int slot = findSlot(o,home);
Object[] objects = home[slot];
if(objects == null){
objects = new Object[1];
}
//Check to see if the hash collision array is full
if(objects[objects.length - 1] != null){
objects = growArray(objects);
//Since we got a copy, re-assign its pointer
home[slot] = objects;
}
for (int i = 0; i < objects.length; i++) {
//Do not store duplicate object in the table
if(objects[i] != null && objects[i].equals(o)){
return false;
}
//Store this object in the next available spot
if(objects[i] == null){
objects[i] = o;
break;
}
}
return true;
}
public boolean contains(Object o){
if(o == null){
return false;
}
int slot = findSlot(o,hashTable);
Object[] objects = hashTable[slot];
for(Object object : objects){
if(o.equals(object)){
return true;
}
}
return false;
}
private <T> T[] growArray(T[] arrayToGrow){
arrayToGrow = Arrays.copyOf(arrayToGrow, arrayToGrow.length * 2);
return arrayToGrow;
}
private Object[][] rehash(Object[][] toRehash){
if(toRehash.length *2 < Integer.MAX_VALUE){
Object[][] newTable = new Object[toRehash.length * 2][1];
for (Object[] objects : toRehash) {
for (Object object : objects) {
if(object != null){
add(object, newTable,false);
}
}
}
return newTable;
}
//Unable to rehash, array would be too large
return toRehash;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment