Как использовать результат хэш-функции для получения индекса массива?

Я изучаю фильтры Блума и просматриваю различные хеш-функции в JavaScript.

Например, я нашел это в другом ответе на переполнение стека:

Найдено здесь https://stackoverflow.com/a/7616484/5217568)

String.prototype.hashCode = function() {
  var hash = 0, i, chr, len;
  if (this.length == 0) return hash;
  for (i = 0, len = this.length; i < len; i++) {
    chr   = this.charCodeAt(i);
    hash  = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
};

Если я бегу:

String.prototype.call(null, "hello")

Я получаю числовое значение: 99162322 (две другие хэш-функции меня достали: 1335831723 и 120092131).

Теперь, если я создам гипотетический фильтр Блума с 3 хэш-функциями и 18 индексами (k = 3, m = 18), как эти большие значения индексируются в массиве с индексами от 0 до 17?


javascript hash data-structures bloom-filter hashtable
person jmancherje    schedule 28.11.2015    source источник
comment
Я считаю, что хэш-функция должна использоваться для определения индекса для хранения данных.   -  person jmancherje    schedule 28.11.2015

Ответы (1)


arrow_upward
2
arrow_downward

Используйте оператор остатка/модуля %, чтобы обернуть случайно сгенерированное значение в пределах определенной границы.

Если у вас есть 18 элементов (индексы от 0 до 17), вы можете получить индекс с 99162322 % 18 (16).

Если количество хеш-значений не кратно количеству индексов, результат будет необъективным. Например, если ваше хэш-значение является одним из пяти значений от 0 до 4, но вы сопоставили его с тремя индексами от 0 до 2, оно будет смещено в сторону 0 (0 % 3, 3 % 3) и 1 (1 % 3 или 4 % 3). более 2 (только 2 % 3). В зависимости от ваших потребностей смещение может быть приемлемым, если количество хеш-значений достаточно больше, чем количество индексов. Если вы хотите избежать этого, вам понадобится схема для создания нового ввода хэша, если результат хеширования находится в диапазоне, вызывающем смещение. Что-то вроде этого:

function hashIndex(string, length, hashValueCount) {
  var minBiasedIndex = hashValueCount - (hashValueCount % length);
  for (var i = 0; ; i++) {
    var hashInput = string + ":" + String(i);
    var hashResult = hash(hashInput);
    if (hashResult < minBiasedIndex) {
      return hashResult % length;
    }
  }
}
person Jeremy    schedule 28.11.2015
comment
Это очень интересно, спасибо. Можете ли вы помочь уточнить параметры в вашей функции. В моем примере в вопросе это будет hashIndex (привет, 18, 17)? Где 18 — длина массива, а 17 — самый высокий индекс в массиве? - person jmancherje; 28.11.2015
comment
Я думаю, что количество возможных хэш-значений (hashValueCount) для вас будет примерно равно 2 в степени 31. Я думаю, что ваша хеш-функция может возвращать любое 31-битное целое число без знака, хотя я могу неправильно понять. Я думаю, что это может быть слишком большим для моего расчета minBiasedIndex из-за ограничений % - упс. (Кроме того, у меня изначально были некоторые ошибки в моей функции. Я думаю, что теперь это исправлено.) - person Jeremy; 28.11.2015
comment
(и да, длина будет равна 18, а строка будет приветствоваться.) Учитывая, что ваше количество возможных хеш-значений намного больше, чем ваше количество индексов, я думаю, что смещение очень мало - меньше чем 0,000001%. Я мог бы подумать о том, чтобы просто использовать оператор по модулю напрямую и принять это смещение, в зависимости от приложения. - person Jeremy; 28.11.2015