Что такое хорошая хеш-функция для набора (т.е. Многострочного) целых чисел?

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

В идеале использование памяти будет постоянным, а значение хеша может быть обновлено в O (1) раз после вставки/удаления. (Это запрещает делать что-то вроде сортировки чисел и с помощью хеш-функции, как Н (х) = h_1 (x_1, h_2 (x_2, H_3 (x_3, X_4))).)

XORing хэши вместе не работают, потому что h ({1,1,2}) = h ({2})

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

Ответ 1

Я задал этот же вопрос на cstheory.stackexchange.com и получил хороший ответ:

https://cstheory.stackexchange.com/questions/3390/is-there-a-hash-function-for-a-collection-i-e-multi-set-of-integers-that-has

Ответ 2

Reverse-биты.

Например, 00001011 станет 11010000. Затем просто SUM все обратные элементы набора.

Если нам нужно O (1) при вставке/удалении, будет использоваться обычный SUM (и то, как Sets реализованы в Java), хотя и не хорошо распределены по множеству малых целых чисел.

Если наш набор не будет равномерно распределен (как это обычно бывает), нам нужно отобразить N- > f (N), так что f (N) будет равномерно распределен для ожидаемого образца данных. Обычно образец данных содержит гораздо больше чисел, близких к нулю, чем числа, близкие к максимальным. В этом случае хэш хэша будет равномерно распределяться.

Пример в Scala:

def hash(v: Int): Int = {
        var h = v & 1
        for (i <- 1 to 31) {
                h <<= 1;
                h |= ((v >>> i) & 1)
        }
        h
}
def hash(a: Set[Int]): Int = {
        var h = 0
        for (e: Int <- a) {
                h += hash(e);
        }
        h
}

Но хэш нашего мультимножества не будет равномерным, хотя намного лучше простого SUM.

Ответ 3

Я согласен с Dzmitry в использовании арифметического SUM хэшей, но я бы рекомендовал использовать хеш-функцию с хорошим распределением вывода для целых чисел вместо того, чтобы просто изменять биты целого числа. Реверсивные биты не улучшают распределение выходных данных. Это может даже ухудшить распределение выходных данных, так как вероятность того, что бит высокого порядка будет потеряна из-за переполнения суммы, намного выше, чем вероятность того, что бит нижнего порядка будет потерян в этом случае. Вот пример быстрой хэш-функции с хорошим распределением: http://burtleburtle.net/bob/c/lookup3.c. Читайте также статью, описывающую, как должны быть построены функции хэша - http://burtleburtle.net/bob/hash/evahash.html.

Использование SUM хэш-значений для каждого элемента в наборе удовлетворяет требованиям в вопросах:

Использование памяти постоянное. Нам нужно сохранить обычное целое число, содержащее хэш-значение для каждого набора. Это целое число будет использоваться для O (1) обновления хэша при добавлении/удалении элементов из набора.
Добавление нового элемента требует только добавления хэш-значения элемента к существующему хеш-значению, то есть операция O (1).
Удаление существующего элемента требует только вычитания хеш-значения элемента из существующего хеш-значения, то есть операция O (1).
Хэш будет отличаться для множеств, которые отличаются только парами идентичных элементов.

SUM и SUB являются безопасными операциями перед целым переполнением, поскольку они обратимы в модульной арифметике где модуль равен 2 ^ 32 или 2 ^ 64 для целых чисел в java.

Ответ 4

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

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

Для получения дополнительной информации о методе Кнута, найдите "Мультипликативный метод Кнута"

-tjw

Ответ 5

Мин-хеширование должно работать здесь. Примените перестановку, сохраните небольшой мультимножество из n минимальных элементов, выберите самый большой.

Разработка: это простой способ работы в O (1) времени и пространстве. Вам нужно что-то вроде очереди приоритетов, не делая ссылку на начальные значения слишком очевидными. Таким образом, вы заказываете свою очередь приоритетов в соответствии с некоторым сложным ключом, что эквивалентно запуску очереди приоритетов при перестановке нормального порядка сортировки. Убедитесь, что очередь отслеживает множественность, так что выбранные элементы также образуют мультимножество.

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

xor(int_hash(x_n, multiplicity_n) foreach n)

Ответ 6

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

// initialize this->hash with 1
unsigned int hash = 1;
void add(int x) {
  this->hash *= (1779033703 + 2*x);
}

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

Если вы хотите объединить два набора, просто умножьте хэш-значение.

Единственное, что я не уверен, что это возможно, - это удалить значение в O (1).