冷飯新炒：理解JDK中UUID的底層實(shí)現(xiàn)

前提

UUID是Universally Unique IDentifier的縮寫(xiě)，翻譯為通用唯一標(biāo)識(shí)符或者全局唯一標(biāo)識(shí)符。對(duì)于UUID的描述，下面摘錄一下規(guī)范文件A Universally Unique IDentifier (UUID) URN Namespace中的一些描述：

?

UUID（也稱(chēng)為GUID）定義了統(tǒng)一資源名稱(chēng)命名空間。UUID的長(zhǎng)度為128比特，可以保證在空間和時(shí)間上的唯一性。

?

「動(dòng)機(jī)：」

?

使用UUID的主要原因之一是不需要集中式管理，其中一種格式限定了IEEE 802節(jié)點(diǎn)標(biāo)識(shí)符，其他格式無(wú)此限制。可以自動(dòng)化按需生成UUID，應(yīng)用于多重不同的場(chǎng)景。UUID算法支持極高的分配速率，每臺(tái)機(jī)器每秒鐘可以生成超過(guò)1000萬(wàn)個(gè)UUID，因此它們可以作為事務(wù)ID使用。UUID具有固定大小128比特，與其他替代方案相比，它具有體積小的優(yōu)勢(shì)，非常適用于各種排序、散列和存儲(chǔ)在數(shù)據(jù)庫(kù)中，具有編程易用性的特點(diǎn)。

?

這里只需要記住UUID幾個(gè)核心特定：

• 全局時(shí)空唯一性
• 固定長(zhǎng)度128比特，也就是16字節(jié)(1 byte = 8 bit)
• 分配速率極高，單機(jī)每秒可以生成超過(guò)1000萬(wàn)個(gè)UUID（實(shí)際上更高）

下面就JDK中的UUID實(shí)現(xiàn)詳細(xì)分析一下UUID生成算法。編寫(xiě)本文的時(shí)候選用的JDK為JDK11。

再聊UUID

前面為了編寫(xiě)簡(jiǎn)單的摘要，所以只粗略摘錄了規(guī)范文件里面的一些章節(jié)，這里再詳細(xì)聊聊UUID的一些定義、碰撞概率等等。

UUID定義

UUID是一種軟件構(gòu)建的標(biāo)準(zhǔn)，也是開(kāi)放軟件基金會(huì)組織在分布式計(jì)算環(huán)境領(lǐng)域的一部分。提出此標(biāo)準(zhǔn)的目的是：讓分布式系統(tǒng)中的所有元素或者組件都有唯一的可辨別的信息，因?yàn)闃O低沖突頻率和高效算法的基礎(chǔ)，它不需要集中式控制和管理唯一可辨別信息的生成，由此，每個(gè)使用者都可以自由地創(chuàng)建與其他人不沖突的UUID。

「UUID本質(zhì)是一個(gè)128比特的數(shù)字」，這是一個(gè)位長(zhǎng)巨大的數(shù)值，理論上來(lái)說(shuō)，UUID的總數(shù)量為2^128個(gè)。這個(gè)數(shù)字大概可以這樣估算：如果「每納秒」產(chǎn)生「1兆」個(gè)不相同的UUID，需要花費(fèi)超過(guò)100億年才會(huì)用完所有的UUID。

UUID的變體與版本

UUID標(biāo)準(zhǔn)和算法定義的時(shí)候，為了考慮歷史兼容性和未來(lái)的擴(kuò)展，提供了多種變體和版本。接下來(lái)的變體和版本描述來(lái)源于維基百科中的Versions章節(jié)和RFC 4122中的Variant章節(jié)。

目前已知的變體如下：

• 變體0xx：Reserved, NCS backward compatibility，為向后兼容做預(yù)留的變體
• 變體10x：The IETF aka Leach-Salz variant (used by this class)，稱(chēng)為Leach–Salz UUID或者IETF UUID，JDK中UUID目前正在使用的變體
• 變體110：Reserved, Microsoft Corporation backward compatibility，微軟早期GUID預(yù)留變體
• 變體111：Reserved for future definition，將來(lái)擴(kuò)展預(yù)留，目前還沒(méi)被使用的變體

目前已知的版本如下：

