Что такое хорошая хеш-функция для набора (то есть, множества) целых чисел?

Question

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

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

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

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

Answer 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

Answer 2

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

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

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

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

Answer 3

Обратные биты.

Например, 00001011 становится 11010000. Затем просто СУММИТЕ все элементы обращенного набора.

---

Если нам нужно O (1) при вставке / удалении,обычный SUM будет работать (и именно так наборы реализованы в 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.

Answer 4

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

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

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

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

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

Answer 5

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

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

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

xor(int_hash(x_n, multiplicity_n) foreach n)

Answer 6

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

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

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

-tjw