当前位置:网站首页>Interviewers, ThreadLocal if you ask me that, I'll hang up! "
Interviewers, ThreadLocal if you ask me that, I'll hang up! "
2020-11-06 01:23:11 【Bugstack wormhole stack】
author : Little brother Fu
Blog :https://bugstack.cn
precipitation 、 Share 、 grow up , Let yourself and others have something to gain !
One 、 Preface
At the end of the day , Do you really know how to build rockets ?
It's often said that interviews make rockets , Screw in . But do you really have the ability to build rockets , Most of them are self mockery that they dare not admit their knowledge blind areas, technical bottlenecks and lack of experience .
During the interview :
- I hope you understand data structure , Because you're using HashMap、ArrayList、LinkedList, More handy .
- I hope you understand hashing , Because then when you design the route , There will be a lot of choices ;
division method
、Square hash
、Fibonacci (Fibonacci) Hashing
etc. . - I hope you understand open source code , Because then when you have a problem , Can quickly locate , It is also possible to create middleware for system services , To better decouple the system .
- I hope you understand design patterns , Because then you can write extensible 、 Easy to maintain program , Let the whole team develop in a better direction .
therefore , Never CRUD I chose you , It's not making screws to make you a tool maker . It's your technical ability that determines your vision , Vision determines the code you write !
Two 、 Interview questions
Thank you plane , Notes
I haven't got offer The plane , Get up early , Finish two oil bars , I went to the company to ask the interviewer for advice !
interviewer : The plane , Listen to the tank , You've been up in the dark to study .
Thank you plane : Mm-hmm , Yes , I've lost my hair recently !
interviewer : Let's talk about it today ThreadLocal
, It can be used in any scene ?
Thank you plane : Um. ,ThreadLocal
The solution is to share resources within threads (This class provides thread-local variables.), So it is usually used in full link monitoring , Or like a log framework MDC
In such components .
interviewer : The plane is good , I did learn recently . So you know ThreadLocal
What kind of data structure is it , What kind of hashing is used ?
Thank you plane : Array ? Um. , It's not clear how to hash …
interviewer : that ThreadLocal
There is a risk of memory leaks , How did it happen ? In addition, you know the process of , Probing and heuristic cleaning ?
Thank you plane : this …, Blind area , Blind area , coke
I put it on the table , I'll go home and read again !
3、 ... and 、ThreadLocal analysis
ThreadLocal
, author :Josh Bloch
and Doug Lea
, Two great gods
If it's just daily business development , This is a relatively cold category , The frequency of use is not high . And the method it provides is very simple , One function is just to scribble lines of code . but , If you dig deep into the source code of the implementation part , It's not that simple . There are too many knowledge points involved here , Include ; data structure
、 Zipper storage
、 Fibonacci scattered
、 magical 0x61c88647
、 Weak reference Reference
、 Be overdue key Probe cleanup and heuristic cleanup
wait .
Next , We're going to learn this step by step Blind area knowledge . This paper involves more code and practical verification drawings , Welcome to the official account :bugstack Wormhole stack
, Reply to download to get a link after opening , find ID:19🤫 obtain !*
1. Application scenarios
1.1 SimpleDateFormat
private SimpleDateFormat f = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
public void seckillSku(){
String dateStr = f.format(new Date());
// The business process
}
Have you ever written this code ? If you still write like this , A thread safe error has been made .SimpleDateFormat
, It's 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();
}
}
This is a multithread under SimpleDateFormat
The verification code of . When equals by false
when , Prove that threads are unsafe . The operation 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
1.1.2 Use ThreadLocal Optimize
The most direct way for thread safety , That is, every call is direct new SimpleDateFormat
. But it's not the best way after all , So we 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();
}
}
As above, we put SimpleDateFormat
, Put it in ThreadLocal
For use in , That is, there is no need to repeat new object , It also avoids thread insecurity . The test results are as follows ;
true
true
true
true
true
true
true
...
1.2 Link tracking
In recent years, it is based on Google Dapper
This paper realizes the non-invasive full link tracing , It's used more and more widely . In short, this is a monitoring system , But you don't have to hardcode your monitoring methods , It's based on its design javaagent + Bytecode
The way of inserting piles , Dynamic collection method execution information . If you want to know about bytecode instrumentation , Read my bytecode programming column :https://bugstack.cn/itstack-demo-agent/itstack-demo-agent.html
a key , Dynamic collection method execution information . This is the main part , Follow ThreadLocal
relevant . Bytecode stub
It's about non intrusive programming , So in a service call , Calls of multiple methods between and within systems , All need to be collected . You need to use ThreadLocal
Record method execution ID, Of course, there are cross thread calls, which are also enhanced versions ThreadLocal
, But in any case, the basic principle remains the same .
1.2.1 Trace code
Here's an example of a 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(){
trackLocal.remove();
}
public static String getLinkId(){
return trackLocal.get();
}
public static void setLinkId(String linkId){
trackLocal.set(linkId);
}
}
@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 tracking (MQ):" + exitSpan.getLinkId() + " " + className + "." + methodName + " Time consuming :" + (System.currentTimeMillis() - exitSpan.getEnterTime().getTime()) + "ms");
}
- The above part is about non intrusion monitoring , The process of link tracking . Specific case and code can refer to read , Series of special articles 《 be based on JavaAgent Full link monitoring of 》
- It's just one way to do it , Bytecode instrumentation uses
byte-buddy
, In fact, we still use ,ASM
perhapsJavassist
.
1.2.2 test result
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-SNAPSHOT.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);
}
Running results
onTransformation:class org.itstack.demo.test.ApiTest
test result :hi2 The wu is empty
test result :hi3 The wu is empty
Link tracking (MQ):90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt3 Time consuming :104ms
init: 256MB max: 3614MB used: 44MB committed: 245MB use rate: 18%
init: 2MB max: 0MB used: 13MB committed: 14MB use rate: 95%
name: PS Scavenge count:0 took:0 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep count:0 took:0 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]
-------------------------------------------------------------------------------------------------
Link tracking (MQ):90c7d543-c7b8-4ec3-af4d-b4d4f5cff760 org.itstack.demo.test.ApiTest.http_lt2 Time consuming :233ms
init: 256MB max: 3614MB used: 44MB committed: 245MB use rate: 18%
init: 2MB max: 0MB used: 13MB committed: 14MB use rate: 96%
name: PS Scavenge count:0 took:0 pool name:[PS Eden Space, PS Survivor Space]
name: PS MarkSweep count:0 took:0 pool name:[PS Eden Space, PS Survivor Space, PS Old Gen]
- These are the test results of link tracking , You can see that both methods will type the corresponding code ID:
90c7d543-c7b8-4ec3-af4d-b4d4f5cff760
. - This part is also the core application of full link tracking , And you can see that some simple systems are printed here JVM Monitoring indicators , It's also part of monitoring .
Cough , In addition to this, all the , All need to use ThreadLocal
, for example MDC
Log framework, etc . Now we start to analyze in detail ThreadLocal
The implementation of the .
2. data structure
Before understanding a function , First understand its data structure . This is equivalent to looking at its foundation first , With this, it's easy to understand in the future . Here are ThreadLocal
Simple use and part of the source code .
new ThreadLocal<String>().set(" Little brother Fu ");
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)]) {
...
}
You can see from this part of the source code ,ThreadLocal
The bottom layer uses array structure to store data , At the same time, hash value is used to calculate the subscript , This shows that it is an array structure of hash table , The demonstration is shown in the following figure ;
As shown in the figure above ThreadLocal
The underlying data structure that holds the data , The knowledge points are as follows ;
- It's an array structure .
Entry
, There's no use opening it here , It's actually a weak reference implementation ,static class Entry extends WeakReference<ThreadLocal<?>>
. This shows that as long as there is no strong reference , happen GC You'll be garbage collected .- Data elements are stored in hash hash , But the hash here uses
Fibonacci (Fibonacci) Hashing
, It will be analyzed in detail later . - And because it's different from HashMap Data structure of , Hash collision will not be saved as linked list or red black tree , It's about zipper storage . That is, when the same subscript position conflicts , be
+1 Address backwards
, Until an empty location or garbage collection location is found for storage .
3. Hash algorithm
since ThreadLocal
Is based on the array structure of zipper storage , Then there must be a hash calculation . But after we read the source code , Find out that this hash calculation is related to HashMap
The hash method of array subscript calculation in hash is different . If you forget HashMap, You can read articles 《HashMap Source code analysis , Insert 、 lookup 》、《HashMap Disturbance function 、 Load factor 》
3.1 Mysterious numbers 0x61c88647
When we look at ThreadLocal
When executing the setting element , There is such a code to calculate hash value ;
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
You must have such a question when you see it here , This is how hash is calculated ? How did this number come from ?
Here we are. , In fact, the way hashes are calculated , It's not just that we see String A way to get a hash value , It also includes ; division method
、 Square hash
、 Fibonacci (Fibonacci) Hashing
、 Random number method
etc. .
and ThreadLocal
What you use is Fibonacci (Fibonacci) Hashing
+ Zipper method stores data into array structure . The reason why we use Fibonacci sequence , It's to make the data more hash , Reduce hash collisions . It comes from the calculation and evaluation of mathematical formulas , The formula :f(k) = ((k * 2654435769) >> X) << Y For common 32 Bit integers , That is to say f(k) = (k * 2654435769) >> 28
The second question is , Numbers 0x61c88647
, How did you get it ?
In fact, this is the golden section of a hash value , That is to say 0.618
, Do you remember the math you learned ? The calculation method is as follows ;
// Golden 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
- If you have studied mathematics, you should know , The golden point is ,
(√5 - 1) / 2
, take 10 The bit approximation0.6180339887
. - After use 2 ^ 32 * 0.6180339887, And what you get is :
-1640531527
, That is to say 16 It's binary ,0x61c88647. This is how this number comes from
3.2 Validate hash
since ,Josh Bloch
and Doug Lea
, The two men chose to use the Fibonacci sequence , Calculate the hash value . There must be something special about it , It's better hashing , Reduce hash collisions .
Next, we get the hash value and calculate the subscript in the source code , Put this part of the code out for verification .
3.2.1 Part of the source code
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
// Compute hash
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
// Get subscript
int i = key.threadLocalHashCode & (len-1);
Above , The source code part uses AtomicInteger
, Atomic method computes subscripts . We don't need to be thread safe , It only needs a simple implementation . in addition ThreadLocal
Initialization array length is 16, We also initialize this length .
3.2.2 unit testing
@Test
public void test_idx() {
int hashCode = 0;
for (int i = 0; i < 16; i++) {
hashCode = i * HASH_INCREMENT + HASH_INCREMENT;
int idx = hashCode & 15;
System.out.println(" Fibonacci scattered :" + idx + " General hash :" + (String.valueOf(i).hashCode() & 15));
}
}
Test the code part , The Fibonacci sequence is used , At the same time, we add ordinary hash algorithm to compare the hash effect . Of course String This hash doesn't look like HashMap To disturb
test result :
Fibonacci scattered :7 General hash :0
Fibonacci scattered :14 General hash :1
Fibonacci scattered :5 General hash :2
Fibonacci scattered :12 General hash :3
Fibonacci scattered :3 General hash :4
Fibonacci scattered :10 General hash :5
Fibonacci scattered :1 General hash :6
Fibonacci scattered :8 General hash :7
Fibonacci scattered :15 General hash :8
Fibonacci scattered :6 General hash :9
Fibonacci scattered :13 General hash :15
Fibonacci scattered :4 General hash :0
Fibonacci scattered :11 General hash :1
Fibonacci scattered :2 General hash :2
Fibonacci scattered :9 General hash :3
Fibonacci scattered :0 General hash :4
Process finished with exit code 0
Found not ?, Fibonacci's hash is very uniform , General hash to 15 After that, we have developed and produced collision . This is the charm of Fibonacci hash , Reducing collisions can also make data storage more decentralized , The complexity of data acquisition is kept at the basic level O(1).
4. Source code interpretation
4.1 initialization
new ThreadLocal<>()
The initialization process is also very simple , It can be set according to the generic type you need . But in ThreadLocal
There is a very important point in the source code of , Is to get threadLocal
To get the hash value of ,threadLocalHashCode
.
private final int threadLocalHashCode = nextHashCode();
/**
* Returns the next hash code.
*/
private static int nextHashCode() {
return nextHashCode.getAndAdd(HASH_INCREMENT);
}
Such as source code , Just instantiate one ThreadLocal
, It will get a corresponding hash value , Let's make an example .
@Test
public void test_threadLocalHashCode() 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));
}
}
because threadLocalHashCode
, It's a private property , So we can get the hash value through the above method after instantiation .
objectThreadLocal:-1401181199
objectThreadLocal:239350328
objectThreadLocal:1879881855
objectThreadLocal:-774553914
objectThreadLocal:865977613
Process finished with exit code 0
Get this value , That is calculation ThreadLocalMap
, When storing data ,ThreadLocal
Array subscript of . As long as it's the same object , stay set
、get
when , You can set and get the corresponding value .
4.2 Set the element
4.2.1 Flow chart
new ThreadLocal<>().set(" Little brother Fu ");
How to set the element , It's just this code . But the process of setting elements involves more , Before analyzing the code in detail , Let's take a look at a flowchart of setting elements , First understand the process of different situations from the diagram, and then learn the source code by comparison . The flow chart is as follows ;
At first glance, it may feel a little dizzy , We look from left to right , They have the following knowledge points ;
- In the middle is
ThreadLocal
The array structure of , After setting the element, there are four different situations , In addition, the insertion of elements is calculated by Fibonacci hash , For storage . - situation 1, Subscript to be inserted , It is an empty position to insert directly .
- situation 2, Subscript to be inserted , Not empty ,key identical , Direct updating
- situation 3, Subscript to be inserted , Not empty ,key inequality , Zip addressing
- situation 4, Not empty ,key inequality , I ran into an expiration date key. In fact, the situation 4, It's a weak reference that happens GC when , What happened . In this case ,
ThreadLocal
It's going to probe, clean up, expire key, This part of the clean-up content 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();
}
With the diagram above , If you look at the code part, it's easier to understand , The corresponding contents include , as follows ;
key.threadLocalHashCode & (len-1);
, Fibonacci scattered , Compute array subscripts .Entry
, Is a weak reference object implementation class ,static class Entry extends WeakReference<ThreadLocal<?>>
, So there is no strong external reference , It's going to happen GC, Delete key.- for Loop to determine whether an element exists , When there is no element in the current subscript , Set elements directly
tab[i] = new Entry(key, value);
. - If the element exists , It will judge whether or not key The values are equal
if (k == key)
, Equal updates the value . - If it's not equal , It's just our
replaceStaleEntry
, In other words, the above figure refers to the detection of expired elements .
Sum up , It's the whole process of storing elements , The design of the whole structure is wonderful , Great use of hash effect , We also use weak references very much 6!
4.3 Expansion mechanism
4.3.1 Capacity expansion condition
Just use the array structure , There will be expansion
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
As we read the settings element , There is a piece of code above , Judge whether to expand capacity .
- First , Conduct
Heuristic cleanup *cleanSomeSlots*
, Get rid of outdated elements , See if the space is - after , Judge
sz >= threshold
, amongthreshold = len * 2 / 3
, In other words, the elements of the array filled with sky , Greater thanlen * 2 / 3
, It needs to be expanded . - Last , That's the focus of our analysis ,
rehash();
, Expand and recalculate element position .
4.3.2 Source code analysis
Exploratory cleaning and verification
private void rehash() {
expungeStaleEntries();
// Use lower threshold for doubling to avoid hysteresis
if (size >= threshold - threshold / 4)
resize();
}
private void expungeStaleEntries() {
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);
}
}
- This part is mainly about probing to clean up expired elements , And judge whether the capacity expansion conditions are met after cleaning ,size >= threshold * 3/4
- After meeting the requirements, expand the capacity , In fact, the core operation after the expansion is to recalculate the hash value , Fill in the new array with elements .
rehash() Capacity expansion
private void resize() {
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;
}
above , Code is the overall operation of the expansion , It includes the following steps ;
- First expand the length of the array to the original 2 times ,
oldLen * 2
, Instantiate the new array . - Traverse for, All the elements in the old array , Put it back in the new array .
- In the process of placing arrays , If there is a hash collision , Then the chain method is extended .
- At the same time, there's testing key The operation of the value
if (k == null)
, convenient GC.
4.4 Get elements
4.4.1 Flow chart
new ThreadLocal<>().get();
Similarly, getting elements is just like this code , If there is no source code analysis before , You can think about it in different data structures , Did you do anything to get the elements . Let's take a look at the figure below , It can be divided into the following situations ;
According to different data element storage conditions , It basically includes the following situations ;
- Go straight to , There is no hash conflict , Return the element directly .
- No direct positioning to ,key Different , Need zipper search .
- No direct positioning to ,key Different , Zip search , encounter GC Clean up elements , Need to be probe cleaned up , Look for elements again .
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;
}
Okay , This part is to get the source code part of the element , It is consistent with what we have shown in the figure .expungeStaleEntry
, It was found that there was key == null
when , To clean up expired elements , And put the elements of subsequent positions , Move forward .
4.5 Element cleanup
4.5.1 Probe cleaning [expungeStaleEntry]
Probe cleaning , It's based on what I've come across right now GC The element begins , Clean up back and forth . Until I met null until , Just stop rehash Calculation Rehash until we encounter null
.
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;
}
above , Exploratory cleaning is used in getting elements ; new ThreadLocal<>().get() -> map.getEntry(this) -> getEntryAfterMiss(key, i, e) -> expungeStaleEntry(i)
4.5.2 Heuristic cleanup [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.
Heuristic cleanup , There's a note , Roughly meaning ; Scan some cells tentatively , Looking for expired elements , That is, the elements that are garbage collected . When you add a new element or delete another obsolete element , This function will be called . It performs logarithmic scans , As not scanning ( Fast but keep garbage ) And the number of scans proportional to the number of elements , This will find all the rubbish , But it can lead to some insertion costs 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;
}
while The loop is constantly moving right to find out the expired elements that need to be cleaned up , They will eventually use expungeStaleEntry
To deal with , There's also element shifting .
Four 、 summary
- Write this is to say
ThreadLocal
The analysis of a corner of knowledge is finished , stayThreadLocal
There is alsoNetty
Used in ,FastThreadLocal
. Get call links between full link and cross service threads , alsoTransmittableThreadLocal
, And then there is JDK A thread passing solution with its ownInheritableThreadLocal
. But on the basis of this article , Understand the most basic principles , In understanding other development designs , It's easier to accept . - In addition, we often see probe cleaning in our analysis , In fact, this is also very time-consuming . For this we are using ThreadLocal Remember that
new ThreadLocal<>().remove();
operation . Avoid weak references GC after , The problem that caused the memory leak . - Last , Did you find out ! We learn the underlying principles , It's all about data structure and good design , Or the shadow of the algorithm . This code is the foundation of the whole system , If we can extract some ideas into the core business processes we develop , It can also greatly improve performance .
5、 ... and 、 Series recommendation
- Is the grass , You're poisoning the code !
- A code review , Almost couldn't pass the probation period !
- HashMap Core knowledge , Disturbance function 、 Load factor 、 Split the expanded list , Deep learning
- HashMap Insert data into 、 lookup 、 Delete 、 Traverse , Source code analysis
- Relearning Java Design patterns (22 Real development scenarios )

( Please indicate the author and source of this article WeChat official account :bugstack Wormhole stack | author : Little brother Fu )
版权声明
本文为[Bugstack wormhole stack]所创,转载请带上原文链接,感谢
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World