• 空UUID（特殊版本0），用00000000-0000-0000-0000-000000000000表示，也就是所有的比特都是0
• date-time and MAC address（版本1）：基于時(shí)間和MAC地址的版本，通過(guò)計(jì)算當(dāng)前時(shí)間戳、隨機(jī)數(shù)和機(jī)器MAC地址得到。由于有MAC地址，這個(gè)可以保證其在全球的唯一性。但是使用了MAC地址，就會(huì)有MAC地址暴露問(wèn)題。若是局域網(wǎng)，可以用IP地址代替
• date-time and MAC address, DCE security version（版本2）：分布式計(jì)算環(huán)境安全的UUID，算法和版本1基本一致，但會(huì)把時(shí)間戳的前4位置換為POSIX的UID或GID
• namespace name-based MD5（版本3）：通過(guò)計(jì)算名字和命名空間的MD5散列值得到。這個(gè)版本的UUID保證了：相同命名空間中不同名字生成的UUID的唯一性；不同命名空間中的UUID的唯一性；相同命名空間中相同名字的UUID重復(fù)生成是相同的
• random（版本4）：根據(jù)隨機(jī)數(shù)，或者偽隨機(jī)數(shù)生成UUID。這種UUID產(chǎn)生重復(fù)的概率是可以計(jì)算出來(lái)的，還有一個(gè)特點(diǎn)就是預(yù)留了6比特存放變體和版本屬性，所以隨機(jī)生成的位一共有122個(gè)，總量為2^122，比其他變體的總量要偏少
• namespace name-based SHA-1（版本5）：和版本3類(lèi)似，散列算法換成了SHA-1

其中，JDK中應(yīng)用的變體是Leach-Salz，提供了namespace name-based MD5（版本3）和random（版本4）兩個(gè)版本的UUID生成實(shí)現(xiàn)。

UUID的格式

在規(guī)范文件描述中，UUID是由16個(gè)8比特?cái)?shù)字，或者說(shuō)32個(gè)16進(jìn)制表示形式下的字符組成，一般表示形式為8-4-4-4-12，加上連接字符-一共有36個(gè)字符，例如：

##?例子
123e4567-e89b-12d3-a456-426614174000
##?通用格式
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

其中4比特長(zhǎng)度的M和1到3比特長(zhǎng)度的N分別代表版本號(hào)和變體標(biāo)識(shí)。UUID的具體布局如下：

基于這個(gè)表格畫(huà)一個(gè)圖：

「嚴(yán)重注意，重復(fù)三次」：

• 上面提到的UUID的具體布局只適用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本雖然采用了基本一樣的字段分布，但是無(wú)法獲取時(shí)間戳、時(shí)鐘序列或者節(jié)點(diǎn)ID等信息
• 上面提到的UUID的具體布局只適用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本雖然采用了基本一樣的字段分布，但是無(wú)法獲取時(shí)間戳、時(shí)鐘序列或者節(jié)點(diǎn)ID等信息
• 上面提到的UUID的具體布局只適用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本雖然采用了基本一樣的字段分布，但是無(wú)法獲取時(shí)間戳、時(shí)鐘序列或者節(jié)點(diǎn)ID等信息

?

JDK中只提供了版本3和版本4的實(shí)現(xiàn)，但是java.util.UUID的布局采用了上面表格的字段

?

UUID的碰撞幾率計(jì)算

UUID的總量雖然巨大，但是如果不停地使用，假設(shè)每納秒生成超過(guò)1兆個(gè)UUID并且人類(lèi)有幸能夠繁衍到100億年以后，總會(huì)有可能產(chǎn)生重復(fù)的UUID。那么，怎么計(jì)算UUID的碰撞幾率呢？這是一個(gè)數(shù)學(xué)問(wèn)題，可以使用比較著名的「生日悖論」解決：

上圖來(lái)源于某搜索引擎百科。剛好維基百科上給出了碰撞幾率的計(jì)算過(guò)程，其實(shí)用的也是生日悖論的計(jì)算方法，這里貼一下：

上面的碰撞幾率計(jì)算是基于Leach–Salz變體和版本4進(jìn)行，得到的結(jié)論是：

• 103萬(wàn)億個(gè)UUID中找到重復(fù)項(xiàng)的概率是十億分之一
• 要生成一個(gè)沖突率達(dá)到50%的UUID至少需要生成2.71 * 1_000_000^3個(gè)UUID

有生之年不需要擔(dān)心UUID沖突，出現(xiàn)的可能性比大型隕石撞地球還低。

UUID的使用場(chǎng)景

