Лучшая хеш-функция для смешанных числовых и литеральных идентификаторов
Типы числовых данных, которые заказаны в порядке возрастания или убывания, являются хорошими индексами по нескольким причинам. Во-первых, числа обычно быстрее для оценки, чем строки (varchar, символ, nvarchar, и т.д.). Во-вторых, если Ваши значения не заказаны, строки и/или страницы, возможно, должны быть переставлены собирающийся обновление Ваш индекс. Это дополнительно служебный.
, Если Вы используете SQL Server 2005 и набор при использовании uniqueidentifiers (гуиды), и НЕ нуждаетесь в них, чтобы быть случайной природы, проверить последовательный тип uniqueidentifier.
Наконец, если Вы говорите о кластерных индексах, Вы говорите о виде физических данных. Если у Вас есть строка как Ваш кластерный индекс, который мог бы стать ужасным.
3 ответа
Две хорошие хэш-функции могут быть отображены в одно и то же пространство значений, и, как правило, не вызовут никаких новых проблем в результате их объединения.
Так ваша хеш-функция может выглядеть вот так:
if it's an integer value:
return int_hash(integer value)
return string_hash(string value)
Если ваши целые числа не сгруппированы вокруг определенных значений по модулю N, где N - возможное количество сегментов, тогда int_hash может просто вернуть введенные данные.
Выбор строкового хеша - это не новая проблема. Попробуйте "djb2" ( http://www.cse.yorku.ca/~oz/hash.html ) или аналогичный, если у вас нет неприличных требований к производительности.
Я не думаю, что здесь много Пункт в модификации хеш-функции для учета общих префиксов. Если ваша хеш-функция хороша для начала, то маловероятно, что общие префиксы создадут какое-либо скопление хеш-значений.
Если вы сделаете это, и хэш не будет неожиданно работать плохо, и вы поместите несколько миллионов хеш-значений в несколько тысяч сегментов, то популяции сегментов будут нормально распределены со средним значением (несколько миллионов / несколько тысяч ) и дисперсия 1/12 (несколько тысяч) ^ 2
В среднем 1500 записей на сегмент, что составляет стандартное отклонение где-то около 430. 95% нормального распределения находится в пределах 2 стандартных отклонений от среднего, поэтому 95% ваших корзин будут содержать 640–2360 записей, если я не ошибся с суммой. Этого достаточно, или вам нужно, чтобы ведра были более близки по размеру?
со средним значением (несколько миллионов / несколько тысяч) и дисперсией 1/12 (несколько тысяч) ^ 2В среднем 1500 записей на сегмент, что составляет стандартное отклонение где-то около 430. 95% нормального распределения лежит в пределах 2 стандартных отклонений от среднего, поэтому 95% ваших сегментов будут содержать 640–2360 записей, если я не ошибся в своих суммах. Этого достаточно, или вам нужно, чтобы ведра были более близки по размеру?
со средним значением (несколько миллионов / несколько тысяч) и дисперсией 1/12 (несколько тысяч) ^ 2В среднем 1500 записей на сегмент, что составляет стандартное отклонение где-то около 430. 95% нормального распределения лежит в пределах 2 стандартных отклонений от среднего, поэтому 95% ваших сегментов будут содержать 640–2360 записей, если я не ошибся в суммах. Этого достаточно, или вам нужно, чтобы ведра были более близки по размеру?
Вы, вероятно, будете в безопасности, используя sha1 и усекая его до любого размера, который вам нужен.
Это было бы не очень эффективно, но, возможно, хэш-функция победила Не будет узким местом?
Я считаю, что CRC16 будет разумным хешем для использования в этих строках, а группы не должны превышать 1-2 тысячи.
Это должно сделать хеш-таблицу размером около 1 МБ + сколько бы элементов в нем не было * 4 байта, то есть мы говорим о 50 МБ, а затем у вас также есть все фактические данные, которые должны быть очень маленькими.