Blog: bugstack.cn

Precipitation, share, grow, let yourself and others can gain something! 😄

One, foreword

After all, can you really build a rocket?

It is often said that the interview builds the rocket and the induction turns the screw. But do you really have the ability to build rockets? Most of them are self-mockery of their knowledge blind spots, technical bottlenecks and inexperience.

During the interview:

  • I hope you understand data structures, because you’ll be much more comfortable with HashMap, ArrayList, and LinkedList.
  • I hope you know hashing algorithms, because then you’ll have a lot of choices when you’re designing routes;Division and hash,Square hash,The Fibonacci hash methodAnd so on.
  • I hope you know the open source code, because this way you can quickly locate problems and possibly create some middleware for system services to better decouple the system.
  • I hope you understand design patterns, because that way you can write scalable, maintainable programs that will make the whole team better.

So, CRUD never chose you, nor did screw making make you a tool man. It’s your technical ability that determines your vision, and that vision determines the code you write!

2. Interview questions

Thank the plane, remember the plane has not got the offer, got up early, ate two fried dough sticks, and went to the company to find the interviewer for lessons!

Interviewer: Aeroplane, listen to tank said, you recently love to get up early study ah.

Thank plane: HMMMM, yes, recently the hair all quick drop didn’t!

Interviewer: So today we’re going to talk about ThreadLocal. What kind of situations can it be used in?

Xj: Well, ThreadLocal provides thread-local variables, so it’s usually used in full-link monitoring, or in components like MDC.

Interviewer: Nice flight. I’ve really studied recently. Do you know what a ThreadLocal data structure is? What hash does it use?

Xie Plane: array? Well, why the hash is not clear…

Interviewer: So ThreadLocal has a memory leak risk. How does that happen? Also, do you know about exploratory and heuristic cleaning in this process?

Thank plane: this… Blind spot, blind spot, COKE I put on the table, I go home to read a book!

3. ThreadLocal analysis

ThreadLocal by Josh Bloch and Doug Lea 👍

This is an obscure class that is not used very often, if only for daily business development. And the method it provides is very simple, with only a few lines of code per function. However, if you dig deep into the source code of the implementation part, you will find that things are not so simple. There are too many knowledge points involved, including; Data structures, open addressing, Fibonacci hashed, the magic of 0x61C88647, weak Reference, stale key detection cleanup, heuristic cleanup, and more.

Next, we will learn these blind spots step by step. This article involves more code and practice verification drawings, welcome to pay attention to the public number: bugStack wormhole stack, reply to download a link to open, find ID: 19🤫 get! *

1. Application scenarios

1.1 SimpleDateFormat

private SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public void seckillSku(a){
    String dateStr = f.format(new Date());
    // Business process
}
Copy the code

Have you ever written code like this? If you’re still doing this, you’re making a thread-safe mistake. SimpleDateFormat is not a thread-safe class.

1.1.1 Thread Unsafe Verification
private static SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");

public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = f.format(new Date());
            try {
                Date parseDate = f.parse(dateStr);
                String dateStrCheck = f.format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if(! equals) { System.out.println(equals +"" + dateStr + "" + dateStrCheck);
                } else{ System.out.println(equals); }}catch(ParseException e) { System.out.println(e.getMessage()); } }).start(); }}Copy the code

This is a multithreaded validation code for SimpleDateFormat. Prove thread unsafe when equals is false. The running results are as follows;

true
true
false 2020- 09 -23 11:40:42 2230- 09 -23 11:40:42
true
true
false 2020- 09 -23 11:40:42 2020- 09 -23 11:40:00
false 2020- 09 -23 11:40:42 2020- 09 -23 11:40:00
false 2020- 09 -23 11:40:00 2020- 09 -23 11:40:42
true
false 2020- 09 -23 11:40:42 2020- 08 -31 11:40:42
true
Copy the code
1.1.2 Optimization with ThreadLocal

The most direct way for thread safety is to call new SimpleDateFormat directly on each call. But that’s not the best approach, so we’ll use ThreadLocal to optimize this code.

