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

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

0 голосов
/ 17 января 2019

Моя текущая реализация Quadratic Probing заменяет элемент, сохраняемый в текущем индексе, новым элементом при столкновении.Я вставляю три объекта 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 ]

0 голосов
/ 18 января 2019

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

  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);
}
0 голосов
/ 17 января 2019

Вы получаете переполнение, потому что вы делаете % M после некоторых операций с целыми числами, которые вызывают переполнение. Вам необходимо заменить 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.
...