Как сопоставить 100 миллионов строк в 100 тысяч int?

Question

У меня около 100 миллионов простых пар ключ-значение (это устаревшие данные, их не нужно обновлять, а клавиши - случайные строки), и я хочу их хранить в redis для запроса.

Я думал, что я использую первые четыре символа в качестве хэш-ключа и сохраняю их в хэш-тип, поэтому в redis есть около миллиона хэш-ключей, причем каждый хэш-ключ имеет около 1000 под-клавиш.

, но все просто не идет по плану. по какой-то причине я обнаружил, что некоторые хеш-ключи имеют только один под-ключ, но некоторые из них содержат более 500 000 под-клавиш, которые могут не кодироваться в памяти очень эффективно.

, так что я хотел бы знать, что есть какой-то простой понятный алгоритм, который может разделить мою 100-миллионную строку в среднем на 100 тысяч ведер (int). когда я беру строку, я могу знать, где она идет, используя тот же алгоритм.

спасибо !!

Answer 1

Использование только небольшой части строки для вычисления хеш-функции может быть проблемой, потому что ваши строки могут, например, иметь общий префикс.

Существует описание строковых хеш-функций, которые принимают всю строку в http://www.javamex.com/tutorials/collections/hash_function_technical_2.shtml и Good Hash Function for Strings (фактически они дают два разных описания одной и той же функции).

Один из способов взглянуть на это состоит в том, что он рассматривает символы строки как коэффициенты A, B, C многочлена вида A + Bx + Cx^2 + Dx^3 ... где в этом случай x равен 31, а арифметика - по модулю 2^32. Если x хорошо выбран, то это схема, в которой есть много опыта, и может быть применена математика, которая дает хорошие свойства. Еще лучше сделать арифметику по размеру хэш-таблицы и выбрать размер хеш-таблицы как простой. Если ваши данные статичны, возможно, стоит попробовать несколько разных простых чисел вокруг вашего предпочтительного размера таблицы и нескольких разных значений x и выбрать комбинацию, которая дает вам наиболее равномерно заполненную таблицу.