Java數(shù)據(jù)結(jié)構(gòu)面試題一直都是面試官喜歡問到的問題，在我們?nèi)ッ嬖嘕ava的相關(guān)崗位時，肯定會被提問到，所以我們就需要提前做好準(zhǔn)備，輕松的去應(yīng)對：

1. 數(shù)據(jù)結(jié)構(gòu)定義

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

• 數(shù)組：物理存儲單元上連續(xù)、順序的存儲結(jié)構(gòu)
• 鏈表：鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
• 隊列：隊列(queue)是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。
• 棧：棧(stack)又名堆棧，它是一種運算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。
• 堆：堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。將根結(jié)點最大的堆叫做最大堆或大根堆，根結(jié)點最小的堆叫做最小堆或小根堆。建堆時間復(fù)雜度O(n)，堆總是滿足下列性質(zhì)：堆總是一棵完全二叉樹;堆中某個結(jié)點的值總是不大于或不小于其父結(jié)點的值;
• 散列表：(Hash table，也叫哈希表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)

2. 堆的創(chuàng)建、插入、刪除、堆排序

• 堆的插入：在已經(jīng)建成的最小堆的后面插入元素，堆的結(jié)構(gòu)可能被破壞，再向上調(diào)整使其滿足性質(zhì)。
• 堆的刪除：刪除時每次刪除堆頂元素，刪除方法：

1. 將堆中最后一個元素代替堆頂元素。
2. 將堆中元素個數(shù)減少一個，相當(dāng)于將堆中最后一個元素刪除。
3. 此時堆的結(jié)構(gòu)可能被破壞，在向下調(diào)整使其滿足性質(zhì)。

• 堆排序：

1. 將堆頂元素與第size-1個元素交換。
2. hp->size–
3. 將其余的元素調(diào)整為最小堆
4. 重復(fù)1、2、3步hp->size-1次。

3.布隆過濾器

bloom算法類似一個位圖，用來判斷某個元素(key)是否在某個集合中。和一般的位圖不同的是，這個算法無需存儲key的值，對于每個key，只需要k個比特位，每個存儲一個標(biāo)志，用來判斷key是否在集合中。

• 應(yīng)用場景：比如網(wǎng)絡(luò)爬蟲抓取時url去重，郵件提供商反垃圾黑名單Email地址去重，之所以需要k個比特位是因為我們大多數(shù)情況下處理的是字符串，那么不同的字符串就有可能映射到同一個位置，產(chǎn)生沖突。
• 優(yōu)點：不需要存儲key，節(jié)省空間
• 缺點：算法判斷key在集合中時，有一定的概率key其實不在集合中，已經(jīng)映射的數(shù)據(jù)無法刪除

4. (Tire)字典樹

• 定義：又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串(但不僅限于字符串)，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
• 3個基本性質(zhì)：

1. 根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符;
2. 從根節(jié)點到某一節(jié)點路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串;
3. 每個節(jié)點的所有子節(jié)點包含的字符都不相同。

5. 海量數(shù)據(jù)找出前K大的數(shù)

top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆(就是上面提到的最小堆)，即先將數(shù)據(jù)集按照Hash方法分解成多個小數(shù)據(jù)集，然后使用Trie樹活著Hash統(tǒng)計每個小數(shù)據(jù)集中的query詞頻，之后用小頂堆求出每個數(shù)據(jù)集中出現(xiàn)頻率最高的前K個數(shù)，最后在所有top K中求出最終的top K。

以上就是“Java工程師修煉手冊：Java數(shù)據(jù)結(jié)構(gòu)面試題”，你能回答上來嗎?如果想要了解更多的Java面試題相關(guān)內(nèi)容，可以關(guān)注動力節(jié)點Java官網(wǎng)。