Russian Qt Forum

Исходные данные - массивы байт с переменной длиной от 8 Байт и до 256 КБайт. Наиболее частые имеют длину от 16 байт и до 1 КБайт. Более 1 КБайт массивы очень маловероятны. Нужна хэш-функция, которая давала бы свертку длиной 32 разряда, и с максимальной вероятностью несовпадения сверток. Может быть, достаточно будет CRC32? Или даже CRC16? Или может существуют другие хэш-функции для подобных задач?

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

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

Используй SHA и не мучайся выбором) Правда там длина хэша 160 бит в случае с SHA1, но это мелочи.

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

Если требования именно 32 разрядный хэш, то какие ещё разумные варианты могут быть кроме CRC32?

CRC32 это ведь не хэш-функция по факту. Она разве гарантирует уникальность данных или другими словами разве она устойчива к коллизиям?

Уникальность хеш-ключа не требуется, просто "чем уникальнее - тем лучше" (меньше коллизий). С этой точки зрения CRC32 хороший кандидат

Без уникальности хэша нет смысла в самом хэше  ;D
CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  ;D
Если жестких требований к уникальности не ставится, то конечно можно использовать CRC, а в ином случае лучше использовать именно хэш-функции..

P.S. MD5 работает быстрее, чем SHA1. А если надо что-то еще быстрее, то алгоритмов миллион, просто не все стандартизованы.

Пример: пусть данные int и в данный момент хеш имеет напр 5 bin'ов (корзин). Тогда хеш-ключ вычисляется как остаток от деления на 5. Да, хранящиеся в хеше значения напр 5, 10, 15 окажутся в одной корзине и будут все перебираться (обычно по списку). Это и есть "коллизии". Требование "уникальности" было бы бессмысленным, т.к. время обращения к такому хешу неприемлемо долго.

Это почему?

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

Скажем так - требование: работающий не медленнее, чем CRC32, и желательно не сильно более длинный. Может быть, 64 разряда, если выполнится требование уникальности и работать будет быстро.

http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%94%D0%B6%D0%B5%D0%BD%D0%BA%D0%B8%D0%BD%D1%81%D0%B0
http://ru.wikipedia.org/wiki/PJW-32

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

Не понял - CRC32("codding - gnu") = 0xAD7CEA44, CRC32("exhibiters - schlager") = 0x389AE08C, CRC32("codding - gnu1") = 0xF2C016D4, CRC32("exhibiters - schlager1") = 0x67EABA5C (http://www.codenet.ru/services/crc32/ (http://www.codenet.ru/services/crc32/))

И снова не понял, о какой уникальности хэша может идти речь при ограниченной длине ключа. В любом случае для 64 битного ключа количество вариантов его значений = 2^64. То есть для 2^64+1 различных вариантов входных последовательностей будут гарантированно совпадать значения хэшей даже для идеальной в смысле минимизации коллизий функции.
Для гарантированно уникальной хэш функции на неограниченно длинной последовательности нужен неограниченно длинный ключ.

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

Такие алгоритмы есть? Интуитивно я догадываюсь, что должны быть, но не встречал никогда.

Когда размеры данных превышают ключ в 256*1024/4=65536 раз (256 кБ к 32 битам), то для любой разумной хэш функции число коллизий на таких размерах будет таким же как и на 1 МБ. Существенным может быть разница для действительно коротких (до 256 байт) входных последовательностей (см., например, тут http://ru.wikipedia.org/wiki/Adler-32#.D0.9F.D1.80.D0.B5.D0.B8.D0.BC.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D0.B8_.D0.BD.D0.B5.D0.B4.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.B8 (http://ru.wikipedia.org/wiki/Adler-32#.D0.9F.D1.80.D0.B5.D0.B8.D0.BC.D1.83.D1.89.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D0.B8_.D0.BD.D0.B5.D0.B4.D0.BE.D1.81.D1.82.D0.B0.D1.82.D0.BA.D0.B8))
Вот интересный вариант на 32 бита
http://code.google.com/p/xxhash/
А вот на 64 бита
http://code.google.com/p/cityhash/
Судя по замерам производительности на xxhash можно успеть трижды (по сравнению с CityHash64) посчитать xxh32 на различных вариантах входной последовательности (например, на полном входе и на каких-либо его участках) и скомбинировать из него 96 битный ключ.

Я имел ввиду пары слов) CRC32("codding") = 0x69c8c72d И CRC32("gnu") = 0x69c8c72d и т.д.

А откройте мне глаза, о каком хэш-ключе вы тут говорите?

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

C++ (Qt)
struct CTest {
	bool operator == ( const CTest & sec ) const
	{
		return mCRC == sec.mCRC && mData == sec.mData;
	}
 
	int mCRC;
	QVector <char> mData;
};
 
inline uint qHash( const CTest & key ) { return key.mCRC; }
 

Безусловно, в академическом смысле термин "ключ" к хеш-функции не очень применим. Здесь под ключом я понимал результат, возвращаемый хеш-функцией.

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

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

Данные - некие измеренные значения, длина которых обычно от 8 до 1024 байт. В этом диапазоне хэширование должно давать строго уникальные ключи. В диапазоне длин от 1024 до 256КБ возможны совпадения ключей, но чем длиннее данные, тем больше допускается вероятность совпадения, поскольку чем длиннее данные, тем меньше вероятность появления совпадающих по ключам. То есть, фактически, появиться разные данные с длиной около 256 КБ и совпадающими ключами никогда в реальности не могут. С длиной немного более 1 КБ - могут, но вероятность этого крайне низкая и снижается с ростом длины таких данных. Можно считать так - если одни и те же данные длиной более 1 КБ могут сгенерировать совпадающие ключи, то это значит, что появиться может только один массив таких данных. То есть для длинных данных требование уникальности ключа обеспечивается тем, что генерирующие коллизию данные никогда не появятся (по задаче я бы написал никогда не появятся одновременно, но это может только запутать). Поэтому нужен алгоритм, который дает такую свертку, при которой вероятность коллизии на коротких данных нулевая, а появляется только на длинных данных, и может расти с ростом их длины.

Сами данные как ключ использовать нельзя по условию задачи - надо иметь ключ не более 64 разрядов, но желательно 32. Большего рассказать не могу.

Если будете использовать хэш-функцию, которая выдает 32-битные значения и количество уникальных данных > 2^32, то коллизии будут по определению, независимо от длины данных. Так что надо придумать что-то еще  :-\

Возможно удобным решением будет использование MAC(Message Authentication Code) или по-русски имитовставка. Это хэш-функция, но зависимая от ключа. Т.е. можно попробовать использовать данные дважды - как сами данные и как ключ. Но насчет коллизий в этом случае мало что известно, т.к. для таких целей MAC не используется. Но почитать можно - гуглить по "MAC на основе однонаправленной хэш-функции".

Хотя нет, тоже самое получится  :-\

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

если ограничение на ключ 32, максимум 64 бита, то вообще не вариант