在定期檢查JDK中是否存在一種或另一種標(biāo)準(zhǔn)算法時，我決定進(jìn)行這種索引。 有趣的是，為什么其中包含一些著名的數(shù)據(jù)結(jié)構(gòu)或算法，而另一些卻沒有？ 此調(diào)查的格式僅涉及JDK的算法和數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵特性和功能，所有詳細(xì)信息和完整描述-您可以在javadoc或jdk源代碼中輕松找到。 讓我們從簡單開始到復(fù)雜！

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

堆

jdk中有一個堆棧 ，它是從堆棧中出現(xiàn)的-類Stack ，但不建議使用它，它很復(fù)雜又很奇怪：它繼承自Vector ，因此基于Dynamic Array并已同步。 為什么一個簡單的棧需要這一切，為什么它不只是一個接口-目前尚不清楚（討論過很多次： 1 ， 2 ），但似乎只是一個架構(gòu)的錯誤，同樣與載體本身。 順便說一句，JDK作者自己建議使用Deque 。

Deque – 雙端隊列的接口（api）（O中的LIFO + FIFO（1）），其中包括堆棧操作（push，pop，isEmpty，size），并且到目前為止在jdk中可用（1.6+） 。 當(dāng)然，將這些堆棧操作放在接口Stack中會更合乎邏輯，例如讓Deque繼承它，但是由于Stack已經(jīng)存在，并且向后兼容性是Java的“圣杯” –他們不得不犧牲常規(guī)設(shè)計。 Deque的實現(xiàn)是ArrayDeque和LinkedList ，它們也是常規(guī)隊列的實現(xiàn)者–因此我們將在后面討論。

隊列

接下來，讓我們看一下隊列數(shù)據(jù)類型 。 這里的一切都很好，設(shè)計得很好。 隊列 – FIFO隊列的接口（api），以恒定時間O（1）添加到開頭并從結(jié)尾刪除。

主要實現(xiàn)有： ArrayDeque ，基于動態(tài)可擴展數(shù)組的循環(huán)緩沖區(qū) （填充時加倍）和LinkedList （ 經(jīng)典的雙向鏈接列表） （大小不受限制）。 令人驚訝的是，第一個不支持隨機訪問 （使用索引添加/刪除/獲取），第二個卻支持O（n）時間并通過鏈表進(jìn)行迭代。 這些類還實現(xiàn)了上述Deque，因此它們支持從末尾移除并在恒定時間內(nèi)添加到頂部。

接下來，從jdk 1.5+開始，添加了PriorityQueue ，這實際上違反了合同，因為隊列元素不是從末尾檢索的（并且也不添加到頭部），而是根據(jù)優(yōu)先級檢索的。 PriorityQueue基于可擴展的二進(jìn)制堆 ，其頂部最小（根據(jù)其比較器），并且在填充時提高了1.5倍。 關(guān)鍵特征分別是：元素的添加/刪除在O（log N）中，而對最小值（標(biāo)頭）的引用在O（1）中。

其他類型的隊列是為多線程使用而設(shè)計的，它們是： BlockingQueue ， TransferQueue ， ConcurrentLinkedQueue和ConcurrentLinkedDeque 。

BlockingQueue （ ArrayBlockingQueue ， LinkedBlockingQueue ， PriorityBlockingQueue ）的實現(xiàn)是其原始版本的一種同步版本，即幾乎每個操作都是串行執(zhí)行的（具有獨占鎖定）。 對于DelayQueue也是如此：也是同步的，并且在內(nèi)部使用PriorityQueue 。

其他實現(xiàn)： SynchronousQueue ， TransferQueue （ LinkedTransferQueue ）， ConcurrentLinkedQueue ， ConcurrentLinkedDeque –基于不同的方法：它們使用基于鏈表和CAS指令的非阻塞隊列算法，這些算法在多處理器環(huán)境中可以很好地并行化。 詳細(xì)描述在源代碼中。

這類算法的理論是一個非常龐大且現(xiàn)代的話題，因此還沒有很好的標(biāo)準(zhǔn)化和結(jié)構(gòu)化，它們超出了本文的討論范圍，也不屬于另一篇文章的主題。

優(yōu)先隊列

就像從jdk 1.5+開始所說的那樣，有一個通用的PriorityQueue根據(jù)元素比較器工作。 而且，jdk中還有堆的另一種實現(xiàn)。 這是很好的舊Timer ，它是內(nèi)部類– TaskQueue（頂部的延遲最小的任務(wù)）。 當(dāng)然，這是一個私有類，除了在Timer內(nèi)部，不能使用。

