Я пытаюсь разработать следующий алгоритм
Ввод: неограниченный массив неограниченных строк, отсортированных по алфавиту, целое число N
Вывод: шестнадцатеричный целочисленный идентификатор с N цифрами, ни одна из которых не равна нулю
Я не уверен, как создавать хорошие хэш-функции. Пока что моя лучшая попытка была на
- взять каждый символ в строке, умножить его на простое число (из списка простых чисел, которые в конечном итоге возвращаются назад)
- умножить каждое полученное число вместе и
xor его псевдослучайной битовой строкой длиной N / 4 .
- создать
final_id как first_id
- Для каждого идентификатора строки, сгенерированного таким образом,
xor final_id с идентификатором этой строки
Или в псевдокоде:
int ids[] = {};
for(string str : strings)
{
int id = 1;
for(char c: str)
{
id *= c * list.nextPrime();
}
id ^ hash1;
ids.push_back(id);
}
final_id = ids[0];
for(id : ids) final_id = (final_id * id) ^ hash2;
return final_id;
Это кажется достаточно случайным для хорошего выбора простых чисел и хэшей, но не гарантирует ненулевые цифры.
У меня также есть проблема, которую я не знаю, могу ли я сделать это равномерно распределенным (чтобы минимизировать коллизии хешей).
Есть предложения?