Code Monkey home page Code Monkey logo

blog's People

Contributors

graptioute avatar

Watchers

avatar

blog's Issues

ThreadLocal 源码分析

前言

在 JDK11 版本中，ThreadLocal 有这么一段注释：

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).

翻译过来就是：

该类提供线程局部变量。这些变量与普通变量的不同之处在于，每个访问一个变量（通过其 get 或 set 方法）的线程都有自己的、独立初始化的变量副本。ThreadLocal 实例通常是类中的私有静态字段，希望将状态与线程关联（例如，用户 ID 或事务 ID）。

简单来说：不同的线程访问相同的 ThreadLocal 实例变量（通过 get 或 set），都只会操作自己独立维护的值。

例子：

ThreadLocal<String> threadLocal = new ThreadLocal<>();

new Thread(() -> {
	threadLocal.set("thread-1");
	System.out.println("value: " + threadLocal.get());
}).start();

new Thread(() -> {
	threadLocal.set("thread-2");
	System.out.println("value: " + threadLocal.get());
}).start();

new Thread(() -> {
	threadLocal.set("thread-3");
	System.out.println("value: " + threadLocal.get());
}).start();

输出：

value: thread-1
value: thread-3
value: thread-2

set 方法

public void set(T value) {
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
        map.set(this, value);
    } else {
        createMap(t, value);
    }
}

可以用这样图来表示整个流程：

set drawio

hash 算法

在线程中首次调用 set 方法会构造一个 ThreadLocalMap 实例，并赋值给线程的实例变量 threadLocals。具体的构造方法：

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

new ThreadLocal.ThreadLocalMap.Entry[INITIAL_CAPACITY]; 初始化 Entry 类型的数组，其中 INITIAL_CAPACITY 的容量为 16。

Entry 类如下：

static class Entry extends WeakReference<ThreadLocal<?>> {
	/** The value associated with this ThreadLocal. */
	Object value;

	Entry(ThreadLocal<?> k, Object v) {
		super(k);
		value = v;
	}
}

Entry 继承 WeakReference，所以在发生 GC 之后，Entry.get() 方法返回值可能出现为 null 的情况，这说明相应的 threadlocal 实例已经被清除。

firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1); 是计算相应的存储索引位置。

threadLocalHashCode 是根据以下代码生成的：

private final int threadLocalHashCode = nextHashCode();

private static AtomicInteger nextHashCode = new AtomicInteger();

private static final int HASH_INCREMENT = 0x61c88647;

private static int nextHashCode() {
       return nextHashCode.getAndAdd(HASH_INCREMENT);
}

每构造一个 threadLocal 实例相应的 hashCode 会增加 HASH_INCREMENT。

HASH_INCREMENT 这个值非常特殊，它是斐波那契数也叫黄金分割数。每个 threadLocal 实例增量为这个数带来的好处就是 hash 分布非常均匀（最大可能减少 hash 碰撞）。

例子：

int hashCode = 0;
for (int i = 0; i < 16; i++) {
	hashCode = i * HASH_INCREMENT + HASH_INCREMENT;
	int bucket = hashCode & 15;
	System.out.println(i + " buket index: " + bucket);
}

输出：

0 buket index: 7
1 buket index: 14
2 buket index: 5
3 buket index: 12
4 buket index: 3
5 buket index: 10
6 buket index: 1
7 buket index: 8
8 buket index: 15
9 buket index: 6
10 buket index: 13
11 buket index: 4
12 buket index: 11
13 buket index: 2
14 buket index: 9
15 buket index: 0

从输出结果可以看到没有发生碰撞。

生成索引后赋值到相应的位置，并且 size 设成 1，初始化扩容阈值。

ThreadLocalMap.set() 方法

ThreadLocal.set() 方法最终都对 ThreadLcoalMap.set() 进行调用，代码如下：

