Automatically sorted by values map in Java

by

Keep 2 data structures:

  • A dictionary of words -> count. Just use an ordinary HashMap<String, Long>.

  • An “array” to keep track of order, such that list[count] holds a Set<String> of words with that count.

    I’m writing this as though it were an array as a notational convenience. In fact, you probably don’t know an upper bound on the number of occurrences, so you need a resizable data structure. Implement using a Map<Long, Set<String>>. Or, if that uses too much memory, use an ArrayList<Set<String>> (you’ll have to test for count == size() - 1, and if so, use add() instead of set(count + 1)).

To increment the number of occurrences for a word (pseudocode):

// assumes data structures are in instance variables dict and arr
public void tally(final String word)
{
    final long count = this.dict.get(word) or 0 if absent;
    this.dict.put(word, count + 1);
    // move word up one place in arr
    this.arr[count].remove(word);   // This is why we use a Set: for fast deletion here.
    this.arr[count + 1].add(word);
}

To iterate over words in order (pseudocode):

for(int count = 0; count < arr.size; count++)
    for(final String word : this.arr[count])
        process(word, count);

Leave a Comment