Упорядоченная строка в целочисленную хеш-функцию, сохраняющая лексикографический порядок своего аргумента
Допустим, у нас есть набор байтовых строк, отсортированных в лексикографическом порядке, как обычно. Мы хотим определить хеш-функцию, отображающую строку в целое число таким образом, чтобы порядок хеш-значений в достаточной степени сохранял порядок строк. То есть, если строка A меньше или равна строке B, H(A) всегда должно давать значение, меньшее или равное H(B).
Ясно, что возможна не очень хорошая хэш-функция такого рода. Например, мы можем взять фиксированный префикс каждой строки (скажем, 8 байт) и представить, что это int64 без знака с обратным порядком байтов. Полученные целые числа будут отсортированы в желаемом порядке. Этот подход работает даже для более коротких строк: мы можем добавить несколько нулей к короткой строке, чтобы сделать ее длиной не менее байтов префикса (но только если мы можем предположить, что 0 не является допустимым значением байта).
К сожалению, это потенциальное решение, хотя и быстрое и простое, имеет серьезные недостатки. Это становится довольно бесполезным в тех случаях, когда строки обычно содержат значительные общие префиксы. Он не может обрабатывать строки короче выбранного префикса, когда «0x00» является значимым байтом, и мы хотим сортировать более короткие строки перед более длинными.
Так вот вопрос можно ли сделать лучше? Какой-то арифметический (или, скорее, своего рода «конкретная математика» Кнута) трюк, который может учитывать все байты строки и давать правильно упорядоченное хеш-значение?
Откуда взялась эта проблема? Очень похожий вопрос задал вчера человек, который сказал, что «сам придумал проблему»: Как отсортировать нечисловые строки, преобразовав их в целые числа? Есть ли способ преобразовать строки в уникальные целые числа при заказе?
Сначала отсортируйте строки по порядку. Присвойте каждой строке хеш-значение, эквивалентное ее положению в отсортированном массиве: 0, 1, 2, 3,... Это точно сохраняет порядок сортировки в хеш-функции. Если вы хотите добавить новые строки, пронумеруйте исходные строки: 0, 10, 20, 30, ..., чтобы можно было вставлять их позже. Возможно, вам придется повторно хешировать весь массив, если в одной части слишком много вставок.
@kcsquared Я пропустил этот другой вопрос. Согласен, похоже. В моем случае проблема возникает из-за ключевых подходов к разделению в конкретной базе данных.
@rossum Нет, у нас нет всех строк заранее.
Ответы 1
Лучшее, что вы можете сделать, это применить сохраняющий порядок арифметическое кодирование, основанный на наилучшей статистической модели строк, которую вы можете придумать, а затем взять префикс для формирования "хеш-кода".
Тогда каждый хеш-код будет равновероятным в соответствии с этой статистической моделью.
Если ваша модель состоит в том, что все строки равновероятны, то это сводится к вашей «просто возьмите идею префикса»… так что, сработает ли это для вас, действительно зависит от того, как много вы знаете о своих строках и насколько хорошо вы нужно, чтобы этот код был.
Также обратите внимание, что многие реалистичные модели также допускают более простую схему кодирования. «просто возьмите префикс» снова является примером этого.
Большинство вещей, которые люди могут подумать, что хотят делать с помощью такого «хеш-кода», непрактичны — вы, вероятно, в конечном итоге сделаете что-то другое. Может быть, вы хотите спросить о своей реальной проблеме, чтобы мы могли помочь решить ее каким-то другим способом.
Проблема под рукой - разделение. Учитывая так много строк, я хочу разбить их на разделы таким образом, чтобы числовые идентификаторы разделов следовали общему порядку всей коллекции.
Я вижу, что люди уже думали о подобных проблемах раньше (например, rsrikant.com/papers/sigmod04.pdf). Предположим, это что-то, что я должен тщательно исследовать.
Зачем нужно свойство сохранения порядка?
То, что вы описываете, похоже, имеет мало общего с тем, что большинство людей называют «хеш-функциями». Какие «хешированные» свойства этой функции вам нужны?