private static ThreadLocal<SimpleDateFormat> threadLocal = ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"));
public static void main(String[] args) {
    while (true) {
        new Thread(() -> {
            String dateStr = threadLocal.get().format(new Date());
            try {
                Date parseDate = threadLocal.get().parse(dateStr);
                String dateStrCheck = threadLocal.get().format(parseDate);
                boolean equals = dateStr.equals(dateStrCheck);
                if(! equals) { System.out.println(equals +"" + dateStr + "" + dateStrCheck);
                } else{ System.out.println(equals); }}catch(ParseException e) { System.out.println(e.getMessage()); } }).start(); }}Copy the code

We put SimpleDateFormat in a ThreadLocal, so we don’t have to repeat new objects, and we don’t have to be thread-safe. The test results are as follows;

true
true
true
true
true
true
true.Copy the code

1.2 Link Tracing

In recent years, based on The Google Dapper paper to achieve non-invasive full link tracking, the use of more and more widely. Simply put, this is a monitoring system, but you do not need to hard-code the way of monitoring methods, but based on its design scheme using JavaAgent + bytecode staking, dynamic collection of method execution information. If you want to learn about bytecode staking, you can read my bytecode programming column: bugstack.cn/itstack-dem…

Key, dynamic collection of method execution information. This is the main part, which is related to ThreadLocal. Bytecode staking addresses non-invasive programming, so during a service invocation, calls of multiple methods between systems and within the system need to be collected. In this case, the ThreadLocal method is used to record the execution ID. There are also cross-thread calls using an enhanced version of ThreadLocal, but the basic principle remains the same.

1.2.1 Trace code

Here is an example of full link method call chain trace, part of the code

public class TrackContext {

    private static final ThreadLocal<String> trackLocal = new ThreadLocal<>();

    public static void clear(a){
        trackLocal.remove();
    }

    public static String getLinkId(a){
        return trackLocal.get();
    }

    public static void setLinkId(String linkId){ trackLocal.set(linkId); }}Copy the code
@Advice.OnMethodEnter()
public static void enter(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span currentSpan = TrackManager.getCurrentSpan();
    if (null == currentSpan) {
        String linkId = UUID.randomUUID().toString();
        TrackContext.setLinkId(linkId);
    }
    TrackManager.createEntrySpan();
}

@Advice.OnMethodExit()
public static void exit(@Advice.Origin("#t") String className, @Advice.Origin("#m") String methodName) {
    Span exitSpan = TrackManager.getExitSpan();
    if (null == exitSpan) return;
    System.out.println("Link Tracing (MQ) :" + exitSpan.getLinkId() + "" + className + "." + methodName + "Time:" + (System.currentTimeMillis() - exitSpan.getEnterTime().getTime()) + "ms");
}
Copy the code
  • The above part is the process of link tracing in non-intrusion monitoring. Specific cases and codes can be refer to the series of special articles “JavaAgent-based full link Monitoring”.
  • This is just one implementation, bytecode staking usesbyte-buddy, actually use,ASMorJavassist.
1.2.2 Test results

The test method

Configuration parameters: – javaagent:E:\itstack\GIT\itstack.org \ itstack – demo – agent \ itstack – demo – agent – 06 \ target \ itstack – demo – agent – 06-1.0.0 – SNAPSH OT.jar=testargs

public void http_lt1(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println("Test result: HI1" + name);
    http_lt2(name);
}