private void set(ThreadLocal<?> key, Object value) {
	ThreadLocal.ThreadLocalMap.Entry[] tab = table;
	int len = tab.length;
	int i = key.threadLocalHashCode & (len-1);

	for (ThreadLocal.ThreadLocalMap.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 ThreadLocal.ThreadLocalMap.Entry(key, value);
	int sz = ++size;
	if (!cleanSomeSlots(i, sz) && sz >= threshold)
		rehash();
}

根据 threadLocalHashCode 计算出此始索引 i 然后向后遍历 tab 数组，直到遇到 null 停止。

其中 nextIndex 方法代码如下：

private static int nextIndex(int i, int len) {
	return ((i + 1 < len) ? i + 1 : 0);
}

当在遍历的过程中遇到相同的 key 会对 value 进行替换操作，然后返回：

if (k == key) {
	e.value = value;
	return;
}

如果遇到 key 为 null 情况执行 replaceStaleEntry() 进行清理，然后返回：

if (k == null) {
	replaceStaleEntry(key, value, i);
	return;
}

如果遍历过程中不满足退出条件，此时 tab 的 i 索引为 null。根据 key 和 value 新建 Entry 实例并赋值，size 值加 1。

循环退出，此时索引 i 位置上的元素为 null，新建一个 Entry 示例并赋值到这个位置上。 size 加 1，最后执行 cleanSomeSlots() 进行清理并根据结果是否 rehash()。

tab[i] = new Entry(key, value);
int sz = ++size;
if (!cleanSomeSlots(i, sz) && sz >= threshold)
    rehash();

replaceStaleEntry() 方法

该方法提供替换过期数据的功能。

private void replaceStaleEntry(ThreadLocal<?> key, Object value,
                               int staleSlot) {
	ThreadLocal.ThreadLocalMap.Entry[] tab = table;
	int len = tab.length;
	ThreadLocal.ThreadLocalMap.Entry e;
	
	int slotToExpunge = staleSlot;
	for (int i = prevIndex(staleSlot, len);
	     (e = tab[i]) != null;
	     i = prevIndex(i, len))
		if (e.get() == null)
			slotToExpunge = i;
	
	for (int i = nextIndex(staleSlot, len);
	     (e = tab[i]) != null;
	     i = nextIndex(i, len)) {
		ThreadLocal<?> k = e.get();
		
		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 (k == null && slotToExpunge == staleSlot)
			slotToExpunge = i;
	}
	
	tab[staleSlot].value = null;
	tab[staleSlot] = new ThreadLocal.ThreadLocalMap.Entry(key, value);
	
	if (slotToExpunge != staleSlot)
		cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
}

slotToExpunge 表示开始探测式清理的开始下标，默认从 staleSlot 开始。向前迭代查找，直到碰到 Entry 为 null 的情况才结束。如果在迭代的过程中找到了过期数据，则更新 slotToExpunge 为过期项索引。

int slotToExpunge = staleSlot;
for (int i = prevIndex(staleSlot, len);
	(e = tab[i]) != null;
	i = prevIndex(i, len))
	if (e.get() == null)
	slotToExpunge = i;

从 staleSlot 开始向后迭代，遇到 Entry 为 null 结束。在迭代过程中可能会遇到 k == key 的情况此时将 staleSlot 索引位置上的元素与索引 i 位置的元素进行交换，如果在向前迭代的过程中没有遇到过期项此时需要将当前索引赋值给 slotToExpunge。最后执行 cleanSomeSlots() 和 expungeStaleEntry() 然后返回。

if (k == key) {
	e.value = value;

	tab[i] = tab[staleSlot];
	tab[staleSlot] = e;

	if (slotToExpunge == staleSlot)
	slotToExpunge = i;
	cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
	return;
}

如果 k 为 null 说明此时遇到一个过期项，并且向前迭代过程中没有发现过期项则将当前的索引赋值给 slotToExpunge。

if (k == null && slotToExpunge == staleSlot)
	slotToExpunge = i;

slotToExpunge == staleSlot 说明在向前和向后的迭代过程中没有找到过期项，不相等需要执行 cleanSomeSlots() 和 expungeStaleEntry() 进行清理。

if (slotToExpunge != staleSlot)
    cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);

探测式清理

expungeStaleEntry() 是进行探测式清理的方法。

源码：

private int expungeStaleEntry(int staleSlot) {
	ThreadLocal.ThreadLocalMap.Entry[] tab = table;
	int len = tab.length;

	// expunge entry at staleSlot
	tab[staleSlot].value = null;
	tab[staleSlot] = null;
	size--;

	// Rehash until we encounter null
	ThreadLocal.ThreadLocalMap.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;
}

