02/14 12:45

## 黄金分割数与斐波那契数列

• 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
• 通项公式：假设F(n)为该数列的第n项（n ∈ N*），那么这句话可以写成如下形式：F(n) = F(n-1) + F(n-2)。

## 黄金分割数的应用

``````public static void main(String[] args) throws Exception {
//黄金分割数 * 2的32次方 = 2654435769 - 这个是无符号32位整数的黄金分割数对应的那个值
long c = (long) ((1L << 32) * (Math.sqrt(5) - 1) / 2);
System.out.println(c);
//强制转换为带符号为的32位整型，值为-1640531527
int i = (int) c;
System.out.println(i);
}
``````

``````public class Main {

private static final int HASH_INCREMENT = 0x61c88647;

public static void main(String[] args) throws Exception {
hashCode(4);
hashCode(16);
hashCode(32);
}

private static void hashCode(int capacity) throws Exception {
int keyIndex;
for (int i = 0; i < capacity; i++) {
keyIndex = ((i + 1) * HASH_INCREMENT) & (capacity - 1);
System.out.print(keyIndex);
System.out.print(" ");
}
System.out.println();
}
}
``````

``````3 2 1 0
7 14 5 12 3 10 1 8 15 6 13 4 11 2 9 0
7 14 21 28 3 10 17 24 31 6 13 20 27 2 9 16 23 30 5 12 19 26 1 8 15 22 29 4 11 18 25 0
``````

This class provides thread-local variables. These variables differ from their normal counterparts in that each thread that accesses one (via its get or set method) has its own, independently initialized copy of the variable. ThreadLocal instances are typically private static fields in classes that wish to associate state with a thread (e.g., a user ID or Transaction ID)

`ThreadLocal`由Java界的两个大师级的作者编写，Josh Bloch和Doug Lea。Josh Bloch是JDK5语言增强、Java集合(Collection)框架的创办人以及《Effective Java》系列的作者。Doug Lea是JUC(`java.util.concurrent`)包的作者，Java并发编程的泰斗。所以，`ThreadLocal`的源码十分值得学习。

`ThreadLocal`虽然叫线程本地(局部)变量，但是实际上它并不存放任何的信息，可以这样理解：它是线程(`Thread`)操作`ThreadLocalMap`中存放的变量的桥梁。它主要提供了初始化、`set()``get()``remove()`几个方法。这样说可能有点抽象，下面画个图说明一下在线程中使用`ThreadLocal`实例的`set()``get()`方法的简单流程图。

``````public class Main {

public static void main(String[] args) throws Exception{
LOCAL.set("doge");
System.out.println(LOCAL.get());
}
}
``````

``````//获取下一个ThreadLocal实例的哈希魔数
private final int threadLocalHashCode = nextHashCode();

//原子计数器，主要到它被定义为静态
private static AtomicInteger nextHashCode = new AtomicInteger();

//哈希魔数(增长数)，也是带符号的32位整型值黄金分割值的取正
private static final int HASH_INCREMENT = 0x61c88647;

//生成下一个哈希魔数
private static int nextHashCode() {
}
``````

``````//t1中的threadLocalHashCode变量为0x61c88647
``````

threadLocalHashCode是下面的`ThreadLocalMap`结构中使用的哈希算法的核心变量，对于每个`ThreadLocal`实例，它的threadLocalHashCode是唯一的。

`ThreadLocal`内部类`ThreadLocalMap`使用了默认修饰符，也就是包(包私有)可访问的。`ThreadLocalMap`内部定义了一个静态类`Entry`。我们重点看下`ThreadLocalMap`的源码，先看成员和结构部分：

``````/**
* 为了处理非常大(指的是值)和长时间的用途，哈希表的Key使用了弱引用(WeakReferences)。
* 引用的队列(弱引用)不再被使用的时候，对应的过期的条目就能通过主动删除移出哈希表。
*/

static class Entry extends WeakReference<ThreadLocal<?>> {

//这个是真正的存放的值
Object value;
super(k);
value = v;
}
}
//初始化容量，必须是2的幂次方
private static final int INITIAL_CAPACITY = 16;

//哈希(Entry)表，必须时扩容，长度必须为2的幂次方
private Entry[] table;

//哈希表中元素(Entry)的个数
private int size = 0;

//下一次需要扩容的阈值，默认值为0
private int threshold;

//设置下一次需要扩容的阈值，设置值为输入值len的三分之二
private void setThreshold(int len) {
threshold = len * 2 / 3;
}

// 以len为模增加i
private static int nextIndex(int i, int len) {
return ((i + 1 < len) ? i + 1 : 0);
}

// 以len为模减少i
private static int prevIndex(int i, int len) {
return ((i - 1 >= 0) ? i - 1 : len - 1);
}
}
``````

``````// 构造ThreadLocal时候使用，对应ThreadLocal的实例方法void createMap(Thread t, T firstValue)
// 哈希表默认容量为16
table = new Entry[INITIAL_CAPACITY];
// 计算第一个元素的哈希码
int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
table[i] = new Entry(firstKey, firstValue);
size = 1;
setThreshold(INITIAL_CAPACITY);
}

