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

Question

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

1. Здесь - хороший обзор наиболее известных хеш-функций.

2. 32bit должно работать очень хорошо.

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

Answer 3

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

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

Answer 4

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

Answer 5

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

Answer 6

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