Способы хеширования числового вектора?

Question

Существуют ли какие-либо известные алгоритмы хеширования, которые вводят вектор целых и выдают одно целое, которое работает аналогично внутреннему произведению?

Другими словами, я думаю об алгоритме хеширования, который может выглядеть следующим образом в C ++:

// For simplicity, I'm not worrying about overflow, and assuming |v| < 7.
int HashVector(const vector<int>& v) {
  const int N = kSomethingBig;
  const int w[] = {234, 739, 934, 23, 828, 194};  // Carefully chosen constants.
  int result = 0;
  for (int i = 0; i < v.size(); ++i) result = (result + w[i] * v[i]) % N;
  return result;
}

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

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

Разъяснение

Хеш предназначен для использования в хеш-таблице для быстрого поиска по ключу / значению. Здесь нет проблем с безопасностью.

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

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

Answer 1

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

Простой эксперимент состоит в том, чтобы хэшировать словарь английского языка и сравнить, сколько у вас коллизий по алгоритму A против алгоритма B.

Вы можете построить аналогичный эксперимент: случайным образом сгенерировать $ BIG_NUMBER возможных векторов длиной 7 или меньше. Хешируйте их по алгоритму A, хешируйте по алгоритму B, затем сравните количество и степень серьезности столкновений.

После того, как вы сможете это сделать, вы можете использовать имитацию отжига или аналогичные методы, чтобы найти «магические числа», которые хорошо вам подходят. В моей работе для заданных словарей, представляющих интерес, и жестко ограниченного размера хэша мы смогли заставить общий алгоритм работать хорошо для нескольких человеческих языков, изменяя «магические числа».

Answer 2

В зависимости от размера констант, я бы сказал, что степень хаоса во входном векторе будет влиять на результат. Тем не менее, быстрый качественный анализ вашего поста предполагает, что у вас хорошее начало:

• Ваши входные данные умножаются, поэтому увеличивается степень разделения между аналогичными входными значениями за итерацию (например, 65 + 66 намного меньше, чем 65 * 66), что хорошо.
• Это детерминированный, если ваш вектор не должен рассматриваться как набор, а не как последовательность. Для ясности, должно ли v = {23, 30, 37} отличаться от v = {30, 23, 37}?
• Равномерность распределения будет варьироваться в зависимости от диапазона и хаоса входных значений в v. Однако это справедливо и для обобщенного алгоритма хеширования целых чисел.

Из любопытства, почему бы просто не использовать существующий алгоритм хеширования для целых чисел и выполнить некоторую интересную математику с результатами?

Answer 3

Python используется для хэширования кортежей таким образом ( source ):

class tuple:
    def __hash__(self):
        value = 0x345678
        for item in self:
            value = c_mul(1000003, value) ^ hash(item)
        value = value ^ len(self)
        if value == -1:
            value = -2
        return value

В вашем случае item всегда будет целым числом, которое использует этот алгоритм:

class int:
    def __hash__(self):
        value = self
        if value == -1:
            value == -2
        return value

Это не имеет ничего общего с внутренним продуктом, хотя ... так что, возможно, это не сильно поможет.

Answer 4

Хотя я, возможно, совершенно не понимаю вас, возможно, будет хорошей идеей рассматривать вектор как поток байтов и делать с ним некоторый хэш, т. Е. SHA1 или MD5 .

Просто чтобы прояснить, известно, что эти хеши имеют хорошие свойства хеширования, и я считаю, что нет причин заново изобретать велосипед и внедрять новый хеш. Другая возможность - использовать известный алгоритм CRC.