Java квадратичное пробирование ArrayIndexOutOfBoundsException

Question

Пыталась сделать заполнение хэш таблицы с квадратичным пробированием, но выдает ArrayIndexOutOfBoundsException. Может кто то сможет подсказать, в чем проблема...

Класс QuadraticProbing

    private int deletedItem;
    ////////////////конструктор
    public QuadraticProbing() // Конструктор
    {
        deletedItem = -1; 
    }
    ////////////////hash function
    public static int hashFunction1(int key) {
        return key % 500; 
    }
    public static int stepCount(int step){
        return  (int) Math.pow(step, 2); //шаг возводится в квадрат
    }
    ///////////////insert
   public static void insert(int item, int[] hashArray) // (Метод предполагает, что таблица не заполнена)
    {
        int i = hashFunction1(item); // Хеширование элемента
       
        int step = 0;
        while (hashArray[i] != 0 && hashArray[i]!= -1) {
            step++;
            i += stepCount(step); // прибавление смещения
            i %= 500; //  к началу
        }
        hashArray[i] = item; 
    }

Заполнение в основном классе

int[] quadraticProbingArray = new int[500];

        for (int i = 0; i < quadraticProbingArray.length; i++) {
            int keyItem = randomNumber();
            QuadraticProbing.insert(keyItem, quadraticProbingArray);
        }

Random функция:

public static int randomNumber(){
    int min = 1;
    int max = 1000;
    max -= min;
    return (int) (Math.random() * ++max) + min;
}

Текст ошибки:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -225 at hashtablehomework.QuadraticProbing.insert(QuadraticProbing.java:33) at hashtablehomework.HashTableHomeWork.main(HashTableHomeWork.java:87) C:\Users\user\OneDrive\Desktop\HashTableHomeWork\nbproject\build-impl.xml:1355: The following error occurred while executing this line: C:\Users\user\OneDrive\Desktop\HashTableHomeWork\nbproject\build-impl.xml:993: Java returned: 1

Answer 1

Возможно переполнение в районе вызова stepCount.

Вы пытаетесь заполнить массив не оставив в нём пустых мест. Такая тактика может привести к ситуации когда stepCount вызывается многократно. Если значение переменной step при этом привысит корень из максимального значения типа int, то округление в функции stepCount вернёт максимальное значение типа int (см. 5.1.3. Narrowing Primitive Conversion). Если это значение сложить с небольшим положительным, то произойдёт сложение по модулю и индекс i станет отрицательным. Операция % от отрицательного числа вернёт отрицательный остаток, который приведёт к исключению.

// при достаточно большом значении step возвращает Integer.MAX_VALUE
public static int stepCount(int step){
    return  (int) Math.pow(step, 2); //шаг возводится в квадрат
}


// если массив достаточно населён этот цикл будет исполнять достаточно долго
// чтобы stepCount вернул Integer.MAX_VALUE
int step = 0;

// в конце концов i станет отрицательным (см. ниже)
while (hashArray[i] != 0 && hashArray[i]!= -1) {
    step++;

    // сложение по модулю сделает i отрицательным
    i += stepCount(step);

    // оператор % вычисляет остаток,
    // который для отрицательного i также будет отрицательным
    i %= 500;
}

Когда вы исправите эту ошибку, код станет зацикливаться, не в силах отыскать единственную свободную ячейку в массиве.

БЛОГ НА HUSL

Java квадратичное пробирование ArrayIndexOutOfBoundsException

Ответы (1 шт):