Минимальная хэш-функция для C?

Я не могу использовать boost: hash, потому что я должен придерживаться C и не могу использовать C++.Минимальная хэш-функция для C?

Но мне нужно хэшировать большое количество (10K до 100k) строк токенов (от 5 до 40 байтов), чтобы поиск в них был самым быстрым.

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

Поэтому мой вопрос:

Что может быть простейший алгоритм хеширования, который будет обеспечивать предотвращение столкновений в большинстве практических случаев.
Сколько бит используется для хэш-значения? Я разрабатываю 32-битные системы. Использует ли хэш-алгоритм в Perl/Python 32-битные хэши? Или мне нужно прыгать до 64?
Что касается реализации хеш-таблиц на обычных языках сценариев: выполняется ли проверка выполнения для коллизий или я могу вообще избежать этой части?

источник

2009-04-13 CDR

+23

Следующая страница имеет несколько реализаций общего назначения хэш-функций, реализованных в C (и во многих других языках): http://partow.net/ programming/hashfunctions/index.html – 2010-10-31 23:06:24

Вы считали, что используете GLib? https://developer.gnome.org/glib/2.46/glib-Hash-Tables.html –

Вы можете найти хорошее (и быстрый) хэш-функции, и интересно читать, в http://www.azillionmonkeys.com/qed/hash.html

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

источник

2009-04-13 14:04:18 gnud

Я бы предложил взглянуть на тот, который пропустил анализ Сси: MurmurHash2. http://en.wikipedia.org/wiki/MurmurHash –

Общая хеш-функция для hash table lookup. Он указывает НЕ используйте для криптографических целей, но так как вы указали, что у вас нет намерения, тогда вам все будет в порядке.

Это Включается обследование функций хэширования попробовать

источник

2009-04-13 14:00:34 TStamper

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

источник

2009-04-13 14:02:43 arul

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

Ну, такое детерминированное поведение - это то, что я имел в виду под «смешным». – arul

Попробуйте Adler32 для длинной строки или Murmur2 для коротких строк.

источник

2009-04-13 14:12:22

Adler32 не очень хороший хеш. На самом деле, это еще хуже, чем CRC-32, как хэш. Murmur2, с другой стороны, очень быстрый хэш с отличным распределением и наихудшим поведением, поэтому нет причин ограничивать его использование короткими строками. Я не понимаю основ вашего совета. –

Если вы находитесь в системе posix и придерживаетесь простой C, я бы просто использовал то, что система уже может предложить. man 3 hcreate предлагает вам всю информацию или вы можете найти онлайн-версию здесь http://linux.die.net/man/3/hcreate

источник

2009-04-13 16:05:02

xxhash довольно быстрая и простая опция. Простой код будет использовать XXH32 функцию:

unsigned int XXH32 (const void* input, int len, unsigned int seed);

Это 32 бит хэша.Поскольку len является int для больших данных более чем 2^31-1 байт использовать эти:

void*   XXH32_init (unsigned int seed); 
XXH_errorcode XXH32_update (void* state, const void* input, int len); 
unsigned int XXH32_digest (void* state);

источник

2013-10-22 08:48:16

ответ

Смежные вопросы