Алгоритм Flajolet-Martin: Вопрос о использовании определенных хэш-функций

Question

Это вопрос, данный в PDF о потоковых алгоритмах (это не является назначением, но я пытаюсь понять)

<Сильные> Упражнение 4.4.1 : Предположим, наш поток состоит из целых чисел 3, 1, 4, 1, 5, 9, 2, 6, 5. Наши хэш-функции будут иметь форму H (x)= AX + B MOD 32 для некоторых а и б. Вы должны относиться к результату как 5-битный Двоичное целое число. Определите длину хвоста для каждого элемента потока и Полученная оценка количества различных элементов, если хеш Функция:

(a) h (x)= 2x + 1 мод 32.

(b) h (x)= 3x + 7 мод 32.

(c) h (x)= 4x mod 32.

! Упражнение 4.4.2 : Видите ли вы какие-либо проблемы с выбором хеша Функции в упражнении 4.4.1? Какой совет вы могли бы дать кому-то, кто собирался использовать хеш-функцию формы h (x)= ax + b мод 2k?

Я уже разрешил первое упражнение, нахожу максимальную длину хвоста 0 для (a) и 4 для (b) и (c), поэтому полученная оценка различных элементов соответственно составляет 1,16,16. (Не просят выполнять средние значения / медики из хеш-функций, чтобы найти лучшее значение)

Однако я не могу понять ответ на вторую упражнение? Это просто выбрать «A» и «B» определенным образом? Или эти функции не приятно генерировать одинаково случайно числа с трейлинговыми 0s и без трейлинга 0s?

Спасибо заранее

Вы можете наблюдать результаты каждого хеш-функций, запустив этот код: https://onlinegdb.com/rjxc4f4vl

Answer 1

Однако я не могу понять ответ на вторую упражнение?Это просто выбрать «A» и «B» определенным образом?Или эти функции не приятно генерировать одинаково случайно числа с трейлинговыми 0s и без трейлинга 0s?

У вас есть правильная идея.Я верю, какой вопрос пытается предложить вопрос, заключается в том, что эта хеш-функция имеет проблему с определенными значениями $ a $ и $B $ .Рассмотрим, в частности, $ a= 16 $ .Что произойдет с функцией хешей в этом случае?Сколько возможностей возможных значений?

Так, чтобы выбрать хорошее значение $ a $ , мы, вероятно, должны убедиться, что $ a= 16 $ не допускается. $ a= 8 $ тоже не хорошо.Что вы предлагаете, это хороший выбор для $ a $ ?