Перефразирование Java8 Hashmap в случае возврата постоянного хеш-кода

Question

В соответствии с приведенным ниже кодом, начальная емкость по умолчанию для hashmap равна 16, а LF равна 0,75, поэтому, когда я вхожу в 13-й элемент, должна произойти перефразировка, и поскольку я предоставил постоянный хэш-код, он внутренне поддерживает связанный список для поддержания порядка вставки.Таким образом, до 10-го элемента он работает как положено, но когда я вхожу в 11-й элемент, он перетасовывает порядок.Кто-нибудь может мне помочь понять, почему это происходит только во время вставки 11-го элемента.

class A{
    int a;

    A(int a){
        this.a = a;
    }
    @Override
    public int hashCode() {
        return 7;
    }
    @Override
    public String toString() {
        return "" + a + "";
    }
}
class Base {
    public static void main(String[] args) {
        Map<Object, Integer> m = new HashMap<Object, Integer>();
        m.put(new A(1), 1);
        m.put(new A(2), 1);
        m.put(new A(3), 1);
        m.put(new A(4), 1);
        m.put(new A(5), 1);
        m.put(new A(6), 1);
        m.put(new A(7), 1);
        m.put(new A(8), 1);
        m.put(new A(9), 1);
        m.put(new A(10), 1);
        //m.put(new A(11), 1);
        System.out.println(m);
    }
}

Вывод, который я получаю до 10-го элемента:

{1=1, 2=1, 3=1, 4=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1}

Вывод, который я получаю после ввода 11-го элемента:

{4=1, 1=1, 2=1, 3=1, 5=1, 6=1, 7=1, 8=1, 9=1, 10=1, 11=1}

Должен поддерживаться вставкапорядок или если он использует дерево RB внутри, так какой обход он использует здесь в этом случае?

Answer 1

Он не зависит от указанного номера хеш-кода, т. Е. 7, и, скорее всего, ваш код является константой, вызывающей его.Вот почему:

Я просмотрел исходный код метода put в HashMap, и есть константа TREEIFY_THRESHOLD, которая решает, когда преобразовывать обычное ведро в дерево.

staticfinal int TREEIFY_THRESHOLD = 8;

Ниже приведен фрагмент кода метода put (метод Put вызывает метод putVal):

.
.
.

                for (int binCount = 0; ; ++binCount) {

                    if ((e = p.next) == null) {

                        p.next = newNode(hash, key, value, null);

                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                            treeifyBin(tab, hash);

                        break;

                    }
.
.
.

Обратите внимание на строку, содержащую if (binCount >= TREEIFY_THRESHOLD - 1)состояние.Как только он обнаруживает, что емкость заполнена до TREEIFY_THRESHOLD, он вызывает метод treeifyBin().

Этот метод, в свою очередь, вызывает метод resize() только тогда, когда встречается MIN_TREEIFY_CAPACITY.

 final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;

            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

Найдите приведенное выше условие во фрагменте выше

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();

Метод изменения размера затем увеличит размер карты соответственно на основе нескольких условных проверок, которые у него есть.Это в основном увеличивает емкость на коэффициент загрузки.

Точно так же, как treeify, если нет.элементов в дереве уменьшите.Операция Untreeify выполняется с использованием UNTREEIFY_THRESHOLD, то есть 6. В качестве базы.

Я ссылался на эту ссылку для прохождения кода Hashmap.

Answer 2

Он должен поддерживать порядок вставки или если он использует дерево RB внутри, так какой обход он использует здесь в этом случае?

Там нет «должен»;HashMap не гарантирует какой-либо заказ.Что на самом деле происходит в текущей реализации, определяется двумя константами, TREEIFY_THRESHOLD = 8 и MIN_TREEIFY_CAPACITY = 64.

Когда количество элементов в одном сегменте превышает первое, сегмент будет преобразован в дерево узлов, если общая емкость карты не будет меньше, чем последняя константа, в этом случае емкость будет удвоена.

Таким образом, когда вы вставите 9-й объект, емкость будет увеличена с 16 до 32, вставив 10-йвызывает повышение с 32 до 64, затем вставка 11-го элемента вызовет преобразование сегмента в дерево.

Это преобразование всегда будет происходить независимо от того, есть ли реальная выгода или нет.Поскольку объекты имеют идентичные хеш-коды и не реализуют Comparable, в конечном итоге они будут использовать свои хеш-коды для определения порядка.Это может привести к изменению порядка (в моем окружении это не так).