Углубленный анализ HashMap

Обзор

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

Почему он называется HashMap? Как это реализовано внутри? Большую часть времени он используется, String используется в качестве его ключа? Давайте взглянем на HashMap и подробно объясним вам эти проблемы.

Происхождение названия HashMap

На самом деле происхождение HashMap основано на технологии Hasing (Hasing).Хасинг заключается в преобразовании большой строки или любого объекта в небольшое значение, используемое для их представления.Эти более короткие значения можно легко использовать для облегчения индексации, для ускорить поиск.

Что такое хэш-карта

HashMap — это коллекция, используемая для хранения пар ключ-значение, вы можете использовать «ключ» для хранения данных. Когда вы хотите получить данные, вы можете получить данные через «ключ», каждая пара «ключ-значение» также называется Entry. Эти пары ключ-значение (Entry) разбросаны и хранятся в массиве, который является основой HashMap.

Сначала введите переменные HashMap

size, это размер хранилища HashMap.thresholdЭто критическое значение HashMap, также называемое пороговым значением.Если HashMap достигает критического значения, размер необходимо перераспределить.loadFactorявляется коэффициентом загрузки и по умолчанию равен 75%. Порог = текущая длина массива ✖ коэффициент загрузки.modCountОтносится к общему количеству изменений или удалений HashMap.

Структура хранения HashMap

Запись разбросана и хранится в таблице-массиве типа Entry, и все данные в таблице являются объектом Entry. Направление оси Y представляет собой массив, а направление оси X — способ хранения связанного списка.

Тип Entry хранится в таблице, класс Entry содержит переменную хэш-кода, ключ, значение и другой объект Entry. Потому что это структура связанного списка. Найдите вас через меня, и вы найдете его. Однако Entry здесь не является LinkedList, это класс с внутренней структурой односвязного списка, который обслуживает только HashMap.

Характеристики массива заключаются в том, что запрос выполняется быстро, временная сложность — O(1), операции вставки и удаления — относительно медленные, а временная сложность — O(n). Способ хранения связанного списка несмежный, размер не фиксированный, характеристики противоположны массиву, вставка и удаление быстрые, скорость запроса медленная. HashMap обращается к ним и выбирает их сегменты, можно сказать, что операции запроса, вставки и удаления будут несколько ускорены.

Основы HashMap

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
public final int hashCode() {
    return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 static int indexFor(int h, int length) {
        return h & (length-1);
    }

        int h=15,length=16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0001111", 2) & Integer.parseInt("0001111", 2));
        h=15+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0011111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0111111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("1111111", 2) & Integer.parseInt("0001111", 2));

public HashMap(int initialCapacity, float loadFactor) {
　// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。
　// loadFactor代表它的负载因子，默认是是DEFAULT_LOAD_FACTOR=0.75，用来计算threshold临界值的。    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Из приведенного выше кода видно, что при инициализации необходимо знать инициализированную емкость, потому что индекс массива Entry будет вычисляться позже с помощью побитового алгоритма AND Hash, поэтому длина массива Entry должна быть от 2 до N-я власть.

поставить операцию

Как HashMap хранит объект?Код выглядит следующим образом:

public V put(K key, V value) {
        //数组为空时创建数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //①key为空单独对待
        if (key == null)
            return putForNullKey(value);
        //②根据key计算hash值
        int hash = hash(key);
        //②根据hash值和当前数组的长度计算在数组中的索引
        int i = indexFor(hash, table.length);
        //遍历整条链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //③hash值和key值都相同的情况，替换之前的值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                //返回被替换的值
                return oldValue;
            }
        }

        modCount++;
        //③如果没有找到key的hash相同的节点,直接存值或发生hash碰撞都走这
        addEntry(hash, key, value, i);
        return null;
    }

Как видно из кода, шаги следующие:

1. Во-первых, он определит, может ли он быть нулевым.Если он нулевой, вызовите pullForNullKey(value) для обработки. код показывает, как показано ниже:

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

Если значение ключа равно null, оно будет сохранено в связанном списке в начале таблицы [0] по умолчанию. Затем пройтись по каждой записи узла связанного списка таблицы [0], если обнаружено, что ключ записи узла равен нулю, заменить новое значение, а затем вернуть старое значение, если нет записи узла с ключом, равным null найден, добавьте новый узел.

2. Вычислите хэш-код ключа, а затем используйте вычисленный результат для двойного хеширования и найдите индекс i массива Entry с помощью indexFor(hash, table.length);.

(3) Затем пройдите по связанному списку с таблицей [i] в ​​качестве головного узла.Если вы найдете узел с тем же хешем и ключом, замените его новым значением, а затем верните старое значение.

Если узел с таким же хешем ключа не найден, добавьте новый узел addEntry(), код выглядит следующим образом:

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
        //判断数组容量是否足够，不足够扩容
            resize(2 * table.length);
    }

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

    void resize(int newCapacity) { //传入新的容量
        //获取旧数组的引用
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //极端情况，当前键值对数量已经达到最大
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //修改阀值为最大直接返回
            threshold = Integer.MAX_VALUE;
            return;
        }
        //步骤①根据容量创建新的数组
        Entry[] newTable = new Entry[newCapacity];
        //步骤②将键值对转移到新的数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //步骤③将新数组的引用赋给table
        table = newTable;
        //步骤④修改阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    void transfer(Entry[] newTable, boolean rehash) {
        //获取新数组的长度
        int newCapacity = newTable.length;
        //遍历旧数组中的键值对
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //计算在新表中的索引，并到新数组中
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }