建站
咨詢
售后
建站咨詢
新聞中心
其實這個問題的完整描述是：Java 中的 PriorityQueue 實現(xiàn)，其數(shù)據(jù)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)嗎?其數(shù)據(jù)的物理結(jié)構(gòu)又是什么?
創(chuàng)新互聯(lián)公司專注于西湖網(wǎng)站建設服務及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供西湖營銷型網(wǎng)站建設，西湖網(wǎng)站制作、西湖網(wǎng)頁設計、西湖網(wǎng)站官網(wǎng)定制、微信小程序服務，打造西湖網(wǎng)絡公司原創(chuàng)品牌,更為您提供西湖網(wǎng)站排名全網(wǎng)營銷落地服務。
估計很多人的答案是：PriorityQueue 是線性結(jié)構(gòu)，因為 PriorityQueue 是優(yōu)先級隊列的實現(xiàn)，隊列不就是線性結(jié)構(gòu)的嗎?但在 PriorityQueue 的實現(xiàn)中，其數(shù)據(jù)的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)，其物理結(jié)構(gòu)是順序存儲結(jié)構(gòu)。
要弄明白這個問題，我們必須先弄明白什么是數(shù)據(jù)的邏輯結(jié)構(gòu)，什么是數(shù)據(jù)的物理結(jié)構(gòu)。
顧名思義，數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)是怎么組織起來的，數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)是怎么存儲的。 數(shù)據(jù)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，是數(shù)據(jù)結(jié)構(gòu)兩個非常重要的要素。但你知道數(shù)據(jù)有幾種邏輯結(jié)構(gòu)、幾種物理結(jié)構(gòu)嗎?
數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)是如何組織起來的，反映數(shù)據(jù)元素之間的邏輯關系，它更加貼近于現(xiàn)實。 例如現(xiàn)實生活中樹干與樹葉就是樹形結(jié)構(gòu)，排隊的隊伍就是線性關系。
數(shù)據(jù)的邏輯結(jié)構(gòu)一般有四種，分別是：線性結(jié)構(gòu)、集合結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)絡結(jié)構(gòu)。 其中，我們把集合、樹形結(jié)構(gòu)、網(wǎng)絡結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)。
線性結(jié)構(gòu)
線性結(jié)構(gòu)指的是數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關系。 例如：數(shù)組是一種線性結(jié)構(gòu)，其下標與元素一一對應。鏈表也是一種線性結(jié)構(gòu)，其元素之間是一個接著一個的。生活中有很多類似的例子，例如排隊買票的隊伍就是一個線性結(jié)構(gòu)。超市里排布整齊的商品，也是一個線性結(jié)構(gòu)。
邏輯結(jié)構(gòu)之線性結(jié)構(gòu)
集合結(jié)構(gòu)
集合結(jié)構(gòu)指的是元素之間除了「同屬一個集合」的關系之外，再無其他關系。 例如數(shù)學中的整數(shù)就是一個集合，所有小數(shù)也是一個集合。
邏輯結(jié)構(gòu)之集合
樹形結(jié)構(gòu)
樹形結(jié)構(gòu)指的是元素存在一對多的關系。 例如水果有香蕉、草莓、西瓜等，這種邏輯結(jié)構(gòu)就是樹形結(jié)構(gòu)。
邏輯結(jié)構(gòu)之線樹形結(jié)構(gòu)
網(wǎng)絡結(jié)構(gòu)
網(wǎng)絡結(jié)構(gòu)指的是元素存在多對多的關系。 網(wǎng)絡結(jié)構(gòu)也叫做網(wǎng)狀結(jié)構(gòu)，它是多對多的關系。比如城市的交通網(wǎng)絡，每棟房子與其他房子都有許多條路。
邏輯結(jié)構(gòu)之線網(wǎng)絡結(jié)構(gòu)
數(shù)據(jù)的物理存儲結(jié)構(gòu)
數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)是如何存儲的，反映數(shù)據(jù)的存儲結(jié)構(gòu)。 數(shù)據(jù)的存儲結(jié)構(gòu)分為四種：順序存儲、鏈式存儲、索引存儲、散列存儲。 一般我們將這四種物理結(jié)構(gòu)分為順序存儲結(jié)構(gòu)與非順序存儲結(jié)構(gòu)。順序存儲是順序存儲結(jié)構(gòu)，鏈式存儲、索引存儲、散列存儲均屬于非順序存儲結(jié)構(gòu)。
數(shù)據(jù)的順序存儲結(jié)構(gòu)的特點是：借助元素的相對位置來表示數(shù)據(jù)元素之間的邏輯關系。非順序存儲的特點是：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。
注：有些朋友說數(shù)據(jù)的物理存儲結(jié)構(gòu)只有順序存儲、鏈式存儲兩種，索引存儲和散列存儲是不存在的。對此，后續(xù)我專門寫篇文章來聊聊這個事情。
順序存儲
順序存儲指的是數(shù)據(jù)在內(nèi)存當中是按照順序存儲的，邏輯結(jié)構(gòu)上相鄰的元素在物理結(jié)構(gòu)上也是相鄰的。Java 中的 ArrayList 就是通過順序存儲的方式實現(xiàn)的。
物理結(jié)構(gòu)之順序存儲
鏈式存儲
鏈式存儲指的是元素之間的邏輯順序，并不是通過內(nèi)存順序來分配的，而是通過一個引用組織起來的。也就是說，邏輯上相鄰的元素，在物理存儲位置上是不相鄰的。Java 中的 LinkedList 就是通過鏈式存儲的方式實現(xiàn)的。
物理結(jié)構(gòu)之鏈式存儲
索引存儲
索引存儲指的是元素之間的邏輯關系，是通過一張索引表來存儲的。這張索引表有很多個索引項，每個索引項存儲兩個信息：關鍵字、數(shù)據(jù)存儲地址。我們通過關鍵字可以找到對應的數(shù)據(jù)存儲地址。這就像書籍的目錄一樣，關鍵字就是章節(jié)名，數(shù)據(jù)存儲地址就是頁碼。我們通過章節(jié)名可以快速地找到對應的頁碼，從而快速地找到書籍對應內(nèi)容。
物理結(jié)構(gòu)之索引存儲
散列存儲
散列存儲也稱之為哈希存儲，其與索引存儲非常類似，都是通過索引值以及對應的值來實現(xiàn)快速查找。唯一不同的區(qū)別是，索引存儲會對索引值進行哈希。應該說散列存儲是索引存儲的一種更加復雜的實現(xiàn)。
物理結(jié)構(gòu)之散列存儲
辨別思路
看到這里，我們對數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)已經(jīng)有了基本的認識，也知道它們的常見種類。那我們到底如何去判斷它們是屬于哪種邏輯結(jié)構(gòu)、哪種物理結(jié)構(gòu)呢?
拿 Java 中對于優(yōu)先級隊列的 PriorityQueue 實現(xiàn)為例。通過閱讀源碼我們得知其底層使用了二叉堆實現(xiàn)，而二叉堆本身其實就是一顆二叉樹。即對于 PriorityQueue 來說，其數(shù)組最終是通過下圖這種邏輯結(jié)構(gòu)組織起來的，因此 PriorityQueue 的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)。
PriorityQueue 的邏輯結(jié)構(gòu)
從 PriorityQueue 的源碼，我們可以知道 PriorityQueue 的數(shù)據(jù)最終是通過一個對象數(shù)組存儲的，而數(shù)組的物理結(jié)構(gòu)是順序存儲的。因此對于 PriorityQueue 來說，其物理結(jié)構(gòu)是順序存儲結(jié)構(gòu)。
PriorityQueue 的類成員變量
通過 PriorityQueue 這個例子，我們可以總結(jié)出判斷數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的思路：判斷邏輯結(jié)構(gòu)，要看數(shù)據(jù)是如何組織起來的。要判斷物理結(jié)構(gòu)，則是要看數(shù)據(jù)最終是如何存儲的。
如果對 PriorityQueue 的源碼實現(xiàn)感興趣，可以閱讀：集合系列 Queue(九)：PriorityQueue - 陳樹義的博客
我們再用這個辦法來判斷一下 TreeMap 這個類。
TreeMap 是 Java 中非常經(jīng)典的實現(xiàn)，其底層是基于紅黑樹的實現(xiàn)，即其最終會將所有數(shù)據(jù)組織成一顆紅黑樹，因此 TreeMap 的邏輯結(jié)構(gòu)是樹形結(jié)構(gòu)。通過閱讀 TreeMap 的源碼，我們知道 TreeMap 的數(shù)據(jù)最終是通過 Entry 這個類存儲的，因此 TreeMap 的物理結(jié)構(gòu)是鏈式存儲結(jié)構(gòu)。
TreeMap 的類成員變量
最后我們拿比較復雜的 LinkedBlockingQueue 來分析一下。
很多人會說隊列就是一種特殊的數(shù)組，而數(shù)組是順序存儲的，因此隊列就是順序存儲的。如果將這個結(jié)論套用在 LinkedBlockingQueue 上，那是否可以得出同樣的結(jié)論，即 LinkedBlockingQueue 也是順序存儲的呢?
前面我們說過：不要用直覺去判斷，而要根據(jù)定義去判斷。 即判斷數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)的思路是：判斷邏輯結(jié)構(gòu)，要看數(shù)據(jù)是如何組織起來的。要判斷物理結(jié)構(gòu)，則是要看數(shù)據(jù)最終是如何存儲的。
LinkedBlockingQueue 是 Java 中的阻塞隊列實現(xiàn)，其最終會將數(shù)組組織成一個隊列，因此其邏輯結(jié)構(gòu)上屬于線性表。通過閱讀源碼，我們可以知道 LinkedBlockingQueue 的元素是存儲在 Node 節(jié)點上的，因此 LinkedBlockingQueue 的物理結(jié)構(gòu)屬于鏈式存儲。
LinkedBlockingQueue 的類成員變量
總結(jié)
本文一開始通過 PriorityQueue 的例子，引入了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)這個話題。接著介紹了四種邏輯結(jié)構(gòu)：線性表、集合、樹狀結(jié)構(gòu)、網(wǎng)絡結(jié)構(gòu)。
文章標題：PriorityQueue 是線性結(jié)構(gòu)嗎？90% 的人都搞錯了！
網(wǎng)站路徑：http://www.5511xx.com/article/dhegcod.html