public void http_lt2(String name) {
    try {
        Thread.sleep((long) (Math.random() * 500));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println("Test result: HI2" + name);
    http_lt3(name);
}
Copy the code

The results

OnTransformation:class org.itstack.demo.test.ApiTestTest results:hi2Results of wukong Test:hi3Wukong Link Tracking (MQ) : 90c7d543-c7b84 -ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt3Time: 104ms

init: 256MB	 max: 3614MB	 used44:MB	 committed: 245MB	 use rate: 18%
init: 2MB	 max: 0MB	 used13:MB	 committed14:MB	 use rate: 95%

name: PS Scavenge	 count: 0took: 0pool name: [PS Eden Space.PS Survivor Space]
name: PS MarkSweep	 count: 0took: 0pool name: [PS Eden Space.PS Survivor Space.PS Old Gen] -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- link tracking (MQ) : 90c7d543-c7b84 -ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt2Time: 233ms

init: 256MB	 max: 3614MB	 used44:MB	 committed: 245MB	 use rate: 18%
init: 2MB	 max: 0MB	 used13:MB	 committed14:MB	 use rate: 96%

name: PS Scavenge	 count: 0took: 0pool name: [PS Eden Space.PS Survivor Space]
name: PS MarkSweep	 count: 0took: 0pool name: [PS Eden Space.PS Survivor Space.PS Old Gen]
Copy the code
  • The above is the test result of link tracing. It can be seen that both methods will print the corresponding coding ID:90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 .
  • This is the core application of full link tracing, and you can also see that some simple JVM monitoring metrics for the system are printed here as part of the monitoring.

Anything else that requires active method invocation chains, such as the MDC logging framework, needs to use ThreadLocal. Let’s take a closer look at the implementation of ThreadLocal.

2. Data structure

Before you understand a feature, understand its data structure. This is equivalent to looking at its foundation first, with this fundamental is easy to understand later. Here is a simple use of ThreadLocal and some of the source code.

New ThreadLocal<String>().set();

private void set(ThreadLocal
        key, Object value) {
   
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    
 	for(Entry e = tab[i]; e ! =null;
                 e = tab[i = nextIndex(i, len)]) {
    ...
}
Copy the code

As you can see from the source code, ThreadLocal uses an array structure to store data and hash values to calculate subscripts, which means that it is an array structure of hash table, as shown in the following figure.

As shown in the figure above, the underlying data structure of ThreadLocal stores data, including knowledge points as follows.

  1. It’s an array structure.
  2. EntrySo instead of opening it again, it’s actually a weak reference implementation,static class Entry extends WeakReference<ThreadLocal<? >>. This means that as long as no strong reference exists, GC will be garbage collected when it occurs.
  3. Data elements are stored hashed, but the hash here usesThe Fibonacci hash method, will be analyzed in detail later.
  4. In addition, unlike the data structure of HashMap, hash collisions are not stored as linked lists or red-black trees, but are stored using open addressing. That is, when the same subscript position conflicts, then+1 addresses backwardsUntil an empty location or garbage collection location is found for storage.

3. Hash algorithm

Since ThreadLocal is an open addressing storage based on an array structure, there must be a hash calculation. However, when we look at the source code, we see that this hash is not the same as the hash of the array index in the HashMap. If you forget HashMap, check out the HashMap source code analysis, Insert, Find, HashMap Perturbation Functions, Load Factors

3.1 Mysterious Number 0x61C88647

When we look at the ThreadLocal setting element, we have code that evaluates the hash value;

private static final int HASH_INCREMENT = 0x61c88647;

private static int nextHashCode(a) {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}
Copy the code

So you’re going to look at this and you’re going to say, well, what’s the way to compute a hash? Where did you get this number?

At this point, actually, the way to compute a hash is not just the way we normally see strings get hashes, but also the way; Division hashing, square hashing, Fibonacci hashing, random number, etc.

ThreadLocal uses Fibonacci hash + open addressing to store data into array structures. The Fibonacci sequence is used to make the data more hashed and less hashed. Specifically from the calculation of the mathematical formula, formula: F (k) = ((K * 2654435769) >> X) << Y for the common 32-bit integer, that is, F (k) = (K * 2654435769) >> 28

The second question, where does the number 0x61C88647 come from?

This is actually the golden ratio of a hash value, 0.618. Do you remember the math you studied? The calculation method is as follows;

// Golden partition point: (√ 5-1) / 2 = 0.6180339887 1.618:1 == 1:0.618
System.out.println(BigDecimal.valueOf(Math.pow(2.32) * 0.6180339887).intValue());      / / - 1640531527
Copy the code
  • If you’ve ever taken math, the golden ratio is,Square root of 5 minus 1 over 2And take the 10-digit approximation0.6180339887.
  • Then use 2 ^ 32 * 0.6180339887 to get the result:- 1640531527.In hexadecimal 0x61C88647.So that’s where this number came from

3.2 Verifying hashes

Now, Josh Bloch and Doug Lea, the two guys, chose to use the Fibonacci sequence to compute hashes. There must be something special about it, which is better hashing, fewer hash collisions.

Next we in accordance with the source code to obtain hash value and calculation of the subscript, put this part of the code out to do verification.

3.2.1 Partial source code
private static AtomicInteger nextHashCode = new AtomicInteger();
 
private static final int HASH_INCREMENT = 0x61c88647;

// Compute the hash
private static int nextHashCode(a) {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}

// get the subscript
int i = key.threadLocalHashCode & (len-1);
Copy the code

As mentioned above, the source section uses AtomicInteger, the atomic method for calculating subscripts. We don’t need to be thread-safe, just simple implementation. Additionally, ThreadLocal initializes an array length of 16, which we also initialize.

3.2.2 Unit tests
@Test
public void test_idx(a) {
    int hashCode = 0;
    for (int i = 0; i < 16; i++) {
        hashCode = i * HASH_INCREMENT + HASH_INCREMENT;
        int idx = hashCode & 15;
        System.out.println("Fibonacci hash:" + idx + "Ordinary hash:" + (String.valueOf(i).hashCode() & 15)); }}Copy the code

In the test code part, Fibonacci sequence is used, and ordinary hashing algorithm is added to compare the hashing effect. Of course the String hash is not perturbed as it is in the HashMap

Test results:

Fibonacci hash:7Ordinary hash:0Fibonacci hash:14Ordinary hash:1Fibonacci hash:5Ordinary hash:2Fibonacci hash:12Ordinary hash:3Fibonacci hash:3Ordinary hash:4Fibonacci hash:10Ordinary hash:5Fibonacci hash:1Ordinary hash:6Fibonacci hash:8Ordinary hash:7Fibonacci hash:15Ordinary hash:8Fibonacci hash:6Ordinary hash:9Fibonacci hash:13Ordinary hash:15Fibonacci hash:4Ordinary hash:0Fibonacci hash:11Ordinary hash:1Fibonacci hash:2Ordinary hash:2Fibonacci hash:9Ordinary hash:3Fibonacci hash:0Ordinary hash:4

Process finished with exit code 0
Copy the code

Found no? Fibonacci hashes are very uniform and normal hashes up to 15 have been developed to produce collisions. This is the beauty of Fibonacci hashes, which reduce collisions so that the data store is more distributed and the time to get the data is roughly O(1).

4. Source code interpretation

4.1 the initialization

new ThreadLocal<>()

The initialization process is also simple, and you can set it up to suit your needs. But one thing that’s really important in the ThreadLocal source code is getting the hash value of a ThreadLocal, threadLocalHashCode.

private final int threadLocalHashCode = nextHashCode();

/** * Returns the next hash code. */
private static int nextHashCode(a) {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
}
Copy the code

If a ThreadLocal is instantiated, a hash value will be obtained.

@Test
public void test_threadLocalHashCode(a) throws Exception {
    for (int i = 0; i < 5; i++) {
        ThreadLocal<Object> objectThreadLocal = new ThreadLocal<>();
        Field threadLocalHashCode = objectThreadLocal.getClass().getDeclaredField("threadLocalHashCode");
        threadLocalHashCode.setAccessible(true);
        System.out.println("objectThreadLocal："+ threadLocalHashCode.get(objectThreadLocal)); }}Copy the code

Since threadLocalHashCode is a private property, we instantiate it to get the hash value as above.

ObjectThreadLocal: -1401181199ObjectThreadLocal:239350328ObjectThreadLocal:1879881855ObjectThreadLocal: -774553914ObjectThreadLocal:865977613

Process finished with exit code 0
Copy the code

Fetching this value is what computs ThreadLocalMap, the array subscript of ThreadLocal when storing data. As long as it is the same object, when set, get, you can set and get the corresponding value.

4.2 Setting Elements

4.2.1 Process diagram

New ThreadLocal<>().set(" ThreadLocal ");

The method that sets the element is just one line of code. But the process of setting elements involves more, before the detailed analysis of the code, we first look at a flowchart of setting elements, from the figure to understand the process of different situations and then compare to learn the source code. The flow chart is as follows;

At first glance, it may feel a little dizzy, but from left to right, we have the following knowledge points; 0. In the middle is the array structure of ThreadLocal, after which the element is set in four different cases, and the element insertion is stored by Fibonacci hash calculation of the underlying value.

  1. Case 1, the index to be inserted, is empty and inserted directly.
  2. Case 2, insert subscript, not null, same key, update directly
  3. Case 3, subscript to be inserted, not null, different key, open addressing
  4. Case 4, not empty, different key, hit an expired key. In fact, case 4 is what happens when a weak reference GC occurs. In a situation like this,ThreadLocalIt will detect and clean expired keys, which will be explained later.
4.2.2 Source code analysis
private void set(ThreadLocal
        key, Object value) {
    Entry[] tab = table;
    int len = tab.length;
    int i = key.threadLocalHashCode & (len-1);
    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;
        }
    }
    tab[i] = new Entry(key, value);
    int sz = ++size;
    if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash(); }Copy the code