清單

如您所知，有順序和/或隨機訪問類型列表。 在Java中，它是List ，主要有2種實現(xiàn)：首先-是ArrayList ，支持隨機訪問 ，基于動態(tài)可擴展數(shù)組 （填充時增加一半），但是在刪除所有元素后不會縮小，您需要調(diào)用a特殊方法（ trimToSize ）。

第二個-再次是LinkedList，它是一個雙鏈表順序訪問大小，僅受jvm的內(nèi)存限制。 盡管也存在隨機訪問（索引）的方法–如前所述，它們需要O（n）時間。

因此，java集合中沒有最簡單的鏈表實現(xiàn)，盡管這是一個好主意（鏈接的開銷減少了2倍），并且沒有簡單的堆棧。

要在多線程環(huán)境中使用列表，有幾個選項： CopyOnWriteArrayList （更改操作– O（n）），包裝器（ synchonizedList ）以及過時的Vector 。

符號表

它們在JDK中顯示為二進(jìn)制樹和哈希表。 二叉樹 –它是TreeMap （或TreeSet ）， SortedMap （也是SortedSet）的實現(xiàn)，它基于經(jīng)典的紅黑樹 ，即是平衡的，并且對于O（log N）保證了其基本操作，并且不限大小。 jdk中不存在其他類型的樹。

哈希表是HashMap （也是HashSet ），它可能是Java中最常用的結(jié)構(gòu)，它基于可動態(tài)擴展的哈希表，具有與鏈表的單獨鏈接 ，具有所有功能：性能取決于哈希函數(shù)的質(zhì)量，因此最壞的情況是O（N）。 當(dāng)大小達(dá)到預(yù)定的loadFactor時， HashMap的大小將增加一倍。 值得注意的是，為了保護(hù)錯誤的哈希函數(shù)，使用了雙哈希，并且對調(diào)用hashCode（）的結(jié)果應(yīng)用了棘手的位算法。

在JDK中，也有帶有開放地址（線性探測）的哈希表實現(xiàn)。 其中之一是IdentityHashMap ，當(dāng)鍵和值都存儲在彼此相鄰的同一數(shù)組中時，它會使用經(jīng)典線性探測的優(yōu)化版本，以實現(xiàn)更好的數(shù)據(jù)緩存（javadoc：?大型表的局部性比使用單獨的數(shù)組?）

第二種開放尋址實現(xiàn)是非常特定的：它僅用于存儲ThreadLocal元素（ ThreadLocalMap中的內(nèi)部隱藏類），當(dāng)然不可用。

還有多線程版本： ConcurrentHashMap中 ，包裝synchronizedMap ， 哈希表和ConcurrentSkipListMap 。 包裝器-自然只是阻止了常規(guī)HashMap Hashtable的版本-同一件事（并且是舊的，不建議使用）， ConcurrentHashMap-鎖條版本，減少了關(guān)鍵的鎖部分（最好閱讀JCiP ，這里是（ 摘錄 ） ConcurrentSkipListMap –是哈希表的非阻塞命名算法的改編版本（有關(guān)詳細(xì)信息，請參見源代碼）。

集合（不包含重復(fù)項）–在Java中設(shè)置 ，并通過HashMap實現(xiàn)，因此所有被稱為哈希表的對象–對HashSet有效。

圖表

圖結(jié)構(gòu)和算法未在jdk中表示。 因此，您只能為此使用第三方庫。

弦樂

java中通常有一個字符串實現(xiàn)：基于unicode字符數(shù)組。 值得一提的是，從1.7_17版本開始，由于已復(fù)制子字符串，因此子字符串的性能為O（n）。

有趣的是， 此實現(xiàn)使用了一種簡單的（強力）子字符串搜索算法，該算法在最壞的情況下以O(shè)（N * M）運行，并且沒有一些有效的算法（在有限狀態(tài)機上構(gòu)建：Knuth-Morris-Pratt等） 。

原因有幾個：字母UTF字符大（?65K），因此存儲狀態(tài)機的開銷很大，而就采用了蠻力算法（不使用額外的內(nèi)存）。 其次，在平均輸入字符串上–根據(jù)統(tǒng)計數(shù)據(jù)，該算法與其他算法相比并沒有很多。

