1. 首頁
  2. 問答
  3. Java：地圖中的內部數據結構

Java：地圖中的內部數據結構

2010-07-15 32 views
4

我想創建一個實現Map接口的類。所以我正在編寫代碼來檢查調用對象是否爲空。不過，我對我應該在內部使用哪種數據結構有點困惑。目前我正在使用哈希表。 在此先感謝Java：地圖中的內部數據結構

來源

2010-07-15 Rohan

回答

4

從Wikipedia，

關聯數組通常用於 時查找是最常見的 操作。出於這個原因， 實現通常設計 以實現快速的查找，犧牲較慢插入 和比其它數據 結構（如協會 列表）的較大 存儲足跡。

高效表示：
主要有兩種有效的數據用於表示 關聯數組，哈希表和 的平衡樹 （ 結構，諸如紅 - 黑樹或AVL 樹）。跳過列表也是 的替代方案，雖然相對較新並且沒有被廣泛使用的 。還可以使用B樹（和 變體），並且當關聯 陣列太大而不能在內存中完全駐留 時，例如在簡單的 數據庫中，通常使用B樹（和 變體）。相對優勢和 缺點包括：

  1. 漸近運行性能：哈希表有更快的平均查找 和插入時間，O（1），相比 平衡二叉搜索樹的Θ（日誌 N），而與Θ（n）相比，平衡樹具有更快的最壞情況查找和插入時間 O（log n）。跳過 列表具有O（n）最差情況和O（log n）平均情況下的操作時間，但 具有較少的插入和刪除 實際開銷比平衡 二叉樹。

  2. 訂購保鮮：平衡二叉樹和跳錶保存 排序 - 允許一個有效 遍歷鍵，以便或者 有效地定位關聯 其主要是最近的給定值。 哈希表不保留訂購 ，因此無法有效執行這些操作（它們的 要求數據在 單獨的步驟中進行排序）。

  3. 範圍查詢：平衡二叉樹可以很容易地適應 有效的單個值分配給鍵的 大範圍有序，或者 計數以有序 範圍的鍵的數目。 （對於數組 中的n個元素並在連續的m個密鑰範圍上執行操作，平衡的二叉樹將花費O（log（n）+ m）時間 ，而散列表將需要Θ（n） 因爲它需要搜索整個 表時間）

  4. 分配行爲：用開尋址存儲哈希表中 所有數據的存儲器 不經常重新分配一個大的連續的塊， 而樹的分配執行許多 小，頻繁分配。其結果 哈希表可能難以 分配在分段的堆，並 相反地樹木可能導致堆 碎片。樹也更容易 分配器的低效率 。緊湊性：散列表可以具有更小的存儲空間，用於小值 類型，特別是當值爲 位時。

  5. 持久性：有簡單的持久版本的平衡二進制 樹，在功能語言中尤其突出 。

  6. 支持新的密鑰類型：建立一個哈希表需要的密鑰類型，其中 可能很難寫不好一個合理 哈希函數，而 平衡二叉樹和跳錶 只需要在總體排序 鍵。

有時簡單 一個數據結構或其它的實施方式中具有 缺點可由 更好的設計來克服。例如：使用不受信任的輸入作爲鍵可能易受 其中一個 不可信用戶提供數據旨在 以產生大量的 碰撞拒絕服務攻擊

  • 哈希表。這可以通過 隨機從 選擇哈希函數的通用家庭，或通過散列 不可信的輸入用插入之前加密 散列函數來克服。

  • 簡單的平衡樹浪費指針和分配 元空間;這些問題可以通過在每個節點中存儲多個 元素並通過使用 內存池得到緩解。

來源

2010-07-15 05:59:20 missingfaktor

2

除了表格本身，您還可以維護一個整數成員變量來跟蹤集合的大小，每次放入新的映射時遞增一次，每次刪除時遞減一次。通過這種方式，可以簡化size和isEmpty接口方法：

public int size() { 
    return this.size; 
} 

public boolean isEmpty() { 
    return this.size == 0; 
}

來源

2010-07-15 04:47:20 maerics

相關問題

 相關問題