Я ищу что-то вроде последовательного хеширования, но с гарантией того, что дистрибутив окажется честным насколько это возможно (не только в среднем для случайных ключей) - есть ли такое и где его найти, если да?
Редактировать. В моем конкретном случае набор ключей известен заранее (и "небольшой"). Именно эти ключи всегда будут присутствовать и должны быть назначены ровно одному узлу каждый в любой заданный момент времени.
Мне кажется, вы ищете минимальный идеальный хеш.
не только в среднем для случайных ключей
Это не точное описание гарантий, обеспечиваемых последовательным хэшированием. Во-первых, «в среднем» не отражает того факта, что при случайном размещении большого количества виртуальных узлов на круге и хорошем семействе хеш-функций (например, независимом от логарифмического уровня) дисбаланс нагрузки серьезно возрастает. вряд ли будет большим (я считаю, что обычный дисбаланс должен быть порядка квадратного корня из числа клавиш, назначенных конкретной машине). Во-вторых, ключи не обязательно должны быть случайными, если они не зависят от случайно выбранной хеш-функции (незаметный противник).
Поскольку вы хотите, чтобы хэширование было всегда честным, рандомизация не поможет, поскольку результаты ГСЧ могут быть неотличимы от этот. Ни один детерминированный алгоритм не может статически назначать предпочтения узла ключам без возможности дисбаланса, если только ключи не известны в автономном режиме.
Если у вас достаточно мало элементов, и вы заботитесь о дисбалансе квадратного корня, вы можете использовать старомодную балансировку нагрузки с отслеживанием состояния.