它的主要逻辑是遍历 tab 数组从开始位置向后探测清理过期项，迭代过程中将过期项置为 null，如果遇到未过期将此数据 rehash 重新在 tab 数组中定位，如果定位的位置已经有了数据，则将未过期项放到最靠近此位置的 Entry 为 null 的位置中。使得 rehash 后的数据项更接近正确的位置上。Entry 为 null 的情况下结束遍历。

用图形来表示清理过程中遇到的各种情况

expungeStaleEntry drawio

expungeStaleEntry() 返回值表明 tab 数组在此位置上为 null。

启发式清理

cleanSomeSlots() 表示启发式清理。

源码：

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

(n >>>= 1) 决定循环次数，比如说 n 为 8 此时 n 为 8 => 4 => 2 => 1 => 0。循环次数为 3 次。

如果在遍历过程中遇到 e != null && e.get() == null 则重新初始化 n，并进行一次 expungeStaleEntry()。

返回值为 true 说明在遍历的过程中有过期项。

扩容机制

在 ThreadLocalMap.set() 方法最后， 如果执行启发式清理 cleanSomeSlots() 后并未清理到数据项，且当前 size 达到 threshlod（len * 2 / 3）则进行 rehash() 逻辑如下：

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

rehash() 代码：

private void rehash() {
	expungeStaleEntries();

	// Use lower threshold for doubling to avoid hysteresis
	if (size >= threshold - threshold / 4)
		resize();
}

private void expungeStaleEntries() {
	ThreadLocal.ThreadLocalMap.Entry[] tab = table;
	int len = tab.length;
	for (int j = 0; j < len; j++) {
		ThreadLocal.ThreadLocalMap.Entry e = tab[j];
		if (e != null && e.get() == null)
			expungeStaleEntry(j);
	}
}

先进行探测式清理 expungeStaleEntry，清理完以后此时 size 达到 threshold * 3/4 则进行 resize()。

resize 代码如下：

