Посоветуйте хэш-функцию для свертки не длинных массивов байт

[xokc]

Когда размеры данных превышают ключ в 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)
Вот интересный вариант на 32 бита
http://code.google.com/p/xxhash/
А вот на 64 бита
http://code.google.com/p/cityhash/
Судя по замерам производительности на xxhash можно успеть трижды (по сравнению с CityHash64) посчитать xxh32 на различных вариантах входной последовательности (например, на полном входе и на каких-либо его участках) и скомбинировать из него 96 битный ключ.

[OKTA]

CRC32 уже выдает одинаковые значения на codding - gnu и exhibiters - schlager. И соответственно на всех производных от этих слов, если к ним справа что-то дописывать  

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

64 разряда, если выполнится требование уникальности и работать будет быстро.

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

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

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

[Igors]

Требование уникальности есть для указанного выше диапазона входных данных. Поэтому CRC32 не подходит.

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

Код

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; }
 

[xokc]

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

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

Думаю что это недостижимо - во всяком случае вероятность совпадения ключей ненулевая.

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

[Old]

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

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

[Гурман]

Требование уникальности есть для указанного выше диапазона входных данных. Поэтому CRC32 не подходит.

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

Код

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; }
 

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

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

[OKTA]

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

[OKTA]

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

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

[Igors]

В этом диапазоне хэширование должно давать строго уникальные ключи.

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

[OKTA]

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