Функция сжатия метода MAD

Question

Я наткнулся на вопрос ниже на старом экзамене.Мои ответы кажутся немного короткими и неадекватными.Любые дополнительные идеи, которые я могу рассмотреть или причины, которые я пропустил, были бы великолепны.Спасибо

Рассмотрим функцию сжатия метода MAD, отображающую объект с хеш-кодом i в элемент [(3i + 7) mod9027] mod6000 массива сегментов из 6000 элементов.Объясните, почему это плохой выбор функции сжатия, и как ее можно улучшить.

Я просто говорю, что функцию можно улучшить, изменив значение для p (или 9027) на простое число и выбравдругая константа для (или 3) также может помочь.

Answer 1

Комментарий Рупа по сути правильный ответ. 3 и 9027 оба делятся на 3, поэтому 3i + 7 отображается только на 1/3 диапазона 0-9026. Затем мод отображения 6000 отображает 2/3 значений в нижнюю половину. Таким образом, ведро 1 будет содержать примерно 1/1500 значений [если я правильно сделал математику], а не 1/6000, как вы бы хотели. Ведро 0 будет пустым.

Answer 2

, если i равномерно распределено по достаточно большому диапазону, то (3i + 7)mod9027 будет равномерно распределено по 0-9026, но если принять мод 6000, то две трети хэшей будут в первой половине диапазона ( От 0 до 3026 и от 6000 до 9026 включительно) и одна треть во второй половине (от 3037 до 5999 включительно).