ArrayIndexOutOfBoundsException 当我通过数组长度修改索引时
ArrayIndexOutOfBoundsException when I'm modding the index by the array length
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);
}
}
所以我目前正在为学校课程编写一个线性探测开放哈希 table,并且我提供了我的哈希 table 代码,以及我用来测试它的代码.我遇到了最令人困惑的错误:
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)
我不明白当我按数组大小进行修改时,我怎么会得到一个越界的索引。此外,当我检查出现此错误时数组的大小时,它告诉我 20,这意味着 10 不应导致索引越界...我错过了什么?
您的问题似乎在 resize
。
您迭代新的(更大的)后备数组的索引,同时访问旧的(更小的)后备数组的元素:
for (int i = 0; i < backingArr.length; i++) {
if (valid[i]) { // Don't add deleted elements
add(oldBackingArr[i]);
}
}
您或许应该将循环的条件更改为 i < oldBackingArr.length
。
编辑:正如 Thomas 评论的那样,您还应该在调整 backingArr
数组大小时调整 valid
数组的大小。
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);
}
}
所以我目前正在为学校课程编写一个线性探测开放哈希 table,并且我提供了我的哈希 table 代码,以及我用来测试它的代码.我遇到了最令人困惑的错误:
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)
我不明白当我按数组大小进行修改时,我怎么会得到一个越界的索引。此外,当我检查出现此错误时数组的大小时,它告诉我 20,这意味着 10 不应导致索引越界...我错过了什么?
您的问题似乎在 resize
。
您迭代新的(更大的)后备数组的索引,同时访问旧的(更小的)后备数组的元素:
for (int i = 0; i < backingArr.length; i++) {
if (valid[i]) { // Don't add deleted elements
add(oldBackingArr[i]);
}
}
您或许应该将循环的条件更改为 i < oldBackingArr.length
。
编辑:正如 Thomas 评论的那样,您还应该在调整 backingArr
数组大小时调整 valid
数组的大小。