Генерация уникального целого числа (4 байта или 8 байтов) для строки символов

Question

Если у меня есть список L строк, состоящих из символов (от a до z и.), Т.е. всего 27 символов, и каждая строка может иметь максимальный размер 256 байтов. Могу ли я иметь хеш-функцию, которая будет иметь 0 коллизий (практически, а не теоретически)? Идеальные хеш-функции здесь не будут работать, так как L можно модифицировать (т.е. это не только для чтения)

Меня интересуют только практические вещи. Я знаю, что невозможно создать хеш-функцию с 0 коллизиями.

Я могу использовать md5sum, но это сгенерирует 16-байтовое целое число. Я просто хочу найти 4-байтовое или макс. 8-байтовое целое число.

Возможно ли это?

Спасибо за ваше терпение

~ дс ~

Answer 1

Одно решение: просто используйте известную хеш-функцию, такую ​​как MD5, и используйте младшие 4 или 8 байтов.

Answer 2

Другие люди уже предложили правильное решение (используйте хэш-сумму), но если вы действительно заинтересованы в том, чтобы как можно меньше коллизий, вот две мысли, чтобы рассмотреть проблему в более широком масштабе:

1. Если вы храните некоторые (или все) строки, для которых вы хотите сгенерировать идентификаторы, в памяти, вы можете использовать адрес памяти, по которому строка хранится в качестве идентификатора. Если предположить, что изменение строки на месте - это нормально, этот идентификатор будет оставаться стабильным даже при изменении строки.

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

Answer 3

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

Предполагая, что строка имеет нулевое окончание ASCII, вы можете начать с преобразования в небольшое целое число.

char *charset = "abcdefghijklm"
                "nopqrstuvwxyz.";
int c = strchr(charset, *s++) - charset;

Затем обработайте каждое значение как основание-27. Расшифруйте, умножив сумму на 27, прежде чем добавить в 0-26 «единицу» из текущего символа. Вы упоминаете максимальную длину. Я предполагаю, что это означает, что строки хранятся в массивах фиксированной длины. Если это так, то массивы не просто обнуляются, но и дополняются нулями. затем вы можете декодировать массивы назад, чтобы поместить существенные различия в наименее значимые «позиции» числа base-27. Но если размер - просто щедрое завышение, и ожидается, что большинство строк будет намного короче, то, вероятно, лучше сканировать вперед и завершать на nul.

int sum;
sum *= 27;
sum += c;

Answer 4

Некоторая контрольная сумма или хэш - это правильный ответ.

Вы правы, что не можете избежать столкновений.Но если вы сократите контрольную сумму или хэш до 4 байтов, частота столкновений существенно возрастет.

Если все в порядке, вы можете проверить что-то вроде http://en.wikipedia.org/wiki/Hash_function, чтобы найти тот, который вам удобнеес.