从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,