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

Переменная-член хеш-таблицы

private transient Entry[] table;  
// Hashtable中元素的实际数量  
private transient int count;  
// 阈值，用于判断是否需要调整Hashtable的容量（threshold = 容量*加载因子）  
private int threshold;  
// 加载因子  
private float loadFactor;  
// Hashtable被改变的次数  
private transient int modCount = 0;  

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

Затем позиция индекса в массиве таблиц определяется значением хеша, и, наконец, значение значения заменяется или вставляется новый элемент.Если количество контейнеров достигает порога, оно будет расширено.

Анализ исходного кода

Метод строительства

    //默认构造函数，容量为11，负载因子是0.75
    public Hashtable() {
        this(11, 0.75f);
    }
    //用指定初始容量和默认的加载印在（0.74）构造一个空的哈希表。
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }
    //用指定初始容量和指定加载因子构造一个新的空哈希表。其中initHashSeedAsNeeded方法用于初始化
    hashSeed参数，其中hashSeed用于计算key的hash值，它与key的hashCode进行按位异或运算。
    这个hashSeed是一个与实例相关的随机值，主要用于解决hash冲突：

    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;
    //初始化table，获得大小为initialCapacity的table数组  
    //这里是与HashMap的区别之一，HashMap中table
        table = new Entry[initialCapacity];
    //计算阀值    
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    //初始化HashSeed值   
     initHashSeedAsNeeded(initialCapacity);
    }

    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

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

public synchronized V put(K key, V value) {//这里方法修饰符为synchronized,所以是线程安全的。
        // 确保value不为null  
        if (value == null) {
            throw new NullPointerException();//value如果为Null,抛出异常
        }
        Entry tab[] = table;

        //计算key的hash值，确认在table[]中的索引位置  

        int hash = hash(key);
        //hash里面的代码是hashSeed^key.hashcode(),null.hashCode()会抛出异常，所以这就解释了
        Hashtable的key和value不能为null的原因。

        int index = (hash & 0x7FFFFFFF) % tab.length;
        //获取数组元素下标,先对hash值取正，然后取余。
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                //迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值  
                V old = e.value;
                e.value = value;
                return old;
            }
        }

        modCount++;//修改次数。
        if (count >= threshold) {//键值对的总数大于其阀值
            rehash();//在rehash里进行扩容处理
            tab = table;
            hash = hash(key);
            //hash&0x7FFFFFFF是为了避免负值的出现，对newCapacity求余是为了使index
            在数组索引范围之内
            index = (hash & 0x7FFFFFFF) % tab.length;
        }
        //在索引出插入一个新的节点
        Entry<K,V> e = tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        //容器中元素+1  ;  
        count++;
        return null;
    }
private int hash(Object k) {
        // hashSeed will be zero if alternative hashing is disabled.
        return hashSeed ^ k.hashCode();//在1.8的版本中，hash就直接为k.hashCode了。
    }

Процесс метода put таков: вычислить хэш-значение ключа, получить позицию индекса ключа в массиве таблиц по хэш-значению, а затем итерировать связанный список Entry по ключу (мы понимаем его как связанный list на данный момент), если в объекте связанного списка есть ключ этого ключа, то просто замените его значение value напрямую, в противном случае вставьте измененный узел ключ-значение в позицию индекса.

Когда программа пытается поместить пару ключ-значение в HashMap, программа сначала определяет место хранения Entry в соответствии с возвращаемым значением hashCode() ключа: если возвращаемое значение hashCode() Ключи двух записей одинаковы, то и место их хранения одинаковое. Если ключи этих двух Записей возвращают значение true при сравнении на равенство, значение вновь добавленной Записи перезапишет значение исходной Записи в коллекции, а ключ — нет. Если ключи этих двух Записей возвращают false при сравнении на равенство, вновь добавленная Запись образует цепочку Записей с исходной Записью в коллекции, а вновь добавленная Запись находится во главе цепочки Записей.

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

 public synchronized V get(Object key) {
//没有什么特殊性，就是加了一个synchronized，就是根据index来遍历索引处的单链表。
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

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

В операции расширения HashTable, в методе put, если вам нужно добавить элемент Entry в table[], сначала будет выполнена проверка емкости.Если емкость достигла порога, HashTable расширит емкость rehash()

protected void rehash() {  
        int oldCapacity = table.length;  
        //元素  
        Entry<K,V>[] oldMap = table;  
  
        //新容量=旧容量 * 2 + 1  
        int newCapacity = (oldCapacity << 1) + 1;  
        if (newCapacity - MAX_ARRAY_SIZE > 0) { 
        //这里的最大值和HashMap里的最大值不同，这里Max_ARRAY_SIZE的是
        因为有些虚拟机实现会限制数组的最大长度。 
            if (oldCapacity == MAX_ARRAY_SIZE)  
                return;  
            newCapacity = MAX_ARRAY_SIZE;  
        }  
          
        //新建一个size = newCapacity 的HashTable  
        Entry<K,V>[] newMap = new Entry[];  
  
        modCount++;  
        //重新计算阀值  
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);  
        //重新计算hashSeed  
        boolean rehash = initHashSeedAsNeeded(newCapacity);  
  
        table = newMap;  
        //将原来的元素拷贝到新的HashTable中  
        for (int i = oldCapacity ; i-- > 0 ;) {  
            for (Entry<K,V> old = oldMap[i] ; old != null ; ) {  
                Entry<K,V> e = old;  
                old = old.next;  
  
                if (rehash) {  
                    e.hash = hash(e.key);  
                }  
                int index = (e.hash & 0x7FFFFFFF) % newCapacity;  
                e.next = newMap[index];  
                newMap[index] = e;  
            }  
        }  
    }  

В этом методе rehash() мы видим, что емкость удваивается +1, и элементы исходной HashTable необходимо копировать в новую HashTable один за другим.Этот процесс занимает много времени, и hashSeed должен быть пересчитал., ведь емкость изменилась. : Например, начальное значение равно 11, а коэффициент загрузки по умолчанию равен 0,75, тогда пороговое значение = 8. Когда элемент в контейнере достигает 8, HashTable выполняет операцию расширения, емкость = 8 * 2 + 1 = 17, а пороговое значение = 17*0,75 = 13, когда элемент-контейнер снова достигает порогового значения, HashTable также выполняет операцию расширения и так далее.