sort out hashmap entries by key

Performance Tuning
#1

hey there :slight_smile:

I came accross this problem today:

I have a HashMap<String, String>, and I want to sort out entries selectively by key, that is, only keys which start with ~ should remain (and the ~s should be removed in the process).

My first thought was to get some queue object from the keys, process them and call remove(key) on the hashmap. but this seems rather slow to me and it’s not possible to remove the ~s in front of all keys in the process. :\

How would you do this? I’m not quite sure - especially about performance aspects - on this one >_>

#2

Use a different datatype? Something tree-based, so that sorting is easy and efficient (assuming, of course, you;ve actually profiled it and discovered this is your bottleneck)

#3

If it’s a single shot sorting and filtering (or at least, not too often used), you can use something like this (from memory…) :
(java 1.4 code)
List sorted = Collections.sort(map.keySet(), new Comparator(){
public int compare(Object o1, Object o2){
String s1 = (String) o1;
if (s1.startsWith("~s"){
String s2 = (String) o2;
if (s2.startsWith("~s")){
return s1.compareTo(s2);
} else {
return -1;
} else {
return 1;
}
}
});

This way you’ll have a sorted list, with “~s” Strings at the beginning.

Iterate over it until a non ~s string found.

Lilian

#4 

        HashMap<String, String> timerdata = new HashMap<String, String>();
        Iterator<String> keys = data.keySet().iterator();
        while(keys.hasNext()){
            String temp = keys.next();
            if(temp.charAt(0) == '~')
                timerdata.put(temp.substring(1), data.get(temp));
        }

may not be the fastest, but it works :slight_smile:

thanks for your advice :slight_smile:

#5

Correct me if i’m wrong, but it is not sorted… :wink:

Lilian

#6

well of course it’s not…

[quote]sort out entries selectively by key, that is, only keys which start with ~ should remain
[/quote]

#7

Last thought (as we are in the performance tuning thread).

I don’t know if it’s usefull in your case, but if you iterate over
entries() instead of keySet(), you’d have the benefits of accessing the key’s associated value in one more field access ((Map.Entry)).getKey() / getValue()) instead of a hashing, but you might already be aware of it.

Lilian

#8

ah… right. thanks :slight_smile:


        HashMap<String, String> timerdata = new HashMap<String, String>();
        Iterator<Entry<String, String>> keys = data.entrySet().iterator();
        while(keys.hasNext()){
            Entry<String, String> temp = keys.next();
            if(temp.getKey().charAt(0) == '~')
                timerdata.put(temp.getKey().substring(1), temp.getValue());
        }