A look at the implementation process of open addressing after hashing from TheadLocalMap

The hash table is an efficient and common data structure that can reduce the lookup time to O(1). It generates a hashcode value through the hash function, so as to perform a certain bit of data. Although the current hash function has been able to achieve good randomness, there are still conflicts, that is, different objects through the hash function calculation, generate the same Hashcode value. When a hash conflict occurs, it can be handled in the following ways:

  • Zipper method: Each hash table node has a next pointer. Multiple hash table nodes can use the next pointer to form a one-way linked list. Multiple nodes assigned to the same index can use this one-way linked list for storage.

    • Open addressing: Once a conflict occurs, look for the next empty hash address. As long as the hash table is large enough, the empty hash address will always be found and the record stored.
    • Rehash: also called double Hash, with multiple different Hash functions, using the second, third… . Wait for the hash function to compute the address until there is no conflict.

The zipper method can be implemented by looking at the source code of the HashMap, and when a single chain is too long, it automatically converts to a red-black tree structure, and when inserting a linked list, it needs to pay attention to whether it is inserted by head or tail.

Let’s start with ThreadLocal, which is an important thing that comes out of the source of the Thead class.

ThreadLocal.ThreadLocalMap threadLocals = null;
Copy the code

ThreadLocal contains the following methods and types

Threadlocal provides three public methods to operate on a thread: set, get, and remove. Threadlocal is an internal storage class that can store data in a specified thread. Once the data is stored, only the specified thread can get the stored data. ThreadLocal’s static inner class, ThreadLocalMap, maintains an array table for each Thread. ThreadLocal determines the subscript of the array by Thread, and that subscript is where the value is stored.

Starting with the initialization process, ThreadLocal is built lazily and is created only when there is data to put in.

ThreadLocalMap(ThreadLocal<? > firstKey, Object firstValue) { table =new Entry[INITIAL_CAPACITY];
            int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
            table[i] = new Entry(firstKey, firstValue);
            size = 1;
            setThreshold(INITIAL_CAPACITY);
        }
Copy the code

The implementation of the set method, which uses hashCode to calculate that the index position I already has a value, will start at I and continue to search through +1 until it finds an empty index position, and will insert the current ThreadLocal as the key.

private void set(ThreadLocal
        key, Object value) {
						// Get the current array and length
            Entry[] tab = table;
            int len = tab.length;
            // Hash the subscript location to store
            int i = key.threadLocalHashCode & (len-1);
						// Consider hash conflicts. If the current coordinate already has data, call nextIndex to get the next location
            for(Entry e = tab[i]; e ! =null; e = tab[i = nextIndex(i, len)]) { ThreadLocal<? > k = e.get();if (k == key) {
                    e.value = value;
                    return;
                }

                if (k == null) {
                    replaceStaleEntry(key, value, i);
                    return; }}// Finally find the new empty position
            tab[i] = new Entry(key, value);
            int sz = ++size;
            if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }private static int nextIndex(int i, int len) {
        	// Determine if the next position exceeds the array length, if so, start at 0
            return ((i + 1 < len) ? i + 1 : 0);
        }
Copy the code

Because of the special nature of the set method, the get method also needs to be changed a bit

private Entry getEntry(ThreadLocal
        key) {
						// Compute the subscript of the storage
            int i = key.threadLocalHashCode & (table.length - 1);
            Entry e = table[i];
            // If the key of the current subscript position is the same as the key of the query, it is returned directly
            if(e ! =null && e.get() == key)
                return e;
            else
            		// If the key is different, there is a conflict and you need to search down
                return getEntryAfterMiss(key, i, e);
        }
        
private Entry getEntryAfterMiss(ThreadLocal<? > key,int i, Entry e) {
            Entry[] tab = table;
            int len = tab.length;
						// always find e is not empty
            while(e ! =null) { ThreadLocal<? > k = e.get();if (k == key)
                    return e;
                if (k == null)
                		// Handle the node whose key is null
                    expungeStaleEntry(i);
                else
                		/ / increase the I
                    i = nextIndex(i, len);
                e = tab[i];
            }
            return null;
        }
        

Copy the code

Both ThreadLocal and Synchronized are designed to solve access conflicts for the same variable in multiple threads

  • Synchronized resolves access conflicts by sacrificing time through thread waiting
  • In addition, compared with Synchronized, ThreadLocal has the effect of thread isolation. Only the corresponding value can be obtained within the thread, and the desired value cannot be accessed outside the thread.

The thread-isolation nature of ThreadLocal makes it a relatively special application scenario. Consider using ThreadLocal when some data is thread-scoped and different threads have different copies of the data.