Пять минут, чтобы понять исходный код Hashtable и отличие от HashMap

Java
image

предисловие

Предыдущий Что мы знаемMap,Hash,понялHashНесколько распространенных методов борьбы с коллизиями хэшей (метод застежки-молнии, метод открытой адресации) и анализ версии JDK1.8.HashMapИсходный код, есть предварительное представление о структуре сбора Java, мы продолжаем анализировать версию JDK1.8 этой статьи.Hashtableисходный код, окончательное сравнениеHashMapа такжеHashtableразница.

Hashtable

Обратите внимание, что Hashtable не является HashTable (t в нижнем регистре), разве это не нарушает теорему о верблюжьем случае? Это должно начаться с рождения Hashtable, Hashtable находится вJava1.0был создан во временаJava2Это было согласовано в начале, и в то время была выпущена новая коллекция, чтобы заменить ее, поэтому это имя использовалось до сих пор, поэтому Hashtable являетсяустаревшийКоллекция не рекомендуется всем для использования этого класса.Хотя Hashtable устарел, нам все еще необходимо проанализировать его, чтобы иметь общее представление о структуре коллекции Java.
первыйHashtableиспользоватьмолния методобрабатывать коллизии хэшей, дапотокобезопасность, значение ключа не может бытьnull, то Hashtable наследуется от Dictionary и реализует интерфейс Map.Hashtable имеет несколько важных переменных-членов.table,count,threshold,loadFactor

  • таблица: этоEntry[]тип данных, в то время какEntryна самом деле односвязный список
  • count: размер Hashtable, то есть количество пар ключ-значение, сохраненных в Hashtable.
  • порог: порог хеш-таблицы, используемый для определения необходимости корректировки емкости хеш-таблицы, порог = емкостькоэффициент нагрузки，порог=11*0,75 с округлением до 8
  • loadFactor: используется для реализации механизма быстрого отказа.

Конструктор

Hashtableимеет 4 конструктора

//无参构造函数 默认Hashtable容量是11，默认负载因子是0.75
public Hashtable() {
    this(11, 0.75f);
}

//指定Hashtable容量，默认负载因子是0.75
public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

//指定Hashtable的容量和负载因子
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    //new一个指定容量的Hashtable
    table = new Entry<?,?>[initialCapacity];
    //阈值threshold=容量*负载因子
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

//包含指定Map的构造函数
public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

Существует разница между емкостью Hashtable и емкостью HashMap.Hashtable не требует, чтобы емкость была степенью 2, а HashMap требует, чтобы емкость была степенью 2. По умолчанию коэффициент загрузки равен 0,75.

положить метод

putпутьСинхронизировать, т. е. потокобезопасный, this иHashMapразные, есть специфическиеputоперация иHashMapЕсть и большая разница: при вставке Hashtable она вставляется взаголовок связанного списка, а HashMap вставляется вконец связанного списка.

