Нужна hash функция для integer array?

Question

[kuzemchik]

Нужна быстрая hash функция для получения хеша от массива чисел. Нужна одинаковая для PHP и JS (проверять целостность на клиенте и сервере). Если нет готовых, то ссылки на алгоритмы для получения хеша от массива тоже пойдут.


Спасибо.

Answer 1

[CrazySquirrel]

Серилизовать массив(например json) и взять хеш от строки(например md5).

При выборе hash функции не забудьте, что они могут создавать коллизии.

Comments

[kuzemchik]

Строку нельзя, так как элементов в массиве около 13 тысяч, числа по 4-ре байта. MD5 поэтому и не беру, потому как шансы коллизии велики.

[CrazySquirrel]

От такого значения будет проблематично брать hash. Есть фариант с crc он должен быть более стабилен, или выполнение мат. операций над элементами массива, и их сравнение, но тоже не гарантирует нечего :-(

[Андрей]

MD5 и любая другая хеш-функция описываются изначально не как string f(string),
а последовательностью вызовов:
state f_start()
state f_add_info(state,info1)
…
state f_add_info(state,infoN)
string f_finish(state)

Это их полное нормальное описание.
А эрзац string f(string) — это уже свертка описанного выше.

Используйте полный формат хеш-функции. Это решит все Ваши проблемы.

[ixSci]

От такого значения будет проблематично брать hash.

Отнюдь, это всего ~50К.

[WebSpider]

Прошу прощения, а что значит «4-ре»?

[kuzemchik]

4-ре = 4

[Сергей Береснев]

Всё зависит от рода чисел, это может быть и все 130К, а может и 13К.

Кстати, при достаточном скилле, можно модифицировать готовые md5 реализации в js, чтобы они работали с массивами. А вот в PHP реализация md5 встроенная, поэтому придётся либо искать реализацию на PHP, либо генерировать строчку.

Answer 2

[Андрей]

Шансы случайной (!) коллизии MD5 ничтожны.

Comments

[ANUFRiY]

Поправка: для данных близких по объёму.
Ну и конечно смотря для кого количества элементов.

[kuzemchik]

от одного до 13к элементов в различных сочетаниях.

Answer 3

[uglymeta]

На ум приходит эвристический алгоритм — сложить все числа в массиве и либо использовать саму сумму для проверки либо md5 от неё.

Answer 4

[egorinsk]

XOR или XOR + умножение на 7.

Comments

[egorinsk]

Для каждого элемента.