private void resize() {
	ThreadLocal.ThreadLocalMap.Entry[] oldTab = table;
	int oldLen = oldTab.length;
	int newLen = oldLen * 2;
	ThreadLocal.ThreadLocalMap.Entry[] newTab = new ThreadLocal.ThreadLocalMap.Entry[newLen];
	int count = 0;

	for (ThreadLocal.ThreadLocalMap.Entry e : oldTab) {
		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;
}

扩容为原来的两倍，对数据项进行重新定位，如果新位置有数据则将数据项放置到最近 Entry 为 null 的位置上。重新计算 threshold。

get() 方法

源码：

public T get() {
	Thread t = Thread.currentThread();
	ThreadLocal.ThreadLocalMap map = getMap(t);
	if (map != null) {
		ThreadLocal.ThreadLocalMap.Entry e = map.getEntry(this);
		if (e != null) {
			@SuppressWarnings("unchecked")
			T result = (T)e.value;
			return result;
		}
	}
	return setInitialValue();
}

获取线程的 threadLocals 如果存在则调用 getEntry 方法获取 Entry 数据项，否则调用 setInitialValue() 初始化值和线程的 threadLocals。

ThreadLocalMap.getEntry() 方法源码：

private ThreadLocal.ThreadLocalMap.Entry getEntry(ThreadLocal<?> key) {
	int i = key.threadLocalHashCode & (table.length - 1);
	ThreadLocal.ThreadLocalMap.Entry e = table[i];
	if (e != null && e.get() == key)
		return e;
	else
		return getEntryAfterMiss(key, i, e);
}

根据 key 计算得到对应的索引，如果索引在 table 数组对应数据项的匹配的话直接返回，否则调用 getEntryAfterMiss() 继续查找。

ThreadLocalMap.getEntryAfterMiss() 源码：

private ThreadLocal.ThreadLocalMap.Entry getEntryAfterMiss(ThreadLocal<?> key, int i, ThreadLocal.ThreadLocalMap.Entry e) {
	ThreadLocal.ThreadLocalMap.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;
}

数据项为 null 结束遍历，在遍历过程中会遇到以下几种情况：

  1. key 相等，直接返回提前结束遍历。
  2. k 为 null，则进行探测式清理 expungeStaleEntry()。

参考

  1. JDK 11 ThreadLocal 源码。

JDK UUID 实现

前言

通用唯一辨识码（Universally Unique Identifier，缩写：UUID）是用于计算机体系中以识别信息的一个 128 位标识符。

UUID 按照标准方法生成时，在实际应用中具有唯一性，且不依赖**机构的注册和分配。UUID 重复的概率接近零，可以忽略不计。

变体与版本

RFC 4122 定义了 4 种变体：

  1. 变体 0（二进制 0xxx2），用于向后兼容已过时的1988年开发的 Apollo 网络计算系统（NCS）1.5 UUID 格式。
  2. 变体 1（二进制 10xx2），定义在 RFC 4122/DCE 1.1 UUIDs，或 "Lech-Salz" UUID。它是按大端序作为二进制存储和传输。
  3. 变体 2（二进制 110x2），RFC 称 "保留，微软公司向后兼容"。早期的Microsoft Windows 平台的 GUID 使用该格式。
  4. 形如 111x2 保留未使用。

版本：

  1. Nil UUID，值为 00000000-0000-0000-0000-000000000000 所有位为 0。
  2. 版本 1（日期时间和MAC地址），根据 60-bit 的时间戳和节点（生成 UUID 的计算机）的 48-bit MAC 地址而生成。
  3. 版本 2（日期时间和MAC地址，DCE安全版本），RFC 4122 保留了版本 2 的 UUID 用于“DCE security”。
  4. 版本 3 和版本 5（基于名字空间名称），“版本3” 和 “版本5” 的 UUID 通过散列（hashing）名字空间标识和名称生成。版本 3 使用 MD5 作为散列算法，版本 5 使用 SHA1。
  5. 版本 4（随机），UUID 是随机生成的。

UUID 格式

UUID 的 16 个 8 位字节表示为 32 个十六进制的数字，有连字符 '-' 分隔成五组显示，形式为 "8-4-4-4-12" 总共 36 个字符（32 个十六进制数字和 4 个连字符）。

例如：

123e4567-e89b-12d3-a456-426655440000 // xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

四位数字 M 表示 UUID 的版本，数字 N 的一至三个最高有效位表示 UUID 变体。

具体布局：

名称 长度（字节） 长度（16进制数字码长） 说明
time_low 4 8 整数：低位 32 bits 时间
time_mid 2 4 整数：中间位 16 bits 时间
time_hi_and_version 2 4 最高有效位中的 4 bits “版本”，后面是高 12 bits 的时间
clock_seq_hi_and_resclock_seq_low 2 4 最高有效位为 1-3 bits “变体”，后跟 13-15 bits 时钟徐序列
node 6 12 48 bits 节点 ID

这些字段对应于 “版本1” 和 “版本2”（基于时间的）UUID 中的字段，但是 “8-4-4-4-12” 的表示适用于所有的 UUID。

简单使用

JDK 提供了 4 种方式来生成 UUID：

  1. UUID::randomID()，这是版本 4 的静态方法。
  2. UUID::nameUUIDFromBytes(byte[] name) 版本 3 的静态方法。
  3. UUID::formString(String name) 解析 8-4-4-4-12 格式的字符串返回 UUID 实例。
  4. UUID(long mostSigBits, long leastSigBits) 低层次构造器，不常用。

例子：

UUID randomUUID = UUID.randomUUID();
UUID md5UUID = UUID.nameUUIDFromBytes("test".getBytes());
UUID fromStrUUID = UUID.fromString("1b8ea3b4-0c6e-4a63-8d77-bcb5acd2c087");

System.out.println(randomUUID); // 9f68d89b-b465-4693-a3d0-906096f5868b
System.out.println(md5UUID); // 098f6bcd-4621-3373-8ade-4e832627b4f6
System.out.println(fromStrUUID); // 1b8ea3b4-0c6e-4a63-8d77-bcb5acd2c087

各种 Getter：

  1. getLeastSignificantBits() 获取 leastSigBits。
  2. getMostSignificantBits() 获取 mostSigBits。
  3. version() 获取版本号。
  4. variant() 获取变体。

下面两个方法调用会报错（如果不是版本 1 会报 UnsupportedOperationException）：

  1. timestamp() 获取 timestamp。
  2. clockSequence() 获取 clock sequence。

JDK 中的实现

UUID 被 final 修饰，继承 Serializable 和 Comparable 接口，说明有以下特性：

  1. 不可变。
  2. 可序列化和反序列化。
  3. 不同 UUID 实例之间可以进行比较。

属性和构造函数

JDK 只提供版本 3 和版本 4 的实现，但是采用了 UUID 规范中的字段定义，长度 128 bit，在 JDK 中采用两个 long 类型的整数来存储：

// The most significant 64 bits of this UUID.
private final long mostSigBits;

// The least significant 64 bits of this UUID.
private final long leastSigBits;

具体布局如下：

名称 bit 长度 长度（16进制数字码长）
time_low 32 8
time_mid 16 4
version 4 1
time_hi 12 3
variant 2 小于 1
clock_seq 14 variant 和 clock_seq 加起来 4
node 48 12

其他的成员和构造函数：

// Java 语言访问类，UUID 的 toString() 将实例格式化成 "8-4-4-4-12" 格式，委托到 Long.fastUUID() 方法。
private static final JavaLangAccess jla = SharedSecrets.getJavaLangAccess();

// 用于版本 4 UUID 生成安全随机数。
private static class Holder {
    static final SecureRandom numberGenerator = new SecureRandom();
}

// 用指定的长度 16 的字节数组来初始化 mostSigBits 和 leastSigBits。
private UUID(byte[] data) {
	long msb = 0;
	long lsb = 0;
	assert data.length == 16 : "data must be 16 bytes in length";
	for (int i=0; i<8; i++)
		msb = (msb << 8) | (data[i] & 0xff);
	for (int i=8; i<16; i++)
		lsb = (lsb << 8) | (data[i] & 0xff);
	this.mostSigBits = msb;
	this.leastSigBits = lsb;
}

// 直接指定 mostSigBits 和 leastSigBits 构造 UUID 实例。
public UUID(long mostSigBits, long leastSigBits) {
	this.mostSigBits = mostSigBits;
	this.leastSigBits = leastSigBits;
}

私有构造器中涉及到一些位运算：

long msb = 0;
long lsb = 0;
assert data.length == 16 : "data must be 16 bytes in length";
for (int i=0; i<8; i++)
	msb = (msb << 8) | (data[i] & 0xff);
for (int i=8; i<16; i++)
	lsb = (lsb << 8) | (data[i] & 0xff);
this.mostSigBits = msb;
this.leastSigBits = lsb;

mostSigBits 由数组的低 8 位转换而来，lastSigBits 由数组的高 8 位转换而来，中间变量 msb 和 lsb 在提取字节位进行计算是：

  • 先进行左移 8 位确保需要计算的位为 0，已经计算好的位位移到左边。
  • 需要提取的字节 data[i] 的 8 位和 0xff 进行 & 运算，确保不足 8 位的高位补充为 0，超过 8 位的高位会被截断。
  • 前面两步的结果再进行 | 运算。

模拟过程：

// 只看字节数组的前 4 个字节，同样的 long 类型也只看前 4 个 字节。
// 0xff = 1111_1111
// long msb = 0  = (0000_0000 0000_0000 0000_0000 0000_0000)
// byte[] data => 0000_0001 0000_0010 0000_0100 0000_1000

// i = 0 (第一轮循环)
// msb << 8 = 0000_0000 0000_0000 0000_0000 0000_0000
// data[i] & 0xff = 0000_0001 & 1111_1111 = 0000_0001
// (msb << 8) | (data[i] & 0xff) = 0000_0000 0000_0000 0000_0000 0000_0001

// msb = 0000_0000 0000_0000 0000_0000 0000_0001

// i = 1 (第二轮循环)
// msb << 8 = 0000_0000 0000_0000 0000_0001 0000_0000
// data[i] & 0xff = 0000_0010 & 1111_1111 = 0000_0010
// (msb << 8) | (data[i] & 0xff) = 0000_0000 0000_0000 0000_0001 0000_0010

// msb = 0000_0000 0000_0000 0000_0001 0000_0010

// i = 2 (第三轮循环)
// msb << 8 = 0000_0000 0000_0001 0000_0010 0000_0000
// data[i] & 0xff = 0000_0100 & 1111_1111 = 0000_0100
// (msb << 8) | (data[i] & 0xff) = 0000_0000 0000_0001 0000_0010 0000_0100

// msb = 0000_0000 0000_0001 0000_0010 0000_0100

// i = 3 (第四轮循环)
// msb << 8 = 0000_0001 0000_0010 0000_0100 0000_0000
// data[i] & 0xff = 0000_1000 & 1111_1111 = 0000_1000
// (msb << 8) | (data[i] & 0xff) = 0000_0001 0000_0010 0000_0100 0000_1000

// msb = 0000_0001 0000_0010 0000_0100 0000_1000

执行结束后，byte 数组的所有位都设置到 mostSigBits 和 leastSigBits 。

随机数版本实现

public static UUID randomUUID() {
        // 获取随机数生成器
	SecureRandom ng = UUID.Holder.numberGenerator;

	byte[] randomBytes = new byte[16];
       // 将随机数填充到长度为 16 的字节数组
	ng.nextBytes(randomBytes);
       // 设置为 version 4
	randomBytes[6]  &= 0x0f;
	randomBytes[6]  |= 0x40;
        // 设置为 IETF variant
	randomBytes[8]  &= 0x3f;
	randomBytes[8]  |= 0x80;
	return new UUID(randomBytes);
}

这里涉及到设置 version 和 variant 的位运算：

假设 randomBytes[6] = 1011_0101
randomBytes[6] &= 0x0f => 1011_0101 & 0000_1111 => 0000_0101
randomBytes[6] |= 0x40 => 0000_0101 | 0100_0000 => 0100_0101
version => 0100 // 等价于十进制 4

假设 randomBytes[8] = 1010_0011
randomBytes[6] &= 0x3f => 1010_0011 & 0011_1111 => 0010_0011
randomBytes[6] |= 0x80 => 0010_0011 | 1000_0000 => 1010_0011
variant => 10(2bit) // 等价于十进制 2

random 版本的 UUID 依赖于 SecureRandom 生成随机数组，SecureRandom 可以生成安全随机数而非伪随机数。

总结一下 random 版本 UUID 生成过程：

  • 生成长度为 16 的随机数组。
  • 重置 version 和 variant。
  • 将重置好的随机数组设置到 mostSigBits 和 lastSigBits。

MD5 版本实现

public static UUID nameUUIDFromBytes(byte[] name) {
	MessageDigest md;
	try {
		md = MessageDigest.getInstance("MD5");
	} catch (NoSuchAlgorithmException nsae) {
		throw new InternalError("MD5 not supported", nsae);
	}
	byte[] md5Bytes = md.digest(name);
	md5Bytes[6]  &= 0x0f;
	md5Bytes[6]  |= 0x30;
	md5Bytes[8]  &= 0x3f;
	md5Bytes[8]  |= 0x80;
	return new UUID(md5Bytes);
}

根据传入的 byte 数组使用 MD5 算法生成摘要 byte 数组，这个数组的长度刚好也是 16。设置 version 和 variant 的方式和生成随机 UUID 的方式类似。

总结一下 MD5 版本 UUID 生成过程：

  • 根据传入的 byte 数组使用 MD5 算法生成摘要字节数组。
  • 重置 version 和 variant。
  • 将重置好的摘要数组设置到 mostSigBits 和 lastSigBits。

MD5 版本的 UUID 依赖于 MD5 算法，这导致只要传入相同的 byte 数组生成相同的 UUID。

toString() 方法

private static final JavaLangAccess jla = SharedSecrets.getJavaLangAccess();

public String toString() {
	return jla.fastUUID(leastSigBits, mostSigBits);
}

// jdk.internal.access.JavaLangAccess.fastUUID
public String fastUUID(long lsb, long msb) {
	return Long.fastUUID(lsb, msb);
}

//java.lang.Long.fastUUID()
static String fastUUID(long lsb, long msb) {
	if (COMPACT_STRINGS) {
		byte[] buf = new byte[36];
		formatUnsignedLong0(lsb,        4, buf, 24, 12);
		formatUnsignedLong0(lsb >>> 48, 4, buf, 19, 4);
		formatUnsignedLong0(msb,        4, buf, 14, 4);
		formatUnsignedLong0(msb >>> 16, 4, buf, 9,  4);
		formatUnsignedLong0(msb >>> 32, 4, buf, 0,  8);

		buf[23] = '-';
		buf[18] = '-';
		buf[13] = '-';
		buf[8]  = '-';

		return new String(buf, LATIN1);
	} else {
		byte[] buf = new byte[72];

		formatUnsignedLong0UTF16(lsb,        4, buf, 24, 12);
		formatUnsignedLong0UTF16(lsb >>> 48, 4, buf, 19, 4);
		formatUnsignedLong0UTF16(msb,        4, buf, 14, 4);
		formatUnsignedLong0UTF16(msb >>> 16, 4, buf, 9,  4);
		formatUnsignedLong0UTF16(msb >>> 32, 4, buf, 0,  8);

		StringUTF16.putChar(buf, 23, '-');
		StringUTF16.putChar(buf, 18, '-');
		StringUTF16.putChar(buf, 13, '-');
		StringUTF16.putChar(buf,  8, '-');

		return new String(buf, UTF16);
	}
}

// java.lang.Long.formatUnsignedLong0UTF16
private static void formatUnsignedLong0UTF16(long val, int shift, byte[] buf, int offset, int len) {
	int charPos = offset + len;
	int radix = 1 << shift;
	int mask = radix - 1;
	do {
		StringUTF16.putChar(buf, --charPos, Integer.digits[((int) val) & mask]);
		val >>>= shift;
	} while (charPos > offset);
}

// 将 long 型 val 的每 shift 比特转变到 buf 数组中，具体转变的起始位和次数由 offset 和 len 决定
// java.lang.Long#formatUnsignedLong0
static void formatUnsignedLong0(long val, int shift, byte[] buf, int offset, int len) {
	int charPos = offset + len;
	int radix = 1 << shift;
	int mask = radix - 1;
	do {
		buf[--charPos] = (byte)Integer.digits[((int) val) & mask];
		val >>>= shift;
	} while (charPos > offset);
}

调用链：UUID::toString() => JavaLangAccess::fastUUID(long lsb, long msb) => Long::fastUUID(long lsb, long msb)，其中 Long::fastUUID(long lsb, long msb) 将 lsb 和 msb 的所有位设置到 byte 数组中，而整个转换过程的最终结果为：

  1. lsb 的低 48 比特达代表 node，转变为 12 个 16 进制字符，位置在 [24, 35]。
  2. lsb 的高 16 比特代表 variant_and_sequence，转变为 4 个 16 进制字符，位置在 [19, 22]。
  3. msb 的低 16 比特代表 time_high_and_version，转变为 4 个 16 进制字符，位置在 [14, 17]。
  4. msb 的中间 16 比特代表 time_mid，转变为 4 个 16 进制字符，位置是 [14, 17]。
  5. msb 的高 32 比特代表 time_low，转变为 8 个 16 进制字符，位置是 [0, 7]。

hashCode()、equals()、compareTo() 方法

// 基于 mostSigBits 和 lastSigBits 做异或得到中间变量 hilo，再以 32 为因子进行计算
public int hashCode() {
	long hilo = mostSigBits ^ leastSigBits;
	return ((int)(hilo >> 32)) ^ (int) hilo;
}

// 直接比较 mostSigBits 和 lastSigBits 值，完全相等的时候返回 true
public boolean equals(Object obj) {
	if ((null == obj) || (obj.getClass() != UUID.class))
		return false;
	UUID id = (UUID)obj;
	return (mostSigBits == id.mostSigBits &&
			leastSigBits == id.leastSigBits);
}

// 先比较 mostSigBits 如果相等则继续比较 lastSigBits
public int compareTo(UUID val) {
	return (this.mostSigBits < val.mostSigBits ? -1 :
			(this.mostSigBits > val.mostSigBits ? 1 :
					(this.leastSigBits < val.leastSigBits ? -1 :
							(this.leastSigBits > val.leastSigBits ? 1 :
									0))));
}

参考

  1. JDk 11 源码

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.