В общем случае невозможно построить функцию, отображающую строки произвольной длины в фиксированный домен. Это нарушает принцип сортировки.
Следующее предложение кажется мне довольно запутанным, но, учитывая отсутствие более широкого контекста вашей проблемы, здесь идет...
Предположим, вы создаете класс, через который прогоняете все ваши имена, т.е.
class compressor {
explicit compressor(std::size_t seed);
std::string operator()(const std::string &name) const;
}
Он состоит из двух элементов: ctor, принимающий начальное значение, и operator()
, принимающий строку имени и возвращающий строку ключа из 8 символов. В своем коде инициализируйте этот объект некоторым фиксированным произвольным начальным числом.
Внутри объект класса должен содержать сопоставление unordered_map
для каждого отдельного имени, к которому оно было применено, и ключ, с которым оно было сопоставлено. Изначально, очевидно, этот внутренний unordered_map
будет пуст.
Объект класса должен использовать универсальную хеш-функцию, псевдо -выбирается случайным образом seed
в конструкторе. См. ответ на этот вопрос об одном из способов создания универсальной хеш-функции.
Когда оператор вызывается, он должен проверить, находится ли имя во внутреннем unordered_map
. Если да, верните найденный для него ключ. В противном случае сначала используйте хэш-функцию для вычисления ключа и поместите его во внутренний файл unordered_map
. Однако при создании нового ключа проверьте, не конфликтует ли он с существующим ключом, и если это так, сгенерируйте исключение.
На самом деле, поскольку каждое отдельное имя соответствует месту в вашем коде, где вы вызываете typeid
, количество различных имен, скажем, n, должно быть не более 1000. Установите m как возможный диапазон с 8 символами (264).
Вероятность столкновения составляет ~n2 / (2 м), что должно быть крошечным. Таким образом, велика вероятность того, что коллизий и исключений не будет. Однако, если он выброшен, измените начальное значение и снова соберите программу. Ожидаемое количество раз, которое вам придется это сделать (после начального раза), близко к 0.
person
Ami Tavory
schedule
23.09.2016