從JAVA中的hashmap中刪除最小的k元素

Question

我有一個對象的散列圖。每個對象都有兩個屬性（比如int length和int weight）。 我想刪除最小長度的k個元素。 這樣做的有效方法是什麼？

Answer 1

Map<K, V> map = new HashMap<>(); 

... 

Set<K> keys = map.keySet(); 
TreeSet<K> smallest = new TreeSet<>(new Comparator<K>(){ 
    public int compare(K o1, K o2) { 
     return o1.getLength() - o2.getLength(); 
    } 
}); 
smallest.addAll(keys); 
for(int x = 0; x < num; x++) { 
    keys.remove(smallest.pollFirst()); 
} 

哪裏K是你的密鑰類型，V是你的價值類型，num是你想刪除的元素數量。

如果您經常這樣做，首先使用TreeMap可能是個好主意。

Answer 2

最簡單的，但肯定不是最有效的是與創建TreeMap的實例爲你的類型提供Comparator，的putAll（）從地圖元素到您剛纔創建和刪除K-元素與keySet()幫助地圖。最後一個TreeMap不會包含K最小的元素。

Answer 3

您沒有提及您區分的屬性是鍵還是值的一部分，如果是鍵，那麼上面討論的樹形圖就是應用程序。

否則如果你需要經常這樣做，我會傾向於實現我自己的地圖，將地圖界面中的所有東西都委託給一個散列表（或適當的結構體0），覆蓋添加/刪除和必要的迭代器，然後使用添加/刪除保持的值的排序列表。

這顯然假定值不發生變化，是高度耦合到你的問題。

Answer 4

請記住，它的鍵的自然順序排序樹狀圖。因此你可以根據它的長度創建一個具有可比性的密鑰。例如（因爲我在午餐時代，代碼並不完美，但應該讓你去找你需要的東西）：

package com.trip.test;  

import java.util.SortedMap;  
import java.util.TreeMap;  

import org.slf4j.Logger;  
import org.slf4j.LoggerFactory;  

public class ComparisonTest {  

private static Logger logger = LoggerFactory.getLogger(ComparisonTest.class);  

private static String[] a = {"1","2","3","4"};  
private static String[] b = {"A","B","D"};  
private static String[] c = {"1","B","D","1","B","D"};  
/**  
* @param args  
*/  
static SortedMap<KeyWithLength, String[]> myMap = new TreeMap<KeyWithLength, String[]>();  

static {  

     myMap.put(new KeyWithLength("a", a.length), a);  
     myMap.put(new KeyWithLength("b", b.length), b);  
     myMap.put(new KeyWithLength("c", c.length), c);    
}  

public static void main(String[] args) {  

    // print Map  
    logger.info("Original Map:");  

    int i = 0;  
    for (String[] strArray: myMap.values()){  
     logger.info(String.format("*** Entry %s: ", i++));  
     printStrings(strArray);  
    }  

    // chop off 2 shortest  
    chopNShortest(myMap, 2);  

    // print Map  
    logger.info("ShortenedMap:");  

    i = 0;  
    for (String[] strArray: myMap.values()){  
     logger.info(String.format("*** Entry %s: ", i++));  
     printStrings(strArray);  
    }  

}  

static void printStrings(String[] strArray){  
    StringBuffer buf = new StringBuffer();  

    for (String str: strArray){  
     buf.append(String.format("%s, ", str));  
    }  
    logger.info(buf.toString());  
}  

static void chopNShortest(SortedMap<KeyWithLength, String[]> sortedMap, int n) {  
    // Assuming map is not unmodifiable  
    if (n <= sortedMap.size()-1){  
     for (int i = 0; i< n;i++){  
      sortedMap.remove(sortedMap.firstKey());  
     }  
    }  
}  

}  

class KeyWithLength implements Comparable<KeyWithLength> {  
private String key;  
private Integer length;  

public KeyWithLength(String key, int length) {  
    super();  
    this.key = key;  
    this.length = length;  
}  

public String getKey() {  
    return key;  
}  

public int getLength() {  
    return length;  
}  

@Override  
public int hashCode() {  
    final int prime = 31;  
    int result = 1;  
    result = prime * result + ((key == null) ? 0 : key.hashCode());  
    return result;  
}  

@Override  
public boolean equals(Object obj) {  
    if (this == obj)  
     return true;  
    if (obj == null)  
     return false;  
    if (getClass() != obj.getClass())  
     return false;  
    KeyWithLength other = (KeyWithLength) obj;  
    if (key == null) {  
     if (other.key != null)  
      return false;  
    } else if (!key.equals(other.key))  
     return false;  
    return true;  
}  

@Override  
public int compareTo(KeyWithLength another) {  
    // TODO Auto-generated method stub  
    return compare(this.length, another.length);  
}  

    public static int compare(int x, int y) {  
     return (x < y) ? -1 : ((x == y) ? 0 : 1);  
    }  

} 

輸出：

Original Map: 
*** Entry 0: 
A, B, D, 
*** Entry 1: 
1, 2, 3, 4, 
*** Entry 2: 
1, B, D, 1, B, D, 

ShortenedMap: 
*** Entry 0: 
1, B, D, 1, B, D,