Java數據結構面試題一直都是面試官喜歡問到的問題，在我們去面試Java的相關崗位時，肯定會被提問到，所以我們就需要提前做好準備，輕松的去應對：
1. 數據結構定義
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。
- 數組：物理存儲單元上連續、順序的存儲結構
- 鏈表：鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。
- 隊列：隊列(queue)是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
- 棧：棧(stack)又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。
- 堆：堆通常是一個可以被看做一棵完全二叉樹的數組對象。將根結點最大的堆叫做最大堆或大根堆，根結點最小的堆叫做最小堆或小根堆。建堆時間復雜度O(n)，堆總是滿足下列性質：堆總是一棵完全二叉樹;堆中某個結點的值總是不大于或不小于其父結點的值;
- 散列表：(Hash table，也叫哈希表)，是根據關鍵碼值(Key value)而直接進行訪問的數據結構
2. 堆的創建、插入、刪除、堆排序
- 堆的插入：在已經建成的最小堆的后面插入元素，堆的結構可能被破壞，再向上調整使其滿足性質。
- 堆的刪除：刪除時每次刪除堆頂元素，刪除方法：
- 將堆中最后一個元素代替堆頂元素。
- 將堆中元素個數減少一個，相當于將堆中最后一個元素刪除。
- 此時堆的結構可能被破壞，在向下調整使其滿足性質。
- 堆排序：
- 將堆頂元素與第size-1個元素交換。
- hp->size–
- 將其余的元素調整為最小堆
- 重復1、2、3步hp->size-1次。
3.布隆過濾器
bloom算法類似一個位圖，用來判斷某個元素(key)是否在某個集合中。和一般的位圖不同的是，這個算法無需存儲key的值，對于每個key，只需要k個比特位，每個存儲一個標志，用來判斷key是否在集合中。
- 應用場景：比如網絡爬蟲抓取時url去重，郵件提供商反垃圾黑名單Email地址去重，之所以需要k個比特位是因為我們大多數情況下處理的是字符串，那么不同的字符串就有可能映射到同一個位置，產生沖突。
- 優點：不需要存儲key，節省空間
- 缺點：算法判斷key在集合中時，有一定的概率key其實不在集合中，已經映射的數據無法刪除
4. (Tire)字典樹
- 定義：又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和保存大量的字符串(但不僅限于字符串)，所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
- 3個基本性質：
- 根節點不包含字符，除根節點外每一個節點都只包含一個字符;
- 從根節點到某一節點路徑上經過的字符連接起來，為該節點對應的字符串;
- 每個節點的所有子節點包含的字符都不相同。
5. 海量數據找出前K大的數
top K類問題，通常比較好的方案是分治+Trie樹/hash+小頂堆(就是上面提到的最小堆)，即先將數據集按照Hash方法分解成多個小數據集，然后使用Trie樹活著Hash統計每個小數據集中的query詞頻，之后用小頂堆求出每個數據集中出現頻率最高的前K個數，最后在所有top K中求出最終的top K。
??????
??以上就是“Java工程師修煉手冊：Java數據結構面試題”，你能回答上來嗎?如果想要了解更多的Java面試題+相關內容，可以關注私信博主，也可以評論區留言~
