public class OpenHashTable {
int[] backingArr;
/* Valid is a boolean array that keeps track of whether the hashcode in
the backingArr has been "deleted" or not. False == deleted */
boolean[] valid;
int numElements;
double loadFactor;
double maxLoad;
public OpenHashTable() {
this(0.8);
}
public OpenHashTable(double maxLoad) {
this(null, maxLoad);
}
public OpenHashTable(int[] hashCodes, double maxLoad) {
this.maxLoad = maxLoad <= 1.0 ? maxLoad : 0.8; /* An open hashtable
cannot exceed a loadfactor of 1.0 */
this.loadFactor = 0.0;
int numElements = 0;
if (hashCodes != null) {
/* We create a new backing array so that the load factor is
initally 1/2 of the max load factor. This was arbitrarily
chosen. */
backingArr = new int[(int) (maxLoad / 2 * hashCodes.length)];
valid = new boolean[backingArr.length];
add(hashCodes);
} else {
backingArr = new int[10];
valid = new boolean[backingArr.length];
}
}
public boolean add(int hashcode) {
if (loadFactor >= maxLoad) {
resize();
}
int index = Math.abs(hashcode % backingArr.length);
if (!valid[index]) {
/* If valid at the given index is false, then the backingArray is
"empty" at that spot, so we add the hashcode to the table,
update the loadFactor, and return true to show that the code was
added */
backingArr[index] = hashcode;
valid[index] = true;
numElements++;
loadFactor = (double) numElements / backingArr.length;
// if (loadFactor >= maxLoad) {
// resize();
// }
return true;
} else {
// System.out.printf("%d,%d;", index, backingArr.length);
while (valid[index % backingArr.length]
&& backingArr[index % backingArr.length] != hashcode) {
/* Search the table for the first open spot, or stop when you
find the hashcode in the table. If the current index is the
same as hashcode, then we stop before incrementing index.
Otherwise, we keep searching for an empty spot */
index++;
}
if (backingArr[index % backingArr.length] != hashcode) {
backingArr[index % backingArr.length] = hashcode;
valid[index % backingArr.length] = true;
numElements++;
loadFactor = (double) numElements / backingArr.length;
return true;
} else {
return false;
/* The given hashcode already existed in the table, so the data
was not added */
}
}
}
public boolean add(int[] hashcodes) {
boolean success = true;
for (int x: hashcodes) {
success = success && add(x);
/* Once adding a hashcode fails once, success will always be
false */
}
return success;
/* This will only return true if all data was added succesfully */
}
public void resize() {
int[] oldBackingArr = backingArr;
backingArr = new int[oldBackingArr.length * 2];
loadFactor = (double) numElements / backingArr.length;
for (int i = 0; i < backingArr.length; i++) {
if (valid[i]) { // Don't add deleted elements
add(oldBackingArr[i]);
}
}
/* The new load factor should be automatically updated when we call
add */
}
public String toString() {
String returned = "";
for (int i = 0; i < backingArr.length; i++) {
returned += "[" + i + "]: ";
if (valid[i]) {
returned += backingArr[i] + " ";
} else {
returned += "- ";
}
}
return returned;
}
}
public class OpenHashTest {
private static OpenHashTable hashTable = new OpenHashTable();
private static String[] data = {"Emma", "Olivia", "Sophia", "Isabella", "Ava", "Mia",
"Emily", "Abigail", "Madison", "Charlotte", "Harper",
"Sofia", "Avery", "Elizabeth", "Amelia", "Evelyn", "Ella",
"Chloe", "Victoria", "Aubrey", "Grace", "Zoey", "Natalie",
"Addison", "Lillian", "Brooklyn", "Lily", "Hannah", "Layla",
"Scarlet"};
public static void main(String... args) {
int[] hashcodes = new int[data.length];
for (int i = 0; i < data.length; i++) {
hashcodes[i] = data[i].hashCode();
}
hashTable.add(hashcodes);
System.out.println(hashTable);
}
}
So I'm currently writing a linear probing open hash table for a school course, and I've provided my hash table code, and the code I'm using to test it. I am getting the most baffling error:
java : Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at OpenHashTable.add(OpenHashTable.java:60)
at OpenHashTable.resize(OpenHashTable.java:103)
at OpenHashTable.add(OpenHashTable.java:39)
at OpenHashTable.add(OpenHashTable.java:87)
at OpenHashTest.main(OpenHashTest.java:15)
I don't understand how I can be getting an index out of bounds when I'm modding by the array size. Also, when I check to see what size the array is at the time of this error, it tells me 20, which means 10 should not cause an index out of bounds... What am I missing?
