Функция Ha sh для двух целочисленных массивов с минимальными коллизиями - PullRequest
Новая
       109

Функция Ha sh для двух целочисленных массивов с минимальными коллизиями

2 голосов
/ 30 апреля 2020

Я работаю над проблемой, где я хочу хранить объекты, состоящие из двух целочисленных массивов одинаковой длины (например, int a[] ={1,2,3,4} и int b[] ={1,2,2,6}) в структуре данных (например, hashmap). Однако для разных объектов длина двух массивов может различаться. Оба массива состоят из целых чисел из заданного интервала (например, между 0-200).

Для хранения объектов с двумя массивами я хочу назначить один хеш-ключ, который быстро вычисляется, сохраняет обе последовательности и приведет к минимальным коллизиям.

Сначала я попытался использовать Arrays.deepHashCode(int[][]) но быстро нашли столкновения. Во-вторых, я попытался распределить значения в массивах более равномерно, изменив a [i] и b [i] на новые значения, чтобы a_new[i] = Math.pow(31,a[i]) % Math.pow(2,16) (фактически используя BigInteger, чтобы избежать переполнения: BigInteger.valueOf(31).modPow(BigInteger.valueOf(a[i]), BigInteger.valueOf(Math.pow(2,16))); используя BigInteger. Так как интервал значений ограничен, я могу предварительно рассчитать его для каждого возможного значения. В результате я пришел к следующему решению: 

    int result = 31;
    for (int i = 0; i < a.length; i++) {
        result = result * 31 * a_new[i];
        result = result * 31 * b_new[i];
    }

Это решение, кажется, работает, когда есть только меньшие массивы, но один раз [] и b [] могут содержать до 10 значений, что также приводит к коллизиям. Теперь мне интересно, есть ли лучший способ добиться того, что я хочу, с меньшим коллизиями.

Редактировать: я исправил это использование правильный java код для полномочий

Ответы [ 3 ]

1 голос
/ 01 мая 2020

Просто констатирую очевидное ... 

return Objects.hash(a_new, b_new);
1 голос
/ 01 мая 2020

Возможно, вместо умножения каждого a[i] и b[i] на 31, вы могли бы сохранить массив простых чисел и текущее число в массиве на prime[i]?

Примерно так: 

int result = 31;
int[] primes = {3, 5, 7, 11, 13, 17, 19, 23, ... };
    for (int i = 0; i < a.length; i++) {
        result = result * primes[i % primes.length] * a_new[i]
        result = result * primes[i % primes.length] * b_new[i]
    }

Вы также можете попробовать с большими простыми числами уменьшить вероятность столкновений.

0 голосов
/ 04 мая 2020

Спасибо за все ответы и идеи. В конце концов, я пришел к другому решению, которое, похоже, работает для меня и до сих пор не привело к каким-либо коллизиям.

Вместо того, чтобы создавать по одному ha sh для обоих массивов, я решил создать два разных хэши. Один ха sh основан на наборе целых чисел в массивах, а другой - на последовательностях (так же, как в моем вопросе). Затем оба хэша используются в качестве ключей в MultiKeyMap (Apache Commons Collections 4.4 API), где я храню данные, связанные с двумя массивами.

ha на основе последовательности ha sh: 

    int result = 31;
    for (int i = 0; i < a.length; i++) {
        result = result * 31 * a_new[i];
        result = result * 31 * b_new[i];
    }

    return result;

Набор на основе га sh: 


    int resultA = 31;
    int resultB = 179;
    for (int i = 0; i < a.length; i++) {
        resultA += a_new[i];
        resultB += b_new[i];
    }

   return resultA *31 * resultB;
...