//synchronized同步锁，所以Hashtable是线程安全的
public synchronized V put(K key, V value) {
    // Make sure the value is not null
    //如果值value为空，则抛出异常 至于为什么官方不允许为空，下面给出分析
    if (value == null) {
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    //直接取key的hashCode()作为哈希地址，这与HashMap的取hashCode()之后再进行hash()的结果作为哈希地址 不一样
    int hash = key.hashCode();
    //数组下标=(哈希地址 & 0x7FFFFFFF) % Hashtable容量，这与HashMap的数组下标=哈希地址 & (HashMap容量-1)计算数组下标方式不一样，前者是取模运算，后者是位于运算，这也就是为什么HashMap的容量要是2的幂次方的原因，效率上后者的效率更高。
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    //遍历Entry链表，如果链表中存在key、哈希地址相同的节点，则将值更新，返回旧值
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    //如果为新的节点，则调用addEntry()方法添加新的节点
    addEntry(hash, key, value, index);
    //插入成功返回null
    return null;
}

private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry<?,?> tab[] = table;
    //如果当前键值对数量>=阈值，则执行rehash()方法扩容Hashtable的容量
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        //获取key的hashCode();
        hash = key.hashCode();
        //重新计算下标，因为Hashtable已经扩容了。
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    //获取当前Entry链表的引用 复赋值给e
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //创建新的Entry链表的 将新的节点插入到Entry链表的头部，再指向之前的Entry，即在链表头部插入节点，这个和HashMap在尾部插入不一样。
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

Почему hashCode() и 0x7FFFFFFF? Поскольку hashCode() некоторых объектов может быть отрицательным, & 0x7FFFFFFF гарантирует, что нижний индекс, полученный при выполнении операции %, является положительным числом.

получить метод

getметод также является синхронным, иHashMapНе то же самое, а именно потокобезопасность, специфическаяgetоперация иHashMapЕсть и отличия.

//同步
public synchronized V get(Object key) {
    Entry<?,?> tab[] = table;
    //和put方法一样 都是直接获取key的hashCode()作为哈希地址
    int hash = key.hashCode();
    //和put方法一样 通过(哈希地址 & 0x7FFFFFFF)与Hashtable容量做%运算 计算出下标
    int index = (hash & 0x7FFFFFFF) % tab.length;
    //遍历Entry链表，如果链表中存在key、哈希地址一样的节点，则找到 返回该节点的值，否者返回null
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

метод удаления

//同步
public synchronized V remove(Object key) {
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>)tab[index];
    //遍历Entry链表，e为当前节点，prev为上一个节点
    for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
        //找到key、哈希地址一样的节点
        if ((e.hash == hash) && e.key.equals(key)) {
            modCount++;
            //如果上一个节点不为空(即不是当前节点头结点)，将上一个节点的next指向当前节点的next，即将当前节点移除链表
            if (prev != null) {
                prev.next = e.next;
            } else { //如果上一个节点为空，即当前节点为头结点，将table数组保存的链表头结点地址改成当前节点的下一个节点
                tab[index] = e.next;
            }
            //Hashtable的键值对数量-1
            count--;
            //获取被删除节点的值 并且返回
            V oldValue = e.value;
            e.value = null;
            return oldValue;
        }
    }
    return null;
}

метод перефразирования

Хеш-таблицаrehashметоды и HashMapresizeМетод тот же, он используется для расширения хеш-таблицы, но реализация расширения отличается.

protected void rehash() {
    //获取旧的Hashtable的容量
    int oldCapacity = table.length;
    //获取旧的Hashtable引用，为旧哈希表
    Entry<?,?>[] oldMap = table;

    // overflow-conscious code
    //新的Hashtable容量=旧的Hashtable容量 * 2 + 1，这里和HashMap的扩容不一样，HashMap是新的Hashtable容量=旧的Hashtable容量 * 2。
    int newCapacity = (oldCapacity << 1) + 1;
    //如果新的Hashtable容量大于允许的最大容量值(Integer的最大值 - 8)
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        //如果旧的容量等于允许的最大容量值则返回
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        //新的容量等于允许的最大容量值
        newCapacity = MAX_ARRAY_SIZE;
    }
    //new一个新的Hashtable 容量为新的容量
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    //计算新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;
    //扩容后迁移Hashtable的Entry链表到正确的下标上
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

Затем мы выполняем следующий код, чтобы проверить следующий процесс переноса данных.

Hashtable hashtable = new Hashtable();
for (int i = 1; i <= 24; i ++) {
    hashtable.put(String.valueOf(i), i);
}
for (int i = 25; i <= 80; i ++) {
    hashtable.put(String.valueOf(i), i);
}

newHashtable с емкостью по умолчанию11, коэффициент нагрузки0.75
выполнить первыйforПосле цикла,20сохранить в подстрочном индексе как0изEntryв, т.е.(hash &0x7FFFFFFF) % 容量 -> (1598 &0x7FFFFFFF) % 11 = 0

