Почему эта реализация Quadratic Probing терпит неудачу, когда не переопределяет значения при столкновении?

Моя текущая реализация Quadratic Probing заменяет элемент, сохраняемый в текущем индексе, новым элементом при возникновении коллизии. Я вставляю три объекта Person, которые хранятся с использованием их фамилии в качестве ключа. Чтобы проверить разрешение столкновения реализации, у них всех есть та же самая фамилия, которая является "Ветряной мельницей".

Мне нужна реализация, чтобы сохранить все объекты person, но просто переместить их в другой индекс, а не переопределять их.

Размер списка был установлен равным 7, он хранится в переменной "M", используемой по модулю в функции вставки.

Вставить функцию

@Override
public void put(String key, Person value) {
   int tmp = hash(key);
   int i, h = 0;

    for (i = tmp; keys[i] != null; i = (i + h * h++) % M) {
        collisionCount++;

        if (keys[i].equals(key))  { 
            values[i] = value;
            return; 
        } 
    }

    keys[i] = key;
    values[i] = value;
    N++;
}

Хэш-функция

private int hash(String key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

получить функцию

@Override
public List<Person> get(String key) {
    List<Person> results = new ArrayList<>();

    int tmp = hash(key);
    int i = hash(key), h = 0;

    while (keys[i] != null)
    {
        if (keys[i].equals(key))
            results.add(values[i]);

        i = (i + h * h++) % M;
    }   

    return results;
}

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

Источник

2 ответа

Решение

Я думаю, что есть два вопроса с вашим кодом:

  1. Вы не проверяете, заполнена ли (мульти) карта. На практике вы хотите сделать 2 проверки:

    • проверить, если N==M (или, возможно, какой-то меньший порог, как 90% M)
    • делать collisionCount локальная переменная и когда она достигает N (к сожалению, эта проверка также необходима, чтобы избежать некоторых патологических случаев)

в обоих случаях вы должны расширить область хранения и скопировать в нее старые данные (заново вставить). Это само по себе должно исправить вашу ошибку для небольших значений M но для действительно больших размеров карты вам все еще нужно следующее.

  1. Вы не учли, как мод (%Операция работает в Java. Особенно для отрицательного значения a значение a % b тоже отрицательно. Поэтому, когда вы вставляете много значений и проверяете следующий индекс, i + h^2 может переполниться Integer.MAX_VALUE и стать отрицательным. Чтобы это исправить, вы можете использовать такой метод:
static int safeMod(int a, int b) {
     int m = a % b;
     return (m >= 0) ? m : (m+b);
}
Источник

Вы получаете переполнение, потому что вы делаете % M после некоторых операций с int, которые вызывают переполнение. Вам нужно заменить i = (i + h * h++) % M с некоторыми дополнительными операциями, основанными на свойствах операций по модулю ( https://en.wikipedia.org/wiki/Modulo_operation):

  • (a + b) mod n = [(a mod n) + (b mod n)] mod n.
  • ab mod n = [(a mod n) (b mod n)] mod n.
Источник
Другие вопросы по тегам