java - JAVAのハッシュマップから最小のk要素を削除します

Question

オブジェクトのハッシュマップがあります。各オブジェクトには2つの属性があります（たとえば、intの長さとintの重み）。最小の長さの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のインスタンスを作成し、マップから作成したばかりのマップにputAll（）要素を作成し、keySet（）を使用してk要素を削除します。最終的に、TreeMapにはk-最小要素は含まれません。

Answer 3

区別する属性がキーの一部であるか値であるかについては言及していません。それがキーである場合は、上記のツリーマップが適用されます。

そうでなければ、これを頻繁に行う必要がある場合は、マップインターフェイスのすべてをハッシュマップ（または適切な構造0。追加/削除をオーバーライドし、必要に応じてイテレータをオーバーライドしてから、追加/削除を使用して、独自のマップを実装する傾向があります。値のソートされたリストを維持します。

これは明らかに値が変化しないことを前提としており、問題と密接に関連しています。

Answer 4

TreeMapは、キーの自然な順序で並べ替えられることに注意してください。したがって、値の長さに基づいて比較可能なキーを作成できます。たとえば（私は昼食をとっているので、コードは完璧ではありませんが、必要なものに到達するはずです）：

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,