Entry[] parentTable = parentMap.table;
int len = parentTable.length;
setThreshold(len);
table = new Entry[len];
for (Entry e : parentTable) {
if (e != null) {
@SuppressWarnings("unchecked")
if (key != null) {
Object value = key.childValue(e.value);
Entry c = new Entry(key, value);
int h = key.threadLocalHashCode & (len - 1);
while (table[h] != null)
h = nextIndex(h, len);
table[h] = c;
size++;
}
}
}
}
``````

``````// 如果Key在哈希表中找不到哈希槽的时候会调用此方法
private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
Entry[] tab = table;
int len = tab.length;
// 这里会通过nextIndex尝试遍历整个哈希表，如果找到匹配的Key则返回Entry
// 如果哈希表中存在Key == null的情况，调用expungeStaleEntry进行清理
while (e != null) {
if (k == key)
return e;
if (k == null)
expungeStaleEntry(i);
else
i = nextIndex(i, len);
e = tab[i];
}
return null;
}

// 1.清空staleSlot对应哈希槽的Key和Value
// 2.对staleSlot到下一个空的哈希槽之间的所有可能冲突的哈希表部分槽进行重哈希，置空Key为null的槽
// 3.注意返回值是staleSlot之后的下一个空的哈希槽的哈希码
private int expungeStaleEntry(int staleSlot) {
Entry[] tab = table;
int len = tab.length;

// expunge entry at staleSlot
// 清空staleSlot对应哈希槽的Key和Value
tab[staleSlot].value = null;
tab[staleSlot] = null;
size--;

// Rehash until we encounter null
// 下面的过程是对staleSlot到下一个空的哈希槽之间的所有可能冲突的哈希表部分槽进行重哈希，置空Key为null的槽
Entry e;
int i;
for (i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {
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;
}

// 这里个方法比较长，作用是替换哈希码为staleSlot的哈希槽中Entry的值
private void replaceStaleEntry(ThreadLocal<?> key, Object value, int staleSlot) {
Entry[] tab = table;
int len = tab.length;
Entry e;

// Back up to check for prior stale entry in current run.
// We clean out whole runs at a time to avoid continual
// incremental rehashing due to garbage collector freeing
// up refs in bunches (i.e., whenever the collector runs).
int slotToExpunge = staleSlot;
// 这个循环主要是为了找到staleSlot之前的最前面的一个Key为null的哈希槽的哈希码
for (int i = prevIndex(staleSlot, len); (e = tab[i]) != null; i = prevIndex(i, len))
if (e.get() == null)
slotToExpunge = i;

// Find either the key or trailing null slot of run, whichever
// occurs first
// 遍历staleSlot之后的哈希槽，如果Key匹配则用输入值替换
for (int i = nextIndex(staleSlot, len); (e = tab[i]) != null; i = nextIndex(i, len)) {

// If we find key, then we need to swap it
// with the stale entry to maintain hash table order.
// The newly stale slot, or any other stale slot
// encountered above it, can then be sent to expungeStaleEntry
// to remove or rehash all of the other entries in run.
if (k == key) {
e.value = value;
tab[i] = tab[staleSlot];
tab[staleSlot] = e;
// Start expunge at preceding stale entry if it exists
if (slotToExpunge == staleSlot)
slotToExpunge = i;
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
return;
}

// If we didn't find stale entry on backward scan, the
// first stale entry seen while scanning for key is the
// first still present in the run.
if (k == null && slotToExpunge == staleSlot)
slotToExpunge = i;
}
// Key匹配不了，则新创建一个哈希槽
tab[staleSlot].value = null;
tab[staleSlot] = new Entry(key, value);

// 这里如果当前的staleSlot和找到前置的slotToExpunge不一致会进行一次清理
// If there are any other stale entries in run, expunge them
if (slotToExpunge != staleSlot)
cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

// 对当前哈希表中所有的Key为null的Entry调用expungeStaleEntry
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);
}
}

// 清理第i个哈希槽之后的n个哈希槽，如果遍历的时候发现Entry的Key为null，则n会重置为哈希表的长度，expungeStaleEntry有可能会重哈希使得哈希表长度发生变化
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;
}

/**
*
*/
// 计算Entry的哈希值
int i = key.threadLocalHashCode & (table.length - 1);
Entry e = table[i];
if (e != null && e.get() == key)
return e;
else  // 注意这里，如果e为null或者Key对不上，会调用getEntryAfterMiss
return getEntryAfterMiss(key, i, e);
}

// 重哈希，必要时进行扩容
private void rehash() {
// 清理所有空的哈希槽，并且进行重哈希
expungeStaleEntries();

// Use lower threshold for doubling to avoid hysteresis
// 哈希表的哈希元素个数大于3/4阈值时候触发扩容
if (size >= threshold - threshold / 4)
resize();
}

