[[387509]]

 其實(shí)這個(gè)問(wèn)題的完整描述是：Java 中的 PriorityQueue 實(shí)現(xiàn)，其數(shù)據(jù)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)嗎?其數(shù)據(jù)的物理結(jié)構(gòu)又是什么?

估計(jì)很多人的答案是：PriorityQueue 是線性結(jié)構(gòu)，因?yàn)?PriorityQueue 是優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)，隊(duì)列不就是線性結(jié)構(gòu)的嗎?但在 PriorityQueue 的實(shí)現(xiàn)中，其數(shù)據(jù)的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)，其物理結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)。

要弄明白這個(gè)問(wèn)題，我們必須先弄明白什么是數(shù)據(jù)的邏輯結(jié)構(gòu)，什么是數(shù)據(jù)的物理結(jié)構(gòu)。

顧名思義，數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)是怎么組織起來(lái)的，數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)是怎么存儲(chǔ)的。 數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)兩個(gè)非常重要的要素。但你知道數(shù)據(jù)有幾種邏輯結(jié)構(gòu)、幾種物理結(jié)構(gòu)嗎?

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)是如何組織起來(lái)的，反映數(shù)據(jù)元素之間的邏輯關(guān)系，它更加貼近于現(xiàn)實(shí)。 例如現(xiàn)實(shí)生活中樹干與樹葉就是樹形結(jié)構(gòu)，排隊(duì)的隊(duì)伍就是線性關(guān)系。

數(shù)據(jù)的邏輯結(jié)構(gòu)一般有四種，分別是：線性結(jié)構(gòu)、集合結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)絡(luò)結(jié)構(gòu)。 其中，我們把集合、樹形結(jié)構(gòu)、網(wǎng)絡(luò)結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)。

線性結(jié)構(gòu)

線性結(jié)構(gòu)指的是數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系。 例如：數(shù)組是一種線性結(jié)構(gòu)，其下標(biāo)與元素一一對(duì)應(yīng)。鏈表也是一種線性結(jié)構(gòu)，其元素之間是一個(gè)接著一個(gè)的。生活中有很多類似的例子，例如排隊(duì)買票的隊(duì)伍就是一個(gè)線性結(jié)構(gòu)。超市里排布整齊的商品，也是一個(gè)線性結(jié)構(gòu)。

邏輯結(jié)構(gòu)之線性結(jié)構(gòu)

集合結(jié)構(gòu)

集合結(jié)構(gòu)指的是元素之間除了「同屬一個(gè)集合」的關(guān)系之外，再無(wú)其他關(guān)系。 例如數(shù)學(xué)中的整數(shù)就是一個(gè)集合，所有小數(shù)也是一個(gè)集合。

邏輯結(jié)構(gòu)之集合

樹形結(jié)構(gòu)

樹形結(jié)構(gòu)指的是元素存在一對(duì)多的關(guān)系。 例如水果有香蕉、草莓、西瓜等，這種邏輯結(jié)構(gòu)就是樹形結(jié)構(gòu)。

邏輯結(jié)構(gòu)之線樹形結(jié)構(gòu)

網(wǎng)絡(luò)結(jié)構(gòu)

網(wǎng)絡(luò)結(jié)構(gòu)指的是元素存在多對(duì)多的關(guān)系。 網(wǎng)絡(luò)結(jié)構(gòu)也叫做網(wǎng)狀結(jié)構(gòu)，它是多對(duì)多的關(guān)系。比如城市的交通網(wǎng)絡(luò)，每棟房子與其他房子都有許多條路。

邏輯結(jié)構(gòu)之線網(wǎng)絡(luò)結(jié)構(gòu)

數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)是如何存儲(chǔ)的，反映數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為四種：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)。 一般我們將這四種物理結(jié)構(gòu)分為順序存儲(chǔ)結(jié)構(gòu)與非順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)是順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)、散列存儲(chǔ)均屬于非順序存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是：借助元素的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序存儲(chǔ)的特點(diǎn)是：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

注：有些朋友說(shuō)數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)只有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)兩種，索引存儲(chǔ)和散列存儲(chǔ)是不存在的。對(duì)此，后續(xù)我專門寫篇文章來(lái)聊聊這個(gè)事情。

順序存儲(chǔ)

順序存儲(chǔ)指的是數(shù)據(jù)在內(nèi)存當(dāng)中是按照順序存儲(chǔ)的，邏輯結(jié)構(gòu)上相鄰的元素在物理結(jié)構(gòu)上也是相鄰的。Java 中的 ArrayList 就是通過(guò)順序存儲(chǔ)的方式實(shí)現(xiàn)的。

物理結(jié)構(gòu)之順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)酱鎯?chǔ)指的是元素之間的邏輯順序，并不是通過(guò)內(nèi)存順序來(lái)分配的，而是通過(guò)一個(gè)引用組織起來(lái)的。也就是說(shuō)，邏輯上相鄰的元素，在物理存儲(chǔ)位置上是不相鄰的。Java 中的 LinkedList 就是通過(guò)鏈?zhǔn)酱鎯?chǔ)的方式實(shí)現(xiàn)的。

物理結(jié)構(gòu)之鏈?zhǔn)酱鎯?chǔ)

索引存儲(chǔ)

