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

Я не могу использовать boost: hash, потому что я должен придерживаться C и не могу использовать C ++.

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

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

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

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

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

  3. Что касается реализации хэш-таблиц в распространенных языках сценариев: проверяет ли реализация на наличие коллизий, или я могу вообще избежать этой части?


c hash hashtable
person CDR    schedule 13.04.2009    source источник
comment
Вы рассматривали возможность использования GLib? developer.gnome.org/glib/2.46/glib-Hash-Tables. html   -  person Bastien Léonard    schedule 13.04.2009
comment
На следующей странице представлено несколько реализаций хэш-функций общего назначения, реализованных на C (и многих других языках): partow .net / programming / hashfunctions / index.html   -  person    schedule 01.11.2010

Ответы (6)


arrow_upward
24
arrow_downward

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

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

person gnud    schedule 13.04.2009
comment
Я бы посоветовал взглянуть на один, который упустил из анализа Се: MurmurHash2. en.wikipedia.org/wiki/MurmurHash - person Steven Sudit; 10.07.2009

arrow_upward
11
arrow_downward

  1. Вот хороший обзор наиболее известного известного хэша. функции.

  2. 32 бита должны работать нормально.

  3. Всегда нужно проверять коллизии, если только вы не хотите писать забавную хеш-таблицу :)

person arul    schedule 13.04.2009
comment
Вам не нужно проверять наличие коллизий, если вас не особо заботит, какой ответ вы получите. Преимущество состоит в том, что вам не нужно хранить исходный ключ в хеш-таблице, поэтому вы можете сэкономить много места. - person Zan Lynx; 13.04.2009
comment
Что ж, такое недетерминированное поведение - вот что я имел в виду под «смешным». - person arul; 13.04.2009

arrow_upward
8
arrow_downward

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

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

person TStamper    schedule 13.04.2009

arrow_upward
5
arrow_downward

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

person amo-ej1    schedule 13.04.2009

arrow_upward
2
arrow_downward

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

person Community    schedule 13.04.2009
comment
Adler32 - это вообще не очень хороший хеш. Фактически, это даже хуже, чем CRC-32, как хеш. Murmur2, с другой стороны, является очень быстрым хешем с отличным распределением и худшим поведением, поэтому нет причин ограничивать его использование короткими строками. Я не совсем понимаю, на чем основан ваш совет. - person Steven Sudit; 10.07.2009

arrow_upward
1
arrow_downward

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);
person Majid Azimi    schedule 22.10.2013