Непрерывная реализация

Мне сложно понять деталь реализации из java-9 ImmutableCollections.SetN; в частности, почему требуется увеличить внутренний массив дважды.

Предположим, вы это сделали:

Set.of(1,2,3,4) // 4 elements, but internal array is 8

Точнее, я прекрасно понимаю, почему это делается (двойное расширение) в случае HashMap - где вы никогда (почти) не хотите, чтобы load_factor был одним. Значение !=1 улучшает время поиска, поскольку записи, например, лучше распределяются на ведра.

Но в случае непреложного Сета - я не могу сказать. Тем более, что выбирается индекс внутреннего массива.

Позвольте мне представить некоторые подробности. Сначала, как выполняется поиск индекса:

 int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);

pe - это фактическое значение, которое мы помещаем в набор. SALT составляет всего 32 бита, сгенерированных при запуске, один раз за JVM (это фактическая рандомизация, если вы хотите). elements.length для нашего примера - 8 (4 элемента, но здесь 8 - двойной размер).

Это выражение похоже на отрицательную операцию по модулю. Обратите внимание, что то же самое логическое дело выполняется в HashMap, например ((n - 1) & hash), когда выбран ковш.

Итак, если elements.length is 8 для нашего случая, то это выражение вернет любое положительное значение, меньшее 8 (0, 1, 2, 3, 4, 5, 6, 7).

Теперь остальная часть метода:

 while (true) {
        E ee = elements[idx];
        if (ee == null) {
            return -idx - 1;
        } else if (pe.equals(ee)) {
            return idx;
        } else if (++idx == elements.length) {
            idx = 0;
        }
    }

Позвольте сломать его:

if (ee == null) {
    return -idx - 1;

Это хорошо, это означает, что текущий слот в массиве пуст - мы можем поместить наше значение там.

} else if (pe.equals(ee)) {
    return idx;

Это плохо - слот занят, а уже введенная позиция равна той, которую мы хотим поставить. Set не может иметь повторяющиеся элементы, поэтому позже вызывается Exception.

 else if (++idx == elements.length) {
      idx = 0;
 }

Это означает, что этот слот занят (хеш-столкновение), но элементы не равны. В a HashMap эта запись будет помещена в тот же самый ведро, что и LinkedNode или TreeNode, но не здесь.

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

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

int idx = Math.floorMod(pe.hashCode() ^ SALT, input.length);

// notice the diff elements.length (8) and not input.length (4)

Ответы

Ответ 1

Текущая реализация SetN - довольно простая замкнутая схема хэширования, в отличие от отдельного подхода к цепочке, используемого HashMap. ( "Закрытое хеширование" также смутно известно как " открытая адресация".) В замкнутой схеме хэширования элементы сохраняются в самой таблице, вместо этого сохраняются в списке или дереве элементов, которые связаны из каждого слота таблицы, который является отдельной цепочкой.

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

Если вы хотите сохранить элементы N, они обязательно попадут в таблицу размера N. Вы всегда можете найти какой-либо элемент в наборе, хотя вам, возможно, придется исследовать несколько (или много) последовательных слотов таблицы, чтобы найти его, потому что будет много столкновений. Но если набор исследуется для объекта, который не является членом, линейное исследование должно будет проверять слот таблицы каждый, прежде чем он сможет определить, что объект не является членом. При полной таблице большинство операций зондирования будут деградировать до O (N) времени, тогда как цель большинства хэш-ориентированных подходов заключается в том, чтобы операции были временем O (1).

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

В процессе реализации мы провели ряд тестов с использованием разных факторов расширения. (Я использовал термин EXPAND_FACTOR в коде, тогда как в большинстве литературы используется коэффициент загрузки. Причина в том, что коэффициент расширения является взаимным фактором нагрузки, используемым в HashMap, и использование "коэффициента загрузки" для обоих значений будет путать.) Когда коэффициент расширения был около 1,0, производительность зонда была довольно медленной, как ожидалось. Он значительно улучшился по мере увеличения коэффициента расширения. Улучшение действительно сгладилось к моменту, когда оно поднялось до 3.0 или 4.0. Мы выбрали 2.0, так как он получил большую часть улучшения производительности (близко к O (1) раз), обеспечивая при этом хорошую экономию пространства по сравнению с HashSet. (Извините, мы нигде не публикуем эти контрольные цифры.)

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

Хорошее обсуждение открытых соглашений об адресации и производительности с коэффициентами нагрузки можно найти в разделе 3.4

Седжуик, Роберт и Кевин Уэйн. Алгоритмы, четвертое издание. Addison-Wesley, 2011.

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