與排序相同：有有效的基數(shù)排序字符串a(chǎn)lgs（LSD，MSD等），但是在jdk中，有一個用于字符串的標(biāo)準(zhǔn)對象排序 ，如果運行，則以O(shè)（M * N * log N）運行大部分線相差不大（M –線長）。 原因是相同的：快速計數(shù)字符串算法需要額外的UTF字母大小的數(shù)組，這使得它們在平均輸入上非常無效。

JDK算法

排序

由于jdk7發(fā)生了許多有關(guān)各種選項的更改，因此討論了很多次，關(guān)于此主題的信息和文章很多，您可以輕松地將其搜索出來。

簡而言之，這是jdk中排序?qū)崿F(xiàn)的實際列表： TimSort –默認(rèn)情況下對對象進(jìn)行排序； mergesort –還用于對象；舊版本（通過系統(tǒng)屬性啟用）； Dual-Pivot Quick sort –用于基元；然后按計數(shù)排序用于字節(jié)/字符數(shù)組，最后插入排序用于任何情況下使用的小數(shù)組。

集合內(nèi)容使用Collections.sort（List…）進(jìn)行排序，仍然可以通過將集合復(fù)制到數(shù)組中，對其進(jìn)行排序，然后相應(yīng)地覆蓋集合內(nèi)容來完成。 因此，盡管沒有開銷，對集合進(jìn)行排序仍然是不可能的，盡管我認(rèn)為擁有就地排序的鏈表是一個好主意。 Java中的字符串排序也使用對象版本完成，原因已經(jīng)提到。

正在搜尋

對于原語和對象的所有數(shù)組以及隨機訪問列表實現(xiàn)（例如ArrayList等），都存在傳統(tǒng)的二進(jìn)制搜索 。 此外，JDK中還有一個二進(jìn)制搜索鏈接列表的版本！ 令人驚訝的是：JDK沒有對鏈表進(jìn)行排序，但是對它們進(jìn)行二進(jìn)制搜索！ 盡管沒有太大意義，因為這種版本的性能為O（N）。

常用表達(dá)

為此提供了Pattern和Matcher類。 Java使用基于帶回溯的非確定性有限狀態(tài)機（ NFA ）的傳統(tǒng)實現(xiàn)。 因此，在退化的輸入上，在最壞的情況下它給出了指數(shù)復(fù)雜度 O（m ^ N），例如，在Java中運行此regexp并嘗試添加/刪除“ a”符號：“ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.aa ）* b”）

此外，還有所謂的有序交替-此功能可在找到第一個匹配項后停止搜索，但不會顯示最具體（最長）的搜索結(jié)果（ 例如 ）。

哈希函數(shù)，校驗和

jdk中有hashCode實現(xiàn)的六個版本，并且Park-Miller_random_number_generator是默認(rèn)版本，其他很簡單，例如常量或?qū)ο髢?nèi)存地址，并且不使用算法，您可以在c ++ jdk源代碼中找到它們。 MessageDigest類中還有行業(yè)標(biāo)準(zhǔn)的哈希算法（SHA-*，MD5和變體）。

對于校驗和，有Adler-32 （ javadoc ）和CRC32 （ javadoc ）算法的實現(xiàn)。

壓縮

jdk中有一個標(biāo)準(zhǔn)的壓縮deflate（ Deflater ）算法的實現(xiàn)，并且zip / gzip jdk utils使用它。 它們都在java.util.zip包中 。

摘要

如您所見，經(jīng)典數(shù)據(jù)結(jié)構(gòu)并未完全用Java呈現(xiàn)，但與此同時，幾乎所有jdk中的所有數(shù)據(jù)結(jié)構(gòu)都可以使用很多線程安全版本。 缺少的是一個懸而未決的問題。 例如，您可以爭辯jdk是否需要一些Union-Find，但是在社交網(wǎng)絡(luò)時代完全缺少該語言的圖形結(jié)構(gòu)和算法非常令人驚訝，并且實際上會產(chǎn)生許多錯誤和自行車。

參考：來自我們JCG合作伙伴 Mikhail Baturov 的JDK 7的算法和數(shù)據(jù)結(jié)構(gòu)，這是另一個俄羅斯編程人員.blog博客。

翻譯自: https://www.javacodegeeks.com/2013/07/algorithms-and-data-structures-of-jdk-7.html

總結(jié)

以上是生活随笔為你收集整理的JDK 7的算法和数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。