基本所有需要使用全局唯一標(biāo)識(shí)符的場(chǎng)景都可以使用UUID，除非對(duì)長(zhǎng)度有明確的限制，常用的場(chǎng)景包括：

• 日志框架映射診斷上下文中的TRACE_ID
• APM工具或者說(shuō)OpenTracing規(guī)范中的SPAN_ID
• 特殊場(chǎng)景下數(shù)據(jù)庫(kù)主鍵或者虛擬外鍵
• 交易ID（訂單ID）
• 等等......

JDK中UUID詳細(xì)介紹和使用

這里先介紹使用方式。前面提到JDK中應(yīng)用的變體是Leach-Salz（變體2），提供了namespace name-based MD5（版本3）和random（版本4）兩個(gè)版本的UUID生成實(shí)現(xiàn)，實(shí)際上java.util.UUID提供了四種生成UUID實(shí)例的方式：

• 最常見(jiàn)的就是調(diào)用靜態(tài)方法UUID#randomUUID()，這就是版本4的靜態(tài)工廠方法
• 其次是調(diào)用靜態(tài)方法UUID#nameUUIDFromBytes(byte[] name)，這就是版本3的靜態(tài)工廠方法
• 另外有調(diào)用靜態(tài)方法UUID#fromString(String name)，這是解析8-4-4-4-12格式字符串生成UUID實(shí)例的靜態(tài)工廠方法
• 還有低層次的構(gòu)造函數(shù)UUID(long mostSigBits, long leastSigBits)，這個(gè)對(duì)于使用者來(lái)說(shuō)并不常見(jiàn)

最常用的方法有實(shí)例方法toString()，把UUID轉(zhuǎn)化為16進(jìn)制字符串拼接而成的8-4-4-4-12形式表示，例如：

String?uuid?=?UUID.randomUUID().toString();

其他Getter方法：

UUID?uuid?=?UUID.randomUUID();
//?返回版本號(hào)
int?version?=?uuid.version();
//?返回變體號(hào)
int?variant?=?uuid.variant();
//?返回時(shí)間戳?-?這個(gè)方法會(huì)報(bào)錯(cuò)，只有Time-based?UUID也就是版本1或者2的UUID實(shí)現(xiàn)才能返回時(shí)間戳
long?timestamp?=?uuid.timestamp();
//?返回時(shí)鐘序列?-?這個(gè)方法會(huì)報(bào)錯(cuò)，只有Time-based?UUID也就是版本1或者2的UUID實(shí)現(xiàn)才能返回時(shí)鐘序列
long?clockSequence?=?uuid.clockSequence();
//?返回節(jié)點(diǎn)ID?-?這個(gè)方法會(huì)報(bào)錯(cuò)，只有Time-based?UUID也就是版本1或者2的UUID實(shí)現(xiàn)才能返回節(jié)點(diǎn)ID
long?nodeId?=?uuid.node();

可以驗(yàn)證一下不同靜態(tài)工廠方法的版本和變體號(hào)：

UUID?uuid?=?UUID.randomUUID();
int?version?=?uuid.version();
int?variant?=?uuid.variant();
System.out.println(String.format("version:%d,variant:%d",?version,?variant));
uuid?=?UUID.nameUUIDFromBytes(new?byte[0]);
version?=?uuid.version();
variant?=?uuid.variant();
System.out.println(String.format("version:%d,variant:%d",?version,?variant));
//?輸出結(jié)果
version:4,variant:2
version:3,variant:2

探究JDK中UUID源碼實(shí)現(xiàn)

java.util.UUID被final修飾，實(shí)現(xiàn)了Serializable和Comparable接口，從一般理解上看，有下面的特定：

• 不可變，一般來(lái)說(shuō)工具類(lèi)都是這樣定義的
• 可序列化和反序列化
• 不同的對(duì)象之間可以進(jìn)行比較，比較方法后面會(huì)分析

下面會(huì)從不同的方面分析一下java.util.UUID的源碼實(shí)現(xiàn)：

• 屬性和構(gòu)造函數(shù)
• 隨機(jī)數(shù)版本實(shí)現(xiàn)
• namespace name-based MD5版本實(shí)現(xiàn)
• 其他實(shí)現(xiàn)
• 格式化輸出
• 比較相關(guān)的方法

屬性和構(gòu)造函數(shù)

