Мне сложно понять детали реализации из 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;
Это плохо - слот занят и уже на месте запись равна той, которую мы хотим поставить. Sets не может иметь повторяющихся элементов, поэтому позже создается исключение.
else if (++idx == elements.length) {
idx = 0;
}
Это означает, что этот слот занят (хеш-коллизия), но элементы не равны. В HashMap эта запись будет помещена в ту же корзину, что и LinkedNode или TreeNode, но не здесь.
Таким образом, index увеличивается, и пробуется следующая позиция (с небольшой оговоркой, что она перемещается по кругу, когда достигает последней позиции).
И вот вопрос: если при поиске по индексу ничего особенного (если я что-то не упускаю) не делается, зачем нужен массив в два раза больше? Или почему функция не была написана так:
int idx = Math.floorMod(pe.hashCode() ^ SALT, input.length);
// notice the diff elements.length (8) and not input.length (4)
probe) - person Dioxin schedule 27.07.2017