Основные понятия хэширования векторов

Question

Я изучаю методы хэширования для поиска и поиска информации. Но прежде, чем я углубится, я смущен определенными понятиями о хэш-функциях вообще.

Скажем, у меня есть вход x, который является вектором значений с плавающей запятой, xi = [x_1,x_2,...,x_L]. Размер вектора L. Есть N такие векторы, также называемые примерами, X = [x1,x2,..,x_N]. Учитывая вектор запроса p, мне нужно найти ближайший/ближайший пример, который соответствует запросу. Просматривая несколько материалов для чтения, самая простая (но неэффективная) хеширующая функция - h(x) = x mod M, когда размер таблицы равен M=10 (скажем).

x mod M является остатком x при делении на M, то x mod M всегда будет находиться в диапазоне от 0 и M -1, всегда можно сопоставить целое с одним из M слотов. Мои вопросы:

Вопрос 1: Модуль выполняется по размеру стола. Однако, если каждый образец имеет длину L и есть такие N такие образцы, то какое число по модулю представляет? Будет ли h(x) = x mod vector length

или h(x) = xmod number of examples?

В приложениях для криптографии обычно выполняется мода 256, поскольку каждый блок имеет размер 8 бит. Это означает, что модуль берется по длине вектора? Пожалуйста, исправьте меня, если ошибаетесь.

Вопрос 2: Я должен преобразовать числа с плавающей запятой в целые числа, потому что многие примеры показывают, что вход представляет собой либо значение ASCII, либо целое число.

Вопрос 3: Если для аргументации хэш-функция имеет значение h(x) = 2*x mod 1, то это приведет к получению числа с плавающей запятой в диапазоне [0,1]. Я могу преобразовать его в целое число, используя H(x) = round(h(x)). Для примера сообщения x, если он разделен на k, блокирует каждую длину такой же длины L, мне нужны k такие хэш-функции? Любые предложения для хэш-функции для этого примера. Спасибо.

Answer 1

Итак, когда вы создаете хеш-таблицу, это всего лишь массив, и что делает хэш-функция, требуется ли объект и на основе свойств объектов возвращается integer mod (length of array). Поэтому не беспокойтесь о своих числах с плавающей запятой! Если вы хотите предложить, как это реализовать, вот что я буду делать.

Прежде всего, выясните, как долго вы хотите, чтобы ваша хэш-таблица была (как правило, в два раза больше объектов, которые вы ставите [или немного дольше], это хорошая ставка). Это будет просто массив типа vector (или объект, который вы храните).

Затем вы хотите сделать свою хэш-функцию. При разработке hashfunctions рекомендуется использовать большие простые числа и умножать на них разные части вашего объекта и добавлять все это. Например ...

int total = 0 
for each floatingptNum currentVector: 
    total = total + 129 * currentFloatingptNum 

return total % lengthOfArray 

Это просто очень простой хэш-функции в suedo коде (не уверен, какой язык вы используете), но до тех пор, как он дает вам целое число в диапазоне вы находитесь массива , ты настроен!

Причина, по которой мы используем большие простые числа, заключается в том, что мы получаем как можно меньше столкновений (когда два отдельных значения сопоставляются с одним и тем же местом), но имейте в виду, что они почти всегда должны произойти. Одним из решений является bucket or chain hashing. Это в основном означает, что вместо массива векторов у вас будет массив связанных списков векторов, с единственной целью - хранить два разных вектора в одном и том же месте в хеш-таблице!

Много информации, но я надеюсь, что это поможет! Счастливое хеширование!