前面反復(fù)提到JDK中只提供了版本3和版本4的實(shí)現(xiàn)，但是java.util.UUID的布局采用了UUID規(guī)范中的字段定義，長(zhǎng)度一共128比特，剛好可以存放在兩個(gè)long類(lèi)型的整數(shù)中，所以看到了UUID類(lèi)中存在兩個(gè)long類(lèi)型的整型數(shù)值：

public?final?class?UUID?implements?java.io.Serializable,?Comparable<UUID>?{
???
????//?暫時(shí)省略其他代碼

????/*
?????*?The?most?significant?64?bits?of?this?UUID.
?????*?UUID中有效的高64比特
?????*
?????*?@serial
?????*/
????private?final?long?mostSigBits;

????/*
?????*?The?least?significant?64?bits?of?this?UUID.
?????*??UUID中有效的低64比特
?????*
?????*?@serial
?????*/
????private?final?long?leastSigBits;
????
????//?暫時(shí)省略其他代碼
}

從UUID類(lèi)注釋中可以看到具體的字段布局如下：

「高64比特mostSigBits的布局」

「低64比特leastSigBits的布局」

接著看UUID的其他成員屬性和構(gòu)造函數(shù)：

public?final?class?UUID?implements?java.io.Serializable,?Comparable<UUID>?{
???
????//?暫時(shí)省略其他代碼
????
????//?Java語(yǔ)言訪問(wèn)類(lèi)，里面存放了很多底層相關(guān)的訪問(wèn)或者轉(zhuǎn)換方法，在UUID中主要是toString()實(shí)例方法用來(lái)格式化成8-4-4-4-12的形式，委托到Long.fastUUID()方法
????private?static?final?JavaLangAccess?jla?=?SharedSecrets.getJavaLangAccess();

????//?靜態(tài)內(nèi)部類(lèi)確保SecureRandom初始化，用于版本4的隨機(jī)數(shù)UUID版本生成安全隨機(jī)數(shù)
????private?static?class?Holder?{
????????static?final?SecureRandom?numberGenerator?=?new?SecureRandom();
????}
????
????//?通過(guò)長(zhǎng)度為16的字節(jié)數(shù)組，計(jì)算mostSigBits和leastSigBits的值初始化UUID實(shí)例
????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構(gòu)造UUID實(shí)例
????public?UUID(long?mostSigBits,?long?leastSigBits)?{
????????this.mostSigBits?=?mostSigBits;
????????this.leastSigBits?=?leastSigBits;
????}

????//?暫時(shí)省略其他代碼
}

私有構(gòu)造private UUID(byte[] data)中有一些位運(yùn)算技巧：

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?<for?(int?i=8;?i<16;?i++)
????lsb?=?(lsb?<this.mostSigBits?=?msb;
this.leastSigBits?=?lsb;

輸入的字節(jié)數(shù)組長(zhǎng)度為16，mostSigBits由字節(jié)數(shù)組的前8個(gè)字節(jié)轉(zhuǎn)換而來(lái)，而leastSigBits由字節(jié)數(shù)組的后8個(gè)字節(jié)轉(zhuǎn)換而來(lái)。中間變量msb或者lsb在提取字節(jié)位進(jìn)行計(jì)算的時(shí)候：

• 先進(jìn)行左移8位確保需要計(jì)算的位為0，已經(jīng)計(jì)算好的位移動(dòng)到左邊
• 然后右邊需要提取的字節(jié)data[i]的8位會(huì)先和0xff（補(bǔ)碼1111 1111）進(jìn)行或運(yùn)算，確保不足8位的高位被補(bǔ)充為0，超過(guò)8位的高位會(huì)被截?cái)酁榈?code style="overflow-wrap: break-word;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;">8位，也就是data[i] & 0xff確保得到的補(bǔ)碼為8位
• 前面兩步的結(jié)果再進(jìn)行或運(yùn)算

一個(gè)模擬過(guò)程如下：

（為了區(qū)分明顯，筆者每4位加了一個(gè)下劃線）