With the flow diagram above, it is easier to look at the code section, which includes the following;

  1. key.threadLocalHashCode & (len-1);Fibonacci hash computes array subscripts.
  2. EntryIs an implementation class of weakly referenced objects,static class Entry extends WeakReference<ThreadLocal<? >>, so in the absence of a strong external reference, GC occurs and the key is deleted.
  3. The for loop checks if the element exists and sets the element if the current subscript does nottab[i] = new Entry(key, value);.
  4. If the element exists, the key is determined to be equalif (k == key), the value is updated if the value is equal.
  5. If it’s not equal, it’s oursreplaceStaleEntry, which is the probe cleaning of expired elements mentioned above.

To sum up, is the entire process of element storage, the overall structure design is very good 👍, the great use of hash effect, but also the use of weak references very 6!

4.3 Capacity Expansion Mechanism

4.3.1 Capacity Expansion Conditions

Whenever you use an array structure, there's always going to be expansion

if(! cleanSomeSlots(i, sz) && sz >= threshold) rehash();Copy the code

When we read the Settings element, we have this piece of code to determine whether to expand.

  • First, proceedHeuristic cleaning *cleanSomeSlots*, remove the expired elements and see if the space is
  • After that, judgesz >= threshold, includingthreshold = len * 2 / 3That is, the number of elements in the array filled by day is greater thanlen * 2 / 3, need to expand the capacity.
  • And finally, which is the focus of our analysis,rehash();To recalculate the location of elements.
