只遍歷地圖的一部分

我將數據存儲在一個HashMap中，我想通過多個線程同時訪問該HashMap來拆分對這些項目所做的工作。只遍歷地圖的一部分

通常情況下（與例如列表）我只是想給每個線程開始的索引，可能容易裂開這樣的工作：

for(int i = startIndex; i < startIndex+batchSize && i < list.size(); i++) 
{ 
    Item a = list.get(i); 
    // do stuff with the Item 
}

當然有一個HashMap這並不工作，因爲我無法通過索引訪問它。

是否有一種簡單的方法來遍歷地圖的一部分？我應該爲這種情況使用另一種數據結構嗎？

我閱讀了關於SortedMap的內容，但它有太多的開銷，我不需要（排序項目）。我有很多數據，性能至關重要。

任何提示將不勝感激。

來源

2011-07-10 magnattic

你會如何分割地圖？ – skaffman

不知道我得到的問題。 :)我想將地圖分割成與我擁有的線程數（例如8）一樣多的部分。如果可能的話，分配不應該是一個代價高昂的操作。 – magnattic

define *很多數據* ... –

如果你只進行遍歷幾次，或者如果地圖沒有改變，你可以得到一組鍵，然後將它發送到一個數組。從那裏它幾乎是你的常規方法。但顯然如果HashMap發生了變化，那麼你將不得不再次做這兩個操作，這可能會非常昂貴。

來源

2011-07-10 22:19:47

幸運的是，線程不會更改HashMap。假設toArray（）方法便宜，你的方法聽起來不錯。試一試，看看錶現有多好，歡呼。 – magnattic

首先，你不應該使用HashMap，因爲迭代順序是未定義的。請使用LinkedHashMap，其迭代順序與插入順序（至少已定義）相同，或使用TreeMap，其迭代順序爲自然排序順序。我會推薦LinkedHashMap，因爲插入一個條目會使地圖變得不可預知。

瓜分地圖，使用此代碼：

LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>(); 

    for (Map.Entry<Integer, String> entry : new ArrayList<Map.Entry<Integer,String>>(map.entrySet()).subList(start, end)) { 
     Integer key = entry.getKey(); 
     String value = entry.getValue(); 
     // Do something with the entry 
    }

我在林立的代碼，但擴大了它等同於：

List<Map.Entry<Integer, String>> entryList = new ArrayList<Map.Entry<Integer,String>>(); 
entryList.addAll(map.entrySet()); 
entryList = entryList.subList(start, end); // You provide the start and end index 
for (Map.Entry<Integer, String> entry : entryList) ...

來源

2011-07-10 22:28:16 Bohemian

TreeMap不是一個選項，因爲這些項目的排序是一個性能殺手，我不需要特殊的項目順序。如果Map在我使用它時沒有改變，我還應該使用LinkedHashMap嗎？我不在乎項目的順序，那爲什麼它被定義爲重要？ – magnattic

Anywho，感謝您使用entryList解決方案。將它與羅斯拉森的想法進行比較，看看更快的表現。 :) – magnattic

因爲如果你在一個線程中要求項目1到5，而在另一個線程中要求項目6到10，那麼你可以在兩個項目中獲得相同的項目 - 迭代次序沒有爲hashmap定義（儘管它可能是固定的 - 你可以試試看） – Bohemian

用的HashMap＃中的keySet - >設置＃toArray你會得到一個鍵數組。

有了這個數組，您可以像以前一樣繼續，保存鍵數組並將它們傳遞給您的線程。然後，每個線程將只訪問已分配的鍵，最後您可以僅使用這些鍵訪問HashMap的給定分區的條目。

來源

2011-07-10 22:30:32 emboss

+1 entrySet（）。toArray（） - 好主意！我沒有想到這一點！ – Bohemian

謝謝！我之前並不瞭解這個問題:)這就是偉大的事情 - 你在思考問題時學到了很多東西。我就像「嗯，如果Set有一個toArray？」 - 檢查了JavaDoc - 它有:) – emboss

除非您的地圖是巨大的，否則迭代在地圖上的成本與在另一個線程上開始任務的成本相比是微不足道的，並且與您打算做的工作相比是微不足道的。

由於這個原因，最簡單的分割工作的方法很可能就是將地圖變成數組並將其分解。

final Map<K, V> map = 
final ExecutorServices es = 
final int portions = Runtime.getRuntime().availableProcessors(); 
final Map.Entry<K,V>[] entries = (Map.Entry<K,V>[]) map.entrySet().toArray(new Map.Entry[map.size()]); 
final int portionSize = (map.size() + portions-1)/ portions; 

for(int i = 0; i < portions; i++) { 
    final int start = i * portionSize; 
    final int end = Math.min(map.size(), (i + 1) * portionSize); 
    es.submit(new Runnable() { 
     public void run() { 
      for(int j=start; j<end;j++) { 
       Map.Entry<K,V> entry = entries[j]; 
       // process entry. 
      } 
     } 
    }); 
}

來源

2011-07-11 08:28:05

只遍歷地圖的一部分

回答

相關問題