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

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

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

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

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

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

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

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

Ответы

Ответ 1

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

Ответ 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);