Hashtable source code analysis, collections Synchronizedmap parsing

One 、 Class inheritance diagram

Two 、HashTable Introduce

HashTable The operation of is almost the same as HashMap Agreement , The main difference is this HashTable For multithreading safety , Add... To almost all methods synchronized lock , And the result of locking is HashTable The efficiency of operation is very low .

Not recommended HashTable,Oracle The official also abandoned it , It is recommended to use... In a multithreaded environment ConcurrentHashMap class .

3、 ... and 、HashTable and HashMap Comparison of

1. Thread safety

HashMap Is a thread unsafe class , Multithreading can cause concurrency conflicts , But it is more efficient under single thread ;HashTable Is a thread safe class , Many methods use synchronized modification , But at the same time, locking leads to low concurrency efficiency , Single threaded environments are also very inefficient ;

2. Insert null

HashMap Allowed keys are null, The value is null; but HashTable A key or value of... Is not allowed null;

3. Capacity

HashMap The length of the underlying array must be 2 The power of , This is for the sake of hash Get ready , The default is 16; and HashTable The length of the underlying array can be any value , That's what happened hash Algorithm scattering nonuniformity , Easy to cause hash Conflict , The default is 11;

   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 = new Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    }

    /**
     * Constructs a new, empty hashtable with the specified initial capacity
     * and default load factor (0.75).
     *
     * @param     initialCapacity   the initial capacity of the hashtable.
     * @exception IllegalArgumentException if the initial capacity is less
     *              than zero.
     */
    public Hashtable(int initialCapacity) {
        this(initialCapacity, 0.75f);
    }

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    public Hashtable() {
        this(11, 0.75f);
    }

    /**
     * Constructs a new hashtable with the same mappings as the given
     * Map.  The hashtable is created with an initial capacity sufficient to
     * hold the mappings in the given Map and a default load factor (0.75).
     *
     * @param t the map whose mappings are to be placed in this map.
     * @throws NullPointerException if the specified map is null.
     * @since   1.2
     */
    public Hashtable(Map<? extends K, ? extends V> t) {
        this(Math.max(2*t.size(), 11), 0.75f);
        putAll(t);
    }

4.Hash mapping

HashMap Of hash The algorithm is designed through unconventional methods , Put the bottom layer table The length is designed as 2 The power of , Use bitwise and operations instead of modulo operations , Reduce computing consumption ; and HashTable Of hash The algorithm first makes hash Value is less than the maximum value of an integer , Then the scattering operation is carried out by taking the module ;

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

5. Expansion mechanism

HashMap Create one for the original 2 Array of times , Then the original array is traversed and the position is calculated again by bit operation , Whether it is a red black tree or a linked list , First, the tail insertion method is adopted to divide into two chains , Then the number of chains can be used to determine whether it is a tree or a linked list （ It's just a way of TreeNode become Node, Because after the red black tree is divided into two chains, it is actually TreeNode The list of components ）;HashTable Expansion will create an original length 2 Array of times + 1, Then traverse the original array and rehash, The first interpolation ;

hashTable Expansion of :

int newCapacity = (oldCapacity << 1) + 1;

hashTable The head insertion method of :

        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;
            }
        }

6. Structural differences

HashMap It's made up of arrays + The linked list forms , stay JDK1.8 After that, the length of the linked list is greater than 8 It turns into a red black tree ; and HashTable It's always an array + Linked list ;

Four 、Collections.synchronizedMap analysis

1.Collections.synchronizedMap How to realize thread safety

(1). call Collections.synchronizedMap It's actually for Map The packaging became SynchronizedMap

    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
        return new SynchronizedMap<>(m);
    }

(2).SynchronizedMap Source code

First look at the properties ：

        private final Map<K,V> m;     // Backing Map
        final Object      mutex;        // Object on which to synchronize

Let's look at the construction method :

        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }

        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }

By construction method , hold map Come in , If you don't pass Object mutex Parameters ,mutex Namely this

Let's take a look at how to implement thread safety :

        public int size() {
            synchronized (mutex) {return m.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return m.isEmpty();}
        }
        public boolean containsKey(Object key) {
            synchronized (mutex) {return m.containsKey(key);}
        }
        public boolean containsValue(Object value) {
            synchronized (mutex) {return m.containsValue(value);}
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }

        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
        public void putAll(Map<? extends K, ? extends V> map) {
            synchronized (mutex) {m.putAll(map);}
        }
        public void clear() {
            synchronized (mutex) {m.clear();}
        }

Discover almost all operations Map Code for , All the mutex As a lock , After obtaining the lock, operate Map.

This and HashTable The granularity of the whole method of direct locking is about the same , Not recommended , Recommended ConcurrentHashMap