4.3.2 Source code analysis

Exploratory cleaning and validation

private void rehash(a) {
    expungeStaleEntries();
    
    // Use lower threshold for doubling to avoid hysteresis
    if (size >= threshold - threshold / 4)
        resize();
}

private void expungeStaleEntries(a) {
    Entry[] tab = table;
    int len = tab.length;
    for (int j = 0; j < len; j++) {
        Entry e = tab[j];
        if(e ! =null && e.get() == null) expungeStaleEntry(j); }}Copy the code
  • This part is mainly about probing to clear expired elements and judging whether the conditions for expansion are met after clearing, size >= threshold * 3/4
  • The core operation after capacity expansion is to recalculate the hash value and fill the elements into the new array.

Rehash () expansion

private void resize(a) {
    Entry[] oldTab = table;
    int oldLen = oldTab.length;
    int newLen = oldLen * 2;
    Entry[] newTab = new Entry[newLen];
    int count = 0;
    for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if(e ! =null) { ThreadLocal<? > k = e.get();if (k == null) {
                e.value = null; // Help the GC
            } else {
                int h = k.threadLocalHashCode & (newLen - 1);
                while(newTab[h] ! =null)
                    h = nextIndex(h, newLen);
                newTab[h] = e;
                count++;
            }
        }
    }
    setThreshold(newLen);
    size = count;
    table = newTab;
}
Copy the code

Above, the code is the overall operation of capacity expansion, including the following steps;

  1. I’m going to double the size of the array,oldLen * 2Instantiate the new array.
  2. Iterate over for, all the elements in the old array, put them back in the new array.
  3. If a hash collision occurs during array placement, the chain method continues.
  4. There is also a key detection operationif (k == null), convenient GC.

4.4 Obtaining Elements

4.4.1 Process Diagram

new ThreadLocal<>().get();

Similarly, the acquisition of elements is just such a line of code, if you do not analyze the source code before, can you consider it in different data structures, when the acquisition of elements do. Let’s take a look at the figure below, which is divided into the following situations;

According to different data element storage conditions, including the following conditions;

  1. Directly to, no hash conflict, just return the element.
  2. Not directly located, the key is different, open addressing search.
  3. Not directly located, the key is different, open addressing search, encountered GC clean element, need to probe clean, then find the element.
4.4.2 Source code analysis
private Entry getEntry(ThreadLocal
        key) {
    int i = key.threadLocalHashCode & (table.length - 1);
    Entry e = table[i];
    if(e ! =null && e.get() == key)
        return e;
    else
        return getEntryAfterMiss(key, i, e);
}

