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

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

Если вам нужны только близкие значения, которые должны быть сопоставлены со случайными дальними значениями, это сработает; если вы хотите избежать коллизий (т.е. если A и B сталкиваются с использованием хэша 1, они, вероятно, также не столкнутся с использованием хэша 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, возможно, будет достаточно простой функции has, но это не самое простое решение.

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

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