// 扩容，简单的扩大2倍的容量
private void resize() {
Entry[] oldTab = table;
int oldLen = oldTab.length;
int newLen = oldLen * 2;
Entry[] newTab = new Entry[newLen];
int count = 0;

for (Entry e : oldTab) {
if (e != null) {
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;
}

private void set(ThreadLocal<?> key, Object value) {

// We don't use a fast path as with get() because it is at
// least as common to use set() to create new entries as
// it is to replace existing ones, in which case, a fast
// path would fail more often than not.

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)]) {
// Key匹配，直接设置值
if (k == key) {
e.value = value;
return;
}
// 如果Entry的Key为null，则替换该Key为当前的key，并且设置值
if (k == null) {
replaceStaleEntry(key, value, i);
return;
}
}

tab[i] = new Entry(key, value);
int sz = ++size;
// 清理当前新设置元素的哈希槽下标到sz段的哈希槽，如果清理成功并且sz大于阈值则触发扩容
if (!cleanSomeSlots(i, sz) && sz >= threshold)
rehash();
}
``````

``````public class ThreadLocalMain {

public static void main(String[] args) throws Exception {
TL_1.set(1);
TL_2.set("1");
TL_3.set(1L);
field.setAccessible(true);
System.out.println(o);
}
}
``````

`ThreadLocal`的构造函数来看，`ThreadLocal`实例的构造并不会做任何操作，只是为了得到一个`ThreadLocal`的泛型实例，后续可以把它作为`ThreadLocalMap\$Entry`的键：

``````// 注意threadLocalHashCode在每个新`ThreadLocal`实例的构造同时已经确定了
private final int threadLocalHashCode = nextHashCode();
private static AtomicInteger nextHashCode = new AtomicInteger();
private static final int HASH_INCREMENT = 0x61c88647;
private static int nextHashCode() {
}

// 通过Supplier去覆盖initialValue方法
public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
}

// 默认公有构造函数

}
``````

`ThreadLocal``set()`方法的源码如下:

``````public void set(T value) {
//设置值前总是获取当前线程实例
if (map != null)
map.set(this, value);
else
createMap(t, value);
}

}

void createMap(Thread t, T firstValue) {
}
``````

• 获取当前运行线程的实例。
• 通过线程实例获取线程实例成员threadLocals(`ThreadLocalMap`)，如果为null，则创建一个新的`ThreadLocalMap`实例赋值到threadLocals。

`ThreadLocal``get()`方法的源码如下:

`````` public T get() {
//获取当前线程的实例
if (map != null) {
if (e != null) {
@SuppressWarnings("unchecked")
T result = (T) e.value;
return result;
}
}
return setInitialValue();
}

private T setInitialValue() {
// 调用initialValue方法获取值
T value = initialValue();
if (map != null)
map.set(this, value);
else
createMap(t, value);
return value;
}

protected T initialValue() {
return null;
}
``````

`initialValue()`方法默认返回null，如果`ThreadLocal`实例没有使用过`set()`方法直接使用`get()`方法，那么`ThreadLocalMap`中的此`ThreadLocal`为Key的项会把值设置为`initialValue()`方法的返回值。如果想改变这个逻辑可以对`initialValue()`方法进行覆盖。

`ThreadLocal``remove()`方法的源码如下:

``````public void remove() {
if (m != null)
m.remove(this);
}
``````

``````public class Thread implements Runnable {

}
``````

• 1、大量地(静态)初始化`ThreadLocal`实例，初始化之后不再调用`get()``set()``remove()`方法。
• 2、初始化了大量的`ThreadLocal`，这些`ThreadLocal`中存放了容量大的Value，并且使用了这些`ThreadLocal`实例的线程一直处于活跃的状态。

`ThreadLocal`中一个设计亮点是`ThreadLocalMap`中的`Entry`结构的Key用到了弱引用。试想如果使用强引用，等于`ThreadLocalMap`中的所有数据都是与`Thread`的生命周期绑定，这样很容易出现因为大量线程持续活跃导致的内存泄漏。使用了弱引用的话，JVM触发GC回收弱引用后，`ThreadLocal`在下一次调用`get()``set()``remove()`方法就可以删除那些`ThreadLocalMap`中Key为null的值，起到了惰性删除释放内存的作用。

``````public class ThreadLocalMain {

public static void main(String[] args) throws Exception {
TL_1.set(1);
TL_1 = null;
System.gc();
}
}
``````

• 每次使用完`ThreadLocal`实例，都调用它的`remove()`方法，清除`Entry`中的数据。

## 小结

`ThreadLocal`线程本地变量是线程实例传递和存储共享变量的桥梁，真正的共享变量还是存放在线程实例本身的属性中。`ThreadLocal`里面的基本逻辑并不复杂，但是一旦涉及到性能影响、内存回收(弱引用)和惰性删除等环节，其实它考虑到的东西还是相对全面而且有效的。

## 个人博客

(本文完 e-a-20190217 c-7-d 发现文章被盗和洗文了，图片的水印也被去掉，下次图片的水印打在中间才行)

0
0 收藏

0 评论
0 收藏
0