private Entry getEntryAfterMiss(ThreadLocal<? > key,int i, Entry e) {
    Entry[] tab = table;
    int len = tab.length;
    while(e ! =null) { ThreadLocal<? > k = e.get();if (k == key)
            return e;
        if (k == null)
            expungeStaleEntry(i);
        else
            i = nextIndex(i, len);
        e = tab[i];
    }
    return null;
}
Copy the code

Ok, so this is the source code for getting elements, which is the same as the ones listed in our diagram. ExpungeStaleEntry: if a key == null element is found, the expungeStaleEntry will clean up the expired element and move the element in the subsequent position forward.

4.5 Element Clearing

4.5.1 Probing Clearing [expungeStaleEntry]

Exploratory cleaning, which starts with the currently encountered GC elements and continues backward. Rehash is not stopped until NULL is encountered.

expungeStaleEntry

private int expungeStaleEntry(int staleSlot) {
    Entry[] tab = table;
    int len = tab.length;
    // expunge entry at staleSlot
    tab[staleSlot].value = null;
    tab[staleSlot] = null;
    size--;
    // Rehash until we encounter null
    Entry e;
    int i;
    for(i = nextIndex(staleSlot, len); (e = tab[i]) ! =null; i = nextIndex(i, len)) { ThreadLocal<? > k = e.get();if (k == null) {
            e.value = null;
            tab[i] = null;
            size--;
        } else {
            int h = k.threadLocalHashCode & (len - 1);
            if(h ! = i) { tab[i] =null;
                // Unlike Knuth 6.4 Algorithm R, we must scan until
                // null because multiple entries could have been stale.
                while(tab[h] ! =null) h = nextIndex(h, len); tab[h] = e; }}}return i;
}
Copy the code

Above, exploratory cleaning is used in fetching elements; new ThreadLocal<>().get() -> map.getEntry(this) -> getEntryAfterMiss(key, i, e) -> expungeStaleEntry(i)

4.5.2 Heuristic Cleaning [cleanSomeSlots]
Heuristically scan some cells looking for stale entries.
This is invoked when either a new element is added, or
another stale one has been expunged. It performs a
logarithmic number of scans, as a balance between no
scanning (fast but retains garbage) and a number of scans
proportional to number of elements, that would find all
garbage but would cause some insertions to take O(n) time.
Copy the code

Heuristic cleaning, there’s a comment that says something like; Tentatively scan some cells for expired elements, that is, elements that have been garbage collected. This function is called when a new element is added or another obsolete element is removed. It performs logarithmic scans as a balance between no scans (fast but garbage preserved) and scans proportional to the number of elements, which will find all garbage but result in some inserts that take O (n) time.

private boolean cleanSomeSlots(int i, int n) {
    boolean removed = false;
    Entry[] tab = table;
    int len = tab.length;
    do {
        i = nextIndex(i, len);
        Entry e = tab[i];
        if(e ! =null && e.get() == null) {
            n = len;
            removed = true; i = expungeStaleEntry(i); }}while ( (n >>>= 1) != 0);
    return removed;
}
Copy the code

The while loop constantly moves right to find expired elements that need to be cleaned up, and is eventually processed using expungeStaleEntry, which includes the shift of the element.

Four,

  • So this is kind of aThreadLocalThe corner of the knowledge point is analyzedThreadLocalThere are more in the familyNettyIs used in,FastThreadLocal. Get call links across service threads at full link, andTransmittableThreadLocalThere is also a thread delivery solution that comes with the JDK itselfInheritableThreadLocal. But standing on the basis of this article, understand the most basic principle, in understanding other extension design, it is easier to accept.
  • In addition, probing cleaning is often seen in our analysis, which is also very time-consuming. This is important to remember when using ThreadLocalnew ThreadLocal<>().remove();Operation. Avoid memory leaks after weak reference GC occurs.
  • Finally, did you find it?! We learn such fundamental knowledge, are inseparable from the data structure and good design scheme, or the figure of the algorithm. This code is the foundation on which the whole system works, and if we can extract some ideas into the core business processes that we develop, we can greatly improve performance.

Five, series recommendation

  • Hold the grass! You poisoned the code!
  • A code review, almost failed the trial period!
  • Core knowledge of HashMap, disturbance function, load factor, expansion linked list resolution, deep learning
  • HashMap data insertion, search, delete, traverse, source code analysis
  • Relearning Java Design Patterns (22 Real Life Development Scenarios)