（為了簡(jiǎn)答，只看字節(jié)數(shù)組的前4個(gè)字節(jié)，同時(shí)只看long類(lèi)型的前4個(gè)字節(jié)）

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?<data[i]?&?0xff?=?0000_0001?&?1111_1111?=?0000_0001
(msb?<
（第一輪?msb?=?0000_0000?0000_0000?0000_0000?0000_0001）

i?=?1（第二輪）
msb?<data[i]?&?0xff?=?0000_0010?&?1111_1111?=?0000_0010
(msb?<
（第二輪?msb?=?0000_0000?0000_0000?0000_0001?0000_0010）

i?=?2（第三輪）
msb?<data[i]?&?0xff?=?0000_0100?&?1111_1111?=?0000_0100
(msb?<
（第三輪?msb?=?0000_0000?0000_0001?0000_0010?0000_0100）

i?=?3（第四輪）
msb?<data[i]?&?0xff?=?0000_1000?&?1111_1111?=?0000_1000
(msb?<
（第四輪?msb?=?0000_0001?0000_0010?0000_0100?0000_1000）

以此類(lèi)推，這個(gè)私有構(gòu)造函數(shù)執(zhí)行完畢后，長(zhǎng)度為16的字節(jié)數(shù)組的所有位就會(huì)轉(zhuǎn)移到mostSigBits和leastSigBits中。

隨機(jī)數(shù)版本實(shí)現(xiàn)

構(gòu)造函數(shù)分析完，接著分析重磅的靜態(tài)工廠方法UUID#randomUUID()，這是使用頻率最高的一個(gè)方法：

public?static?UUID?randomUUID()?{
????//?靜態(tài)內(nèi)部類(lèi)Holder持有的SecureRandom實(shí)例，確保提前初始化
????SecureRandom?ng?=?Holder.numberGenerator;
????//?生成一個(gè)16字節(jié)的安全隨機(jī)數(shù)，放在長(zhǎng)度為16的字節(jié)數(shù)組中
????byte[]?randomBytes?=?new?byte[16];
????ng.nextBytes(randomBytes);
????//?清空版本號(hào)所在的位，重新設(shè)置為4
????randomBytes[6]??&=?0x0f;??/*?clear?version????????*/
????randomBytes[6]??|=?0x40;??/*?set?to?version?4?????*/
????//?清空變體號(hào)所在的位，重新設(shè)置為
????randomBytes[8]??&=?0x3f;??/*?clear?variant????????*/
????randomBytes[8]??|=?0x80;??/*?set?to?IETF?variant??*/
????return?new?UUID(randomBytes);
}

關(guān)于上面的位運(yùn)算，這里可以使用極端的例子進(jìn)行推演：

假設(shè)randomBytes[6]?=?1111_1111
//?清空version位
randomBytes[6]?&=?0x0f?=>?1111_1111?&?0000_1111?=?0000_1111
得到randomBytes[6]?=?0000_1111?（這里可見(jiàn)高4比特被清空為0）
//?設(shè)置version位為整數(shù)4?=>?十六進(jìn)制0x40?=>?二級(jí)制補(bǔ)碼0100_0000
randomBytes[6]?|=?0x40?=>?0000_1111?|?0100_0000?=?0100_1111
得到randomBytes[6]?=?0100_1111

結(jié)果：version位?=>?0100（4 bit）=>?對(duì)應(yīng)十進(jìn)制數(shù)4

同理

假設(shè)randomBytes[8]?=?1111_1111
//?清空variant位
randomBytes[8]?&=?0x3f?=>?1111_1111?&?0011_1111?=?0011_1111
//?設(shè)置variant位為整數(shù)128?=>?十六進(jìn)制0x80?=>?二級(jí)制補(bǔ)碼1000_0000?（這里取左邊高位2位）
randomBytes[8]?|=?0x80?=>?0011_1111?|?1000_0000?=?1011_1111

結(jié)果：variant位?=> 10（2 bit）=>?對(duì)應(yīng)十進(jìn)制數(shù)2

關(guān)于UUID里面的Getter方法例如version()、variant()其實(shí)就是找到對(duì)應(yīng)的位，并且轉(zhuǎn)換為十進(jìn)制整數(shù)返回，如果熟練使用位運(yùn)算，應(yīng)該不難理解，后面不會(huì)分析這類(lèi)的Getter方法。

「隨機(jī)數(shù)版本實(shí)現(xiàn)強(qiáng)依賴(lài)于SecureRandom生成的隨機(jī)數(shù)（字節(jié)數(shù)組）」。SecureRandom的引擎提供者可以從sun.security.provider.SunEntries中查看，對(duì)于不同系統(tǒng)版本的JDK實(shí)現(xiàn)會(huì)選用不同的引擎，常見(jiàn)的如NativePRNG。JDK11配置文件$JAVA_HOME/conf/security/java.security中的securerandom.source屬性用于指定系統(tǒng)默認(rèn)的隨機(jī)源：

這里要提一個(gè)小知識(shí)點(diǎn)，想要得到密碼學(xué)意義上的安全隨機(jī)數(shù)，可以直接使用真隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)，或者使用真隨機(jī)數(shù)產(chǎn)生器產(chǎn)生的隨機(jī)數(shù)做種子。通過(guò)查找一些資料得知「非物理真隨機(jī)數(shù)產(chǎn)生器」有：

• Linux操作系統(tǒng)的/dev/random設(shè)備接口
• Windows操作系統(tǒng)的CryptGenRandom接口

如果不修改java.security配置文件，默認(rèn)隨機(jī)數(shù)提供引擎會(huì)根據(jù)不同的操作系統(tǒng)選用不同的實(shí)現(xiàn)，這里不進(jìn)行深究。在Linux環(huán)境下，SecureRandom實(shí)例化后，不通過(guò)setSeed()方法設(shè)置隨機(jī)數(shù)作為種子，默認(rèn)就是使用/dev/random提供的安全隨機(jī)數(shù)接口獲取種子，產(chǎn)生的隨機(jī)數(shù)是密碼學(xué)意義上的安全隨機(jī)數(shù)。「一句話概括，UUID中的私有靜態(tài)內(nèi)部類(lèi)Holder中的SecureRandom實(shí)例可以產(chǎn)生安全隨機(jī)數(shù)，這個(gè)是JDK實(shí)現(xiàn)UUID版本4的一個(gè)重要前提」。這里總結(jié)一下隨機(jī)數(shù)版本UUID的實(shí)現(xiàn)步驟：

• 通過(guò)SecureRandom依賴(lài)提供的安全隨機(jī)數(shù)接口獲取種子，生成一個(gè)16字節(jié)的隨機(jī)數(shù)（字節(jié)數(shù)組）
• 對(duì)于生成的隨機(jī)數(shù)，清空和重新設(shè)置version和variant對(duì)應(yīng)的位
• 把重置完version和variant的隨機(jī)數(shù)的所有位轉(zhuǎn)移到mostSigBits和leastSigBits中

namespace name-based MD5版本實(shí)現(xiàn)

接著分析版本3也就是namespace name-based MD5版本的實(shí)現(xiàn)，對(duì)應(yīng)于靜態(tài)工廠方法UUID#nameUUIDFromBytes()：

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;??/*?clear?version????????*/
????md5Bytes[6]??|=?0x30;??/*?set?to?version?3?????*/
????md5Bytes[8]??&=?0x3f;??/*?clear?variant????????*/
????md5Bytes[8]??|=?0x80;??/*?set?to?IETF?variant??*/
????return?new?UUID(md5Bytes);
}

它的后續(xù)基本處理和隨機(jī)數(shù)版本基本一致（清空版本位的時(shí)候，重新設(shè)置為3），唯一明顯不同的地方就是生成原始隨機(jī)數(shù)的時(shí)候，采用的方式是：基于輸入的name字節(jié)數(shù)組，通過(guò)MD5摘要算法生成一個(gè)MD5摘要字節(jié)數(shù)組作為原始安全隨機(jī)數(shù)，返回的這個(gè)隨機(jī)數(shù)剛好也是16字節(jié)長(zhǎng)度的。使用方式很簡(jiǎn)單：

UUID?uuid?=?UUID.nameUUIDFromBytes("throwable".getBytes());

namespace name-based MD5版本UUID的實(shí)現(xiàn)步驟如下：

• 通過(guò)輸入的命名字節(jié)數(shù)組基于MD5算法生成一個(gè)16字節(jié)長(zhǎng)度的隨機(jī)數(shù)
• 對(duì)于生成的隨機(jī)數(shù)，清空和重新設(shè)置version和variant對(duì)應(yīng)的位
• 把重置完version和variant的隨機(jī)數(shù)的所有位轉(zhuǎn)移到mostSigBits和leastSigBits中

namespace name-based MD5版本的UUID強(qiáng)依賴(lài)于MD5算法，有個(gè)明顯的特征是如果輸入的byte[] name一致的情況下，會(huì)產(chǎn)生完全相同的UUID實(shí)例。

其他實(shí)現(xiàn)

其他實(shí)現(xiàn)主要包括：

//?完全定制mostSigBits和leastSigBits，可以參考UUID標(biāo)準(zhǔn)字段布局進(jìn)行設(shè)置，也可以按照自行制定的標(biāo)準(zhǔn)
public?UUID(long?mostSigBits,?long?leastSigBits)?{
????this.mostSigBits?=?mostSigBits;
????this.leastSigBits?=?leastSigBits;
}

//?基于字符串格式8-4-4-4-12的UUID輸入，重新解析出mostSigBits和leastSigBits，這個(gè)靜態(tài)工廠方法也不常用，里面的位運(yùn)算也不進(jìn)行詳細(xì)探究
public?static?UUID?fromString(String?name)?{
????int?len?=?name.length();
????if?(len?>?36)?{
????????throw?new?IllegalArgumentException("UUID?string?too?large");
????}
????int?dash1?=?name.indexOf('-',?0);
????int?dash2?=?name.indexOf('-',?dash1?+?1);
????int?dash3?=?name.indexOf('-',?dash2?+?1);
????int?dash4?=?name.indexOf('-',?dash3?+?1);
????int?dash5?=?name.indexOf('-',?dash4?+?1);
????if?(dash4?0?||?dash5?>=?0)?{
????????throw?new?IllegalArgumentException("Invalid?UUID?string:?"?+?name);
????}
????long?mostSigBits?=?Long.parseLong(name,?0,?dash1,?16)?&?0xffffffffL;
????mostSigBits?<<=?16;
????mostSigBits?|=?Long.parseLong(name,?dash1?+?1,?dash2,?16)?&?0xffffL;
????mostSigBits?<<=?16;
????mostSigBits?|=?Long.parseLong(name,?dash2?+?1,?dash3,?16)?&?0xffffL;
????long?leastSigBits?=?Long.parseLong(name,?dash3?+?1,?dash4,?16)?&?0xffffL;
????leastSigBits?<<=?48;
????leastSigBits?|=?Long.parseLong(name,?dash4?+?1,?len,?16)?&?0xffffffffffffL;
????return?new?UUID(mostSigBits,?leastSigBits);
}

格式化輸出

格式化輸出體現(xiàn)在UUID#toString()方法，這個(gè)方法會(huì)把mostSigBits和leastSigBits格式化為8-4-4-4-12的形式，這里詳細(xì)分析一下格式化的過(guò)程。首先從注釋上看格式是：

----

time_low?=?4?*??=>?4個(gè)16進(jìn)制8位字符
time_mid?=?2?*??=>?2個(gè)16進(jìn)制8位字符
time_high_and_version?=?4?*??=>?2個(gè)16進(jìn)制8位字符
variant_and_sequence?=?4?*??=>?2個(gè)16進(jìn)制8位字符
node?=?4?*??=>?6個(gè)16進(jìn)制8位字符

hexOctet?=?（2個(gè)hexDigit）
hexDigit?=?0-9a-F（其實(shí)就是16進(jìn)制的字符）

和前文布局分析時(shí)候的提到的內(nèi)容一致。UUID#toString()方法源碼如下：

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


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

↓↓↓↓↓↓↓↓↓↓↓↓

//?java.lang.System
private?static?void?setJavaLangAccess()?{

????SharedSecrets.setJavaLangAccess(new?JavaLangAccess()?{
????
????????public?String?fastUUID(long?lsb,?long?msb)?{
????????????return?Long.fastUUID(lsb,?msb);
????????}
}

↓↓↓↓↓↓↓↓↓↓↓↓
//?java.lang.Long
static?String?fastUUID(long?lsb,?long?msb)?{
????//?COMPACT_STRINGS在String類(lèi)中默認(rèn)為true，所以會(huì)命中if分支
????if?(COMPACT_STRINGS)?{
????????//?初始化36長(zhǎng)度的字節(jié)數(shù)組?
????????byte[]?buf?=?new?byte[36];
????????//?lsb的低48位轉(zhuǎn)換為16進(jìn)制格式寫(xiě)入到buf中?-?node?=>?位置[24,35]
????????formatUnsignedLong0(lsb,????????4,?buf,?24,?12);
????????//?lsb的高16位轉(zhuǎn)換為16進(jìn)制格式寫(xiě)入到buf中?-?variant_and_sequence??=>?位置[19,22]
????????formatUnsignedLong0(lsb?>>>?48,?4,?buf,?19,?4);
????????//?msb的低16位轉(zhuǎn)換為16進(jìn)制格式寫(xiě)入到buf中?-?time_high_and_version?=>?位置[14,17]
????????formatUnsignedLong0(msb,????????4,?buf,?14,?4);?
????????//?msb的中16位轉(zhuǎn)換為16進(jìn)制格式寫(xiě)入到buf中?-?time_mid?=>?位置[9,12]
????????formatUnsignedLong0(msb?>>>?16,?4,?buf,?9,??4);
????????//?msb的高32位轉(zhuǎn)換為16進(jìn)制格式寫(xiě)入到buf中?-?time_low?=>?位置[0,7]
????????formatUnsignedLong0(msb?>>>?32,?4,?buf,?0,??8);
????????//?空余的字節(jié)槽位插入'-'，剛好占用了4個(gè)字節(jié)
????????buf[23]?=?'-';
????????buf[18]?=?'-';
????????buf[13]?=?'-';
????????buf[8]??=?'-';
????????//?基于處理好的字節(jié)數(shù)組，實(shí)例化String，并且編碼指定為L(zhǎng)ATIN1
????????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);
????}
}

/**
?*?格式化無(wú)符號(hào)的長(zhǎng)整型，填充到字節(jié)緩沖區(qū)buf中，如果長(zhǎng)度len超過(guò)了輸入值的ASCII格式表示，則會(huì)使用0進(jìn)行填充
?*?這個(gè)方法就是把輸入長(zhǎng)整型值val，對(duì)應(yīng)一段長(zhǎng)度的位，填充到字節(jié)數(shù)組buf中，len控制寫(xiě)入字符的長(zhǎng)度，offset控制寫(xiě)入buf的起始位置
?*?而shift參數(shù)決定基礎(chǔ)格式，4是16進(jìn)制，1是2進(jìn)制，3是8位
?*/
static?void?formatUnsignedLong0(long?val,?int?shift,?byte[]?buf,?int?offset,?int?len)?{
????int?charPos?=?offset?+?len;
????int?radix?=?1?<????int?mask?=?radix?-?1;
????do?{
????????buf[--charPos]?=?(byte)Integer.digits[((int)?val)?&?mask];
????????val?>>>=?shift;
????}?while?(charPos?>?offset);
}

比較相關(guān)的方法

比較相關(guān)方法如下：

//?hashCode方法基于mostSigBits和leastSigBits做異或得出一個(gè)中間變量hilo，再以32為因子進(jìn)行計(jì)算
public?int?hashCode()?{
????long?hilo?=?mostSigBits?^?leastSigBits;
????return?((int)(hilo?>>?32))?^?(int)?hilo;
}

//?equals為實(shí)例對(duì)比方法，直接對(duì)比兩個(gè)UUID的mostSigBits和leastSigBits值，完全相等的時(shí)候返回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);
}

//?比較規(guī)則是mostSigBits高位大者為大，高位相等的情況下，leastSigBits大者為大
public?int?compareTo(UUID?val)?{
????//?The?ordering?is?intentionally?set?up?so?that?the?UUIDs
????//?can?simply?be?numerically?compared?as?two?numbers
????return?(this.mostSigBits?1?:
????????????(this.mostSigBits?>?val.mostSigBits???1?:
????????????????(this.leastSigBits?1?:
????????????????(this.leastSigBits?>?val.leastSigBits???1?:
????????????????0))));
}

所有比較方法僅僅和mostSigBits和leastSigBits有關(guān)，畢竟這兩個(gè)長(zhǎng)整型就存儲(chǔ)了UUID實(shí)例的所有信息。

小結(jié)

縱觀UUID的源碼實(shí)現(xiàn)，會(huì)發(fā)現(xiàn)了除了一些精巧的位運(yùn)算，它的實(shí)現(xiàn)是依賴(lài)于一些已經(jīng)完備的功能，包括MD5摘要算法和SecureRandom依賴(lài)系統(tǒng)隨機(jī)源產(chǎn)生安全隨機(jī)數(shù)。UUID之所以能夠成為一種標(biāo)準(zhǔn)，是因?yàn)樗哿擞?jì)算機(jī)領(lǐng)域前輩鉆研多年的成果，所以現(xiàn)在使用者才能像寫(xiě)Hello World那樣簡(jiǎn)單調(diào)用UUID.randomUUID()。

參考資料：

• RFC 4122
• 維基百科 - Universally unique identifier
• JDK11相關(guān)源碼

留給讀者的開(kāi)放性問(wèn)題：

• UUID是利用什么特性把沖突率降到極低？
• 人類(lèi)有可能繁衍到UUID全部用完的年代嗎？

（本文完 c-2-w e-a-20210129）