索引存儲(chǔ)指的是元素之間的邏輯關(guān)系，是通過(guò)一張索引表來(lái)存儲(chǔ)的。這張索引表有很多個(gè)索引項(xiàng)，每個(gè)索引項(xiàng)存儲(chǔ)兩個(gè)信息：關(guān)鍵字、數(shù)據(jù)存儲(chǔ)地址。我們通過(guò)關(guān)鍵字可以找到對(duì)應(yīng)的數(shù)據(jù)存儲(chǔ)地址。這就像書籍的目錄一樣，關(guān)鍵字就是章節(jié)名，數(shù)據(jù)存儲(chǔ)地址就是頁(yè)碼。我們通過(guò)章節(jié)名可以快速地找到對(duì)應(yīng)的頁(yè)碼，從而快速地找到書籍對(duì)應(yīng)內(nèi)容。

物理結(jié)構(gòu)之索引存儲(chǔ)

散列存儲(chǔ)

散列存儲(chǔ)也稱之為哈希存儲(chǔ)，其與索引存儲(chǔ)非常類似，都是通過(guò)索引值以及對(duì)應(yīng)的值來(lái)實(shí)現(xiàn)快速查找。唯一不同的區(qū)別是，索引存儲(chǔ)會(huì)對(duì)索引值進(jìn)行哈希。應(yīng)該說(shuō)散列存儲(chǔ)是索引存儲(chǔ)的一種更加復(fù)雜的實(shí)現(xiàn)。

物理結(jié)構(gòu)之散列存儲(chǔ)

辨別思路

看到這里，我們對(duì)數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)已經(jīng)有了基本的認(rèn)識(shí)，也知道它們的常見(jiàn)種類。那我們到底如何去判斷它們是屬于哪種邏輯結(jié)構(gòu)、哪種物理結(jié)構(gòu)呢?

拿 Java 中對(duì)于優(yōu)先級(jí)隊(duì)列的 PriorityQueue 實(shí)現(xiàn)為例。通過(guò)閱讀源碼我們得知其底層使用了二叉堆實(shí)現(xiàn)，而二叉堆本身其實(shí)就是一顆二叉樹。即對(duì)于 PriorityQueue 來(lái)說(shuō)，其數(shù)組最終是通過(guò)下圖這種邏輯結(jié)構(gòu)組織起來(lái)的，因此 PriorityQueue 的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)。

PriorityQueue 的邏輯結(jié)構(gòu)

從 PriorityQueue 的源碼，我們可以知道 PriorityQueue 的數(shù)據(jù)最終是通過(guò)一個(gè)對(duì)象數(shù)組存儲(chǔ)的，而數(shù)組的物理結(jié)構(gòu)是順序存儲(chǔ)的。因此對(duì)于 PriorityQueue 來(lái)說(shuō)，其物理結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)。

PriorityQueue 的類成員變量

通過(guò) PriorityQueue 這個(gè)例子，我們可以總結(jié)出判斷數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的思路：判斷邏輯結(jié)構(gòu)，要看數(shù)據(jù)是如何組織起來(lái)的。要判斷物理結(jié)構(gòu)，則是要看數(shù)據(jù)最終是如何存儲(chǔ)的。

如果對(duì) PriorityQueue 的源碼實(shí)現(xiàn)感興趣，可以閱讀：集合系列 Queue(九)：PriorityQueue - 陳樹義的博客

我們?cè)儆眠@個(gè)辦法來(lái)判斷一下 TreeMap 這個(gè)類。

TreeMap 是 Java 中非常經(jīng)典的實(shí)現(xiàn)，其底層是基于紅黑樹的實(shí)現(xiàn)，即其最終會(huì)將所有數(shù)據(jù)組織成一顆紅黑樹，因此 TreeMap 的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)。通過(guò)閱讀 TreeMap 的源碼，我們知道 TreeMap 的數(shù)據(jù)最終是通過(guò) Entry 這個(gè)類存儲(chǔ)的，因此 TreeMap 的物理結(jié)構(gòu)是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

TreeMap 的類成員變量

最后我們拿比較復(fù)雜的 LinkedBlockingQueue 來(lái)分析一下。

很多人會(huì)說(shuō)隊(duì)列就是一種特殊的數(shù)組，而數(shù)組是順序存儲(chǔ)的，因此隊(duì)列就是順序存儲(chǔ)的。如果將這個(gè)結(jié)論套用在 LinkedBlockingQueue 上，那是否可以得出同樣的結(jié)論，即 LinkedBlockingQueue 也是順序存儲(chǔ)的呢?

前面我們說(shuō)過(guò)：不要用直覺(jué)去判斷，而要根據(jù)定義去判斷。 即判斷數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的思路是：判斷邏輯結(jié)構(gòu)，要看數(shù)據(jù)是如何組織起來(lái)的。要判斷物理結(jié)構(gòu)，則是要看數(shù)據(jù)最終是如何存儲(chǔ)的。

LinkedBlockingQueue 是 Java 中的阻塞隊(duì)列實(shí)現(xiàn)，其最終會(huì)將數(shù)組組織成一個(gè)隊(duì)列，因此其邏輯結(jié)構(gòu)上屬于線性表。通過(guò)閱讀源碼，我們可以知道 LinkedBlockingQueue 的元素是存儲(chǔ)在 Node 節(jié)點(diǎn)上的，因此 LinkedBlockingQueue 的物理結(jié)構(gòu)屬于鏈?zhǔn)酱鎯?chǔ)。

LinkedBlockingQueue 的類成員變量

總結(jié)

本文一開始通過(guò) PriorityQueue 的例子，引入了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)這個(gè)話題。接著介紹了四種邏輯結(jié)構(gòu)：線性表、集合、樹狀結(jié)構(gòu)、網(wǎng)絡(luò)結(jié)構(gòu)。