ArrayIndexOutOfBoundsException 当我通过数组长度修改索引时

Question

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 不应导致索引越界...我错过了什么？

Answer 1

您的问题似乎在 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 数组的大小。

ArrayIndexOutOfBoundsException 当我通过数组长度修改索引时

ArrayIndexOutOfBoundsException when I'm modding the index by the array length

java

arrays

hashtable

indexoutofboundsexception