What is the difference between HashMap and HashTable in java? Simple comparison of HashMap and HashTable

What this article brings to you is what is the difference between HashMap and HashTable in Java? A simple comparison of HashMap and HashTable. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. First, let’s take a look at the inheritance structure:

HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

Hashtable

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

1. First, through the name, we can see that HashMap conforms to camel case naming. Rules, Hashtable does not comply with the camel case naming rules. Through the inheritance structure, we find that HashMap inherits from AbstractMap, and Hashtable inherits from Dictionnary. Dictionary is an abandoned class, and all Hashtables are generally not recommended. , the synchronization container ConcurrentHashMap class can be used in a multi-threaded environment.

2. It can be found through the attributes of the class that in jdk1.8, when the number of nodes stored in a chain in the HashMap is greater than or equal to 8 and the length of the linked list array is greater than 64, it is converted into a red-black tree, and Hashtable does not convert to red-black tree.

3. Hashtable’s put() and HashMap’s put()

Hashtable’s put operation:

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

The method in Hashtable adds the synchronized keyword, so it is A synchronized method.

Through if (value == null) throw new NullPointerException();} we can see that it does not allow the value of value to be empty, and when the key is null, calling key.hashCode(); will throw The null pointer is abnormal, so the key and value in the Entry stored in the Hashtable cannot be empty. In addition, Hashtable obtains the subscript of the linked list through the % operation.

Look at HashMap below

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

You can see that the key in HashMap can have a null. When the key is null, its hash value is 0, and the method of HashMap to obtain the subscript of the linked list array is the same as Hashtable Different, it is calculated using (n-1)&hash, because the length of the array linked list of HashMap is 2 to the nth power.

Summary: The key in HashMap can have one null, the value can have multiple nulls, and the key and value in Hashtable cannot be empty. The methods of positioning the chain are different. HashMap obtains the subscript through the & operation, while Hashtable obtains the subscript through %, and the & operation is faster.

4. HashMap and Hashtable have different expansion methods.

Hashtable expansion:

 @SuppressWarnings("unchecked")
    protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // overflow-conscious code
        int newCapacity = (oldCapacity << 1) + 1;
        //MAX_ARRAY_SIZE = int的最大值-8
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
        
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;
		//从链表数组尾到头遍历
        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;
            }
        }
    }

Through the source code, we found that the maximum length of the Hashtable linked list array is the maximum value of the int type -8. The expansion of the Hashtable will double the original length plus 1, and After expansion, the linked list needs to be repositioned. Moreover, after the expansion, the order of the array linked list becomes the reverse order of the original order.

HashMap expansion:

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果远链表数组长度大于零
        if (oldCap > 0) {
            //如果原长度大于或等于MAXIMUM_CAPACITY(2^30)，则将threshold(闸值)设为Integer.MAX_VALUE大约为MAXIMUM_CAPACITY(2^30)的二倍
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //让新的容量变为旧的二倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                 //新的闸值也变为原来的二倍
                newThr = oldThr << 1; // double threshold
        }
        //老的链表数组长度小于等于0，老的闸值大于零，这种情况是初始化时传入一个map导致的构造器为public HashMap(Map<? extends K, ? extends V> m)
        else if (oldThr > 0) // initial capacity was placed in threshold
        	//让新的容量等于旧的闸值
            newCap = oldThr;
         //下面的else是默认的构造器，即public HashMap()
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //新的闸值为零时（也就是(newCap = oldCap << 1) >= MAXIMUM_CAPACITY的情况），这时需要赋予newThr正确的值。
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;   //闸值=链表数组长度*加载因子。
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //扩容，如果原来的链表数组中有数据，就复杂到table中
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //遍历老的链表数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //当oldTab[j]这条链不为空时
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //如果这条链只有首节点有数据，把它添加进新链表数组中
                    if (e.next == null)
                        //因为数组的容量时2的n次方，所以使用hash&(newCap-1)来计算出在那条链中。
                        newTab[e.hash & (newCap - 1)] = e;
                     //如果老的链在红黑树中，使用split()方法来复制
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //当前链中不只只有一个链表头数据时，遍历链表来复制
                    else { // preserve order
                        //数据的复制有两种情况，第一种是原位置不变，第二种是位置改变
         				loHead代表和原链相同位置的链，hiHead代表是原链加上原容量的链，因为扩容后长度为原长度的二倍，一个链中的节点要不在原位置的链中，要么在原位置加原容量的链中
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //通过e.hash和oldCap进行&运算来得出位置是否需要改变。
                            比如原数组容量为16（10000）和hash值进行&运算，如果高位1未参加运算，则为0即位置不变，如果高位参加了运算值不等于0,需要改变位置。
                           
                        
                            //loHead和hiHead分别代表原位置的链和新位置的链
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            //原位置为j
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //新位置为j+oldCap
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

You can see that the expansion capacity of HashMap has doubled, and it does not need to reposition the linked list, because the expanded position is either at the original position or at the original position. The original capacity of the position can be determined by ANDing the hash and the length of the linked list array. If the high bits of the array length participate in the calculation, the original capacity will be at the original position. If the high bits of the array length do not participate in the calculation, the original capacity will be at the original position. Moreover, the order of linked list data remains unchanged after HashMap is expanded.

5. The initial capacities of HashMap and Hashtable are different.
The initial capacity of Hashtable is 11, and the initial capacity of HashMap is 16.

The above is the detailed content of What is the difference between HashMap and HashTable in java? Simple comparison of HashMap and HashTable. For more information, please follow other related articles on the PHP Chinese website!