Используют ли какие-либо хэш-таблицы (в памяти, нераспределенные) согласованное хеширование?

Я не слышал об этом в дикой природе, но это может быть хорошей идеей, если вы выберете правильную непротиворечивую реализацию хеширования. В частности, Jump Consistent Hashing от Google et al. Сначала я расскажу, почему Jump, а затем расскажу, как он может быть полезен в локальной структуре данных.

Согласованное хеширование с переходом

Согласованное хеширование с переходом (которое я буду сокращать до Jump) отлично подходит для этой области по нескольким причинам. Jump предполагает, что узлы не выходят из строя, что отлично подходит для локальных структур данных, потому что они не выходят из строя! Это позволяет Jump просто отображать диапазон чисел [0, numBuckets), требуя всего 2-4 байта пространства.

Далее реализация проста и быстра. И это даже быстрее, если мы удалим деление с плавающей запятой эталонной реализации и заменим его вдвое меньшим количеством целочисленных делений. (Что мы можем, кстати.)

Все это можно использовать для вариации на...

ConcurrentHashMap

Но сначала Конкурентная хеш-карта на высоком уровне.

ConcurrentHashMap в Java параметризуется несколькими сегментами. Этот коэффициент шардинга остается постоянным на протяжении всей жизни карты. Каждая из этих корзин сама по себе является хэш-картой со своей блокировкой.

При вставке пары ключ-значение в карту ключ хэшируется в одну из корзин. Блокировка для этого ключа берется, и элемент вставляется в хэш-карту корзины перед снятием блокировки. Во время вставки в корзину x другой поток может одновременно выполнять вставку в корзину y, но он будет ждать блокировки при вставке в корзину x. Таким образом, Java ConcurrentHashMap имеет n-сторонний параллелизм, где n — это параметр bucket конструктора.

Как и любая хеш-карта, сегмент в ConcurrentHashMap может заполниться, и ему нужно будет расти. Как и обычная хеш-карта, он делает это, удваивая свой размер и перефразируя все в ведре обратно в более крупное «я». За исключением того, что «его большее я» — это только «я» ведра. Если ведро является горячей точкой и получает больше ключей, чем ему положено, оно будет расти непропорционально по сравнению с другими ведрами. И каждый раз, когда ведро растет, требуется все больше и больше времени, чтобы перефразировать его. Этот последний пункт является проблемой не только для горячих точек, но и когда старая хеш-таблица получает больше ключей.

Представьте, если бы мы могли увеличивать количество сегментов по мере роста количества ключей. Таким образом, мы могли бы ослабить рост каждого отдельного ведра.

Введите согласованное хеширование, что позволит нам добавить больше сегментов!

ConcurrentHashMap дубль 2: согласованный стиль хеширования

Мы можем заставить ConcurrentHashMap увеличить количество корзин за два простых шага.

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

Второй отделить новое ведро, когда ведро заполнено; также вырастить наполненное ведро. На самом деле, отделяйте новое ведро только в том случае, если заполненное ведро становится самым большим с точки зрения вместимости. Это можно рассчитать без повторения ведер.

При последовательном хешировании разделение будет направлять ключи только в новое ведро, а не обратно в какое-либо из старых ведер.

Конечные примечания

Я уверен, что эту схему можно улучшить. А именно, отделение корзины требует полного сканирования таблицы, чтобы переместить ключи в новую корзину. Это, безусловно, не хуже, чем ванильная хеш-карта, и, вероятно, лучше, но это невыгодно реализации ConcurrentHashMap, которая, вероятно, не должна выполнять полное сканирование.