Генерация k попарно независимых хеш-функций

Question

Я пытаюсь реализовать алгоритм Sketch Count-Min в Scala, и поэтому мне нужно сгенерировать k попарно независимых хеш-функций.

Это более низкий уровень, чем все, что я когда-либо программировал раньше, и я мало что знаю о хеш-функциях, кроме как из классов Algorithms, поэтому мой вопрос: как мне сгенерировать эти k попарно независимых хеш-функций?

Я должен использовать хэш-функцию, такую ​​как MD5 или MurmurHash? Должен ли я просто сгенерировать k хеш-функций вида f(x) = ax + b (mod p)где p простое число, а a и b случайные целые числа? (т. е. универсальное семейство хэширования, которое каждый изучает в алгоритмах 101)

Я ищу больше простоты, чем сырой скорости (например, я возьму что-то в 5 раз медленнее, если это проще реализовать).

Answer 1

Скала уже есть MurmurHash реализовано (это scala.util.MurmurHash). Это очень быстро и очень хорошо распределяет ценности. Криптографический хэш излишний - вам понадобится в десятки или сотни раз больше времени, чем нужно. Просто выбери k различные семена для начала и, так как это почти криптографическое качество, вы получите k в значительной степени независимые хэш-коды. (В версии 2.10 вам, вероятно, следует перейти на использование scala.util.hashing.MurmurHash3; использование довольно разное, но вы можете сделать то же самое с микшированием.)

Если вам нужно сопоставить только значения, близкие к случайным значениям, это будет работать; если вы хотите избежать коллизий (т. е. если A и B сталкиваются с использованием хэша 1, они, вероятно, также не будут сталкиваться с использованием хэша 2), вам нужно будет сделать хотя бы еще один шаг и хешировать не весь объект, а его подкомпоненты, так у хэшей есть возможность начать иначе.

Answer 2

Вероятно, самый простой подход состоит в том, чтобы взять некоторую криптографическую хеш-функцию и "заполнить" ее различными последовательностями байтов. Для большинства практических целей результаты должны быть независимыми, так как это одно из ключевых свойств, которое должна иметь криптографическая хеш-функция (если вы заменяете какую-либо часть сообщения, хеш должен быть совершенно другим).

Я бы сделал что-то вроде:

// for each 0 <= i < k generate a sequence of random numbers
val randomSeeds: Array[Array[Byte]] = ... ; // initialize by random sequences

def hash(i: Int, value: Array[Byte]): Array[Byte] = {
    val dg = java.security.MessageDigest.getInstance("SHA-1");
    // "seed" the digest by a random value based on the index
    dg.update(randomSeeds(i));
    return dg.digest(value);
    // if you need integer hash values, just take 4 bytes
    // of the result and convert them to an int
}

---

Редактировать: я не знаю точных требований Count-Min Sketch, может быть, простой функции has будет достаточно, но это не самое простое решение.

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

С другой стороны, если у вас есть две хэш-функции вида f1(x) = ax + b (mod p) а также f2(x) = cx + d (mod p), то вы можете вычислить один, используя другой (не зная, x) используя простую линейную формулу f2(x) = c / a * (f1(x) - b) + d (mod p)Это говорит о том, что они не очень независимы. Таким образом, вы можете столкнуться с неожиданными проблемами здесь.