выполнить второйforПосле цикла становится20сохранить в подстрочном индексе как70изEntry, потому что хеш-таблица была расширена 4 раза, соответственно, от емкости по умолчанию 11->23->47->95->191, а затем емкость в это время составляет 191, поэтому(hash &0x7FFFFFFF) % 容量 -> (1598 &0x7FFFFFFF) % 191 = 70

Разница между HashMap и Hashtable

Здесь мы проанализировали принципы HashMap и Hashtable, а теперь сравним различия между ними.

разница

  • Унаследованные классы не совпадают: унаследовано от HashMapAbstractMapАбстрактный класс, унаследованный от HashtableDictionayабстрактный класс
  • Различные способы борьбы с многопоточностью: HashMap не является потокобезопасным, Hashtable является потокобезопасным, поэтому Hashtable менее эффективен.
  • Различные алгоритмы позиционирования: HashMap пройденkeyhashCode() выполняет hash() для получения хеш-адреса, индекс массива = хэш-адрес и (емкость - 1), используя операцию И, поэтомуЕмкость должна быть степенью двойки, чтобы результат был таким же, как результат операции по модулю.. Hashtable: индекс массива = (key's hashCode() & 0x7FFFFFFF ) % емкости, используется операция по модулю, поэтому емкость не требуется.
  • Правила пары ключ-значение отличаются: HashMap допускает ключевые значенияnull, а Hashtable не допускает значений ключейnull
  • Алгоритм расширения хеш-таблицы другой: Расширение емкости HashMap основано на исходной емкости*2, а расширение емкости Hashtable основано на исходной емкости*2+1.
  • Значение емкости по умолчанию отличается: значение емкости HashMap по умолчанию — 16, а значение по умолчанию Hashtable — 11.
  • Метод put реализован иначе: HashMap вставляет узлы в конец связанного списка, а Hashtable вставляет узлы в начало связанного списка.
  • Базовая структура отличается: HashMap принимаетМассив + связанный список + красное черное дерево, а Hashtable используетмассив + связанный список

Почему HashMap позволяетnullА как насчет ключевых значений, а Hashtable не позволяетnullКак насчет ключевых значений? Здесь мы должны сначала представить, что такоеnull, мы знаем, что в языке Java есть два типа, один из нихбазовый типДругойтип ссылкина самом деле существует особый типnullТип, он не представляет ни объект (Object), ни объект (Object), а затем используется в операции HashMap и Hashtable над ключамиObjectв классеequalsметод, поэтому, если значение ключа установлено в HashtablenullЕсли это так, вполне возможно, что будет сообщено об ошибке, но почему HashMap это делает? Поскольку HashMap использует особый способ,nullПреобразовывается в объект (Object), как его преобразовать, я не буду здесь подробно останавливаться.

Та же точка

  • реализовать тот же интерфейс: реализованы HashMap и Hashtable.Mapинтерфейс
  • Значение коэффициента нагрузки по умолчанию (loadFactor) такое же: коэффициент загрузки HashMap и Hashtable по умолчанию равен 0,75.
  • Столкновения хэшей обрабатываются таким же образом.: Оба используют метод цепного адреса, то есть метод застежки-молнии для обработки хэш-коллизий.
  • Один и тот же хеш-адрес может быть назначен разным связанным спискам, и хеш-адреса узлов в одном и том же связанном списке не обязательно совпадают.: поскольку и HashMap, и Hashtable будут расширены, емкость изменится после расширения, и индексы массива, полученные с одного и того же хэш-адреса, также будут другими.

Ссылаться на

Принцип и отличие HashMap, HashTable, ConcurrentHashMap
Анализ исходного кода хеш-таблицы коллекции Java

Оригинальный адрес: https://ddnd.cn/2019/03/08/jdk1-8-hashtable/

Категории