有效的方法顛倒了映射到相同值的少數鍵映射hashmap

我有一個散列映射，我知道一些鍵映射到相同的值。
這些鍵的數量非常小（小於6％），它們映射在2-4個值之間。
例如有效的方法顛倒了映射到相同值的少數鍵映射hashmap

Map<String, String> map = new HashMap<>(); 
map.put("codeA", "100"); 
map.put("codeB", "7"); 
map.put("codeC", "0012");

我需要建立從值此映射到按鍵的逆所以我做：

inverseMap = new HashMap<String, ArrayList<String>>(); 
for(Map.Entry<String, String> e:map.entrySet()) { 
    String code = e.getKey(); 
    String val = e.getValue(); 
    ArrayList<String> codesColliding = inverseMap.get(val); 
    if(codesColliding == null) { 
     codesColliding = new ArrayList<>(4); 
     inverseMap.put(val, codesColliding); 
    } 
    codesColliding.add(code); 
}

這工作，但我認爲這是不理想的，因爲我使用比需要更多的內存絕大多數的鑰匙。
雖然從編碼角度來看，它的工作原理我想知道這是否可以被不同走近
注（通過其他數據結構）：我感興趣的是普通的Java 7（沒有額外的庫）接近

來源

2015-10-09 Jim

爲什麼當它在每次迭代之間被重新分配時，會添加到'codesColliding'對象？ – Tgsmith61591

@ Tgsmith61591因爲對'codesColliding'的引用在地圖中。 –

對不起，誤讀反映圖爲'HashMap '，而不是ArrayList。 D'哦！ – Tgsmith61591

如果逆映射的值需要能夠容納來自原始映射的多個鍵，那麼當它們不需要如此適應時，相對於這種情況是不會避免一些開銷的。你目前的做法並不差，但如果原始地圖的價值如此小的一部分重複，並且沒有重複超過幾次，那麼我會更加吝嗇你使用的列表的初始容量作爲逆映射中的值。爲什麼預先分配多於一個元素？你很少需要重新分配，但是當你這樣做時，這個列表將會透明地處理它。

來源

2015-10-09 19:09:09

關於'ArrayList'容量的好處。這是您可以在不使設計複雜化的情況下做出的簡單改變。 –

我在想''ArrayList（1）'比'String'大得多。 '字符串'是40字節的開銷iirc。我不確定''ArrayList [1]'佔據了多少內存' – Jim

@Jim，'ArrayList'和'String'的相對大小是無關緊要的，因爲'String'不是逆的值的可行類型地圖。 –

也許最簡單的方法是創建一個具有兩個HashMaps的類，一個用於非碰撞鍵，另一個用於碰撞的鍵。如果您以某種方式消除衝突（例如，您總是按字母順序選擇第一個），您可以將該邏輯添加到課程中。或者，如果你想返回ArrayLists，你可以懶惰地將非碰撞字符串包裝到一個ArrayList中。

這就是要知道你想要做的地圖。如果您確信您的代碼可以處理String和ArrayList結果之間的歧義，那麼您甚至可以犧牲某種類型的安全性。

來源

2015-10-09 19:04:25 spirographer

我知道你在說的是Map<String,String>，但只是爲了清楚起見，我們將其推廣到Map<K,V>，從中構建Map<V,Collection<K>>。添加另一個Map<V,K>，或許稱之爲uniqueInverseMap。在掃描條目時，請始終在inverseMap，然後uniqueInverseMap中首先檢查密鑰。如果它已在uniqueInverseMap中，請將其刪除，創建一個新的兩元素列表，將該列表添加到inverseMap。

來源

2015-10-09 19:16:51 david

有效的方法顛倒了映射到相同值的少數鍵映射hashmap

回答

相關問題