Custom datastructure in Java

Question

I am looking for a datastructure in Java that can do the following:

• It contains key, value pairs;
• I can do an 'add' operation, if the key is already present it increases the counter in the value, otherwise it adds a new key,value pair to the datastructure;
• With every add the datastructure automatically reorders itself so that the key,value pairs are sorted based on the value;
• Preferably all these operations should be logarithmic in time complexity (or less, but will be hard I guess).

How can I manage something like this or is there already something implemented?

EDIT

private HashMap<String, Integer> keyMap;
private TreeSet<String> valueSet;

public MultiSet() {
    Comparator<String> comparator = new Comparator<String>() {
        @Override
        public int compare(String key1, String key2) {
            return keyMap.get(key1).compareTo(keyMap.get(key2));
        }
    };
    keyMap = new HashMap<String, Integer>();
    valueSet = new TreeSet<String>(comparator);
}

public void add(String key) {
    if (keyMap.containsKey(key)) {
        valueSet.remove(key);
        keyMap.put(key, keyMap.get(key) + 1);
        valueSet.add(key);
    } else {
        keyMap.put(key, 1);
    }
}

Answer 1

You basically need a Map (preferably hash based), and an SortedSet (probably a TreeSet).

Map<Key,Value> byKey and Set<Key> byValue

The first map will have the natural key's Comparator, while the second one will have a Comparator that first uses byKey.get(key1).compareTo(byKey.get(key2)) first, and only if they are deemed as equal, uses the natural Key Comparator.

Add:

• check if element already exists, if it is - take it out from byValue.
• modify the value in byKey
• Add the element to byValue

Note that this ensures that the Set is ordered by increasing value of the given values.

Assuming the map is hashed based, and every operation in it is O(1) on average, it gives you O(logn) running time (removing from byValue and adding to it).

Answer 2

You can use a combination of a HashMap to store the key/value, HashMap to the key/counter and a TreeMap<Integer, List<Key>> for the sorted list.

i.e. you need a combination of existing collection as you won't find just one which does everything.

Answer 3

Use a HashMap and then if HashMap contains key you just increase the value associated to it.

Answer 4

Try the Guava Multiset. It does exactly what you are asking for.