Sorting a HashMap by Value

Programming Questions

justincou..

in Programming Questions • 1 year ago

Hello All,

I am attempting to sort a HashMap based on the Value. I want to use the most frequent words in a text. First I have to count them (which I can do), then I have to sort them by their number (which isn't working).

I've found several things that touch on it, and I think I'm very close, but it's not exactly working.

If you run the code you'll see that the 'sortHashMap' function is sorting them properly, but when I print the sortedMap, it's no longer sorted. Is there something with the .put function that I'm not realizing?

Thanks for looking.

p.s. - you'll also need some sort of text file.

HashMap newWords; // HashMap object
HashMap sortedWords;
HashMap countedWords;
String[] newTokens; // Array of all words from input file
String[] commonTokens; // Array of all words from input file
int counter;
PFont displayFont;
void setup(){
size(400, 400);
newWords = new HashMap();
sortedWords = new HashMap();
countedWords = new HashMap();
// Load new file and chop it up
String[] newLines = loadStrings("hamlet.txt");
String allNewText = join(newLines, " ");
//create hash table
newTokens = splitTokens(allNewText, " -/%=#&,.?!:;[]1234567890()\t\n\r\f");
//println(newTokens.length);
for (int i=0; i<newTokens.length; i++){
String newString = newTokens[i].toLowerCase();
if (newWords.containsKey(newString)) {
// Get the word object and increase the count
// We access objects from a HashMap via its key, the String
Word includedWord = (Word) newWords.get(newString);
includedWord.countIncrease();
} else {
// Otherwise make a new word
Word includedWord = new Word(newString);
// And add to the HashMap
// put() takes two arguments, "key" and "value"
// The key for us is the String and the value is the Word object
newWords.put(newString, includedWord);
}
}
//print(newWords.keySet());
// Make an iterator to look at all the things in the HashMap
Iterator i = newWords.values().iterator();
while (i.hasNext()) {
Word wordChk = (Word) i.next();
//println(wordChk.word + ": " + wordChk.count);
countedWords.put(wordChk.word, wordChk.count);
}
sortedWords = sortHashMap(countedWords);
//println(sortedWords);
List sortKeys = new ArrayList(sortedWords.keySet());
Iterator sortedI = sortKeys.iterator();
while(sortedI.hasNext()){
Object skey = sortedI.next();
//println(skey.toString() + ": " + sortedWords.get(skey));
}
//println(sortedWords);
}
void draw(){
}
HashMap sortHashMap(HashMap input){
List mapKeys = new ArrayList(input.keySet());
List mapKeysClone = mapKeys;
List mapValues = new ArrayList(input.values());
List mapValuesClone = mapValues;
//println(mapValues);
Collections.sort(mapValues);
//Collections.sort(mapKeys);
//println(mapKeys);
//println(mapValues);
HashMap sortedMap = new HashMap();
Iterator valueIt = mapValues.iterator();
while (valueIt.hasNext()) {
Object val = valueIt.next();
Iterator keyIt = mapKeys.iterator();
while (keyIt.hasNext()) {
Object ky = keyIt.next();
String comp1 = input.get(ky).toString();
String comp2 = val.toString();
if (comp1.equals(comp2)){
input.remove(ky);
mapKeys.remove(ky);
println(ky.toString() + ": " + val);
//println(val.getClass());
sortedMap.put(ky.toString(), val);
break;
}
}
//println(sortedMap);
}
println(sortedMap);
return sortedMap;
}
class Word {
int count;
String word;
Word(String s) {
word = s;
count = 1;
}
void countIncrease() {
count++;
}
}

Replies(12)

PhiLho

Re: Sorting a HashMap by Value

1 year ago

HashMap is, by essence, not sortable. Its algorithm requires the values to be in a highly random order, so they are distributed uniformly in the storage space.
The good news is that Java offers a TreeMap, which is a SortedMap, a hash map with a natural order. It doesn't contradict what I wrote above, it is actually a hash map with a list (a double collection), the list providing the ordering and holding references to the items in the hash map.
Even better: the tree map is always sorted, each time you add a new item.

justincou..

Re: Sorting a HashMap by Value

1 year ago

But from what I understand, a TreeMap is sorted by Key, not Value. I can get a lovely alphabetized list, but what I want is a list of words in ascending (or descending) order based on word count.

So in the code, this first line gives me exactly what I want. but for some reason at the end, the sortedMap is not ordered.

println(ky.toString() + ": " + val);

sortedMap.put(ky.toString(), val);

Maybe I shouldn't be using HashMap? Should I just have two ArrayLists with the same order? I'll try that and let you know.

phillarby

Re: Sorting a HashMap by Value

1 year ago

Another way of approaching this could be to use a trie with a value at each node to represent the word count: http://en.wikipedia.org/wiki/Trie. You would need to naviagte through the tree to build the ordered results, but it would be more space efficient and possibly more time efficient than maintaining a treemap of whole words.

There is an implementation of a trie here: http://www.mpi-inf.mpg.de/yago-naga/javatools/doc/javatools/datatypes/Trie.html but it would need extending to hold the word count.

justincou..

Re: Sorting a HashMap by Value

1 year ago

I was able to get it to work for my purposes. I could never sort the HashMap, but I created two ArrayLists with matched indices so I could get the right combination. Not pretty but it worked. I sorted the values, then went through that list, found matching keys in the original set, then added those keys to a new ArrayList.

mapKeys = new ArrayList(countedWords.keySet());
mapKeysClone = new ArrayList(countedWords.keySet());
mapValues = new ArrayList(countedWords.values());
mapValuesClone = new ArrayList(countedWords.values());
ascWords = new ArrayList();
Collections.sort(mapValues);
Collections.sort(mapValuesClone);
Iterator valueIt = mapValues.iterator();
while (valueIt.hasNext()) {
Object val = valueIt.next();
Iterator keyIt = mapKeys.iterator();
while (keyIt.hasNext()) {
Object ky = keyIt.next();
String comp1 = countedWords.get(ky).toString();
String comp2 = val.toString();
if (comp1.equals(comp2)){
countedWords.remove(ky);
mapKeys.remove(ky);
ascWords.add(ky.toString());
break;
}
}
//println(sortedMap);
}

bustup

Re: Sorting a HashMap by Value

1 year ago

A simple google search on "sort treemap by value java" gave me: http://stackoverflow.com/questions/2864840/treemap-sort-by-value

justincou..

Re: Sorting a HashMap by Value

1 year ago

Yeah, I found that but had no idea what it meant. That takes a level of understanding that i'm not at. Thanks though.

bustup

Re: Sorting a HashMap by Value

1 year ago

So what I understand you have an integer as key and string as value. In that case it can be achieved by this:

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.Map.Entry;
void setup() {
Map<Integer, String> nonSortedMap = new HashMap<Integer, String>();
nonSortedMap.put(1, "orange");
nonSortedMap.put(2, "apple");
nonSortedMap.put(3, "pineapple");
nonSortedMap.put(4, "peer");
Map<Integer, String> sorted = sortMapByValues(nonSortedMap);
Iterator<Entry<Integer, String>> entries = sorted.entrySet().iterator();
while (entries.hasNext ()) {
Entry<Integer, String> entry = entries.next();
PApplet.println(entry.getKey() + " " + entry.getValue());
}
}
public static <K, V extends Comparable<V>> Map<K, V> sortMapByValues(final Map<K, V> map) {
Comparator<K> valueComparator = new Comparator<K>() {
public int compare(K k1, K k2) {
final V v1 = map.get(k2);
final V v2 = map.get(k1);
/* Not sure how to handle nulls ... */
if (v1 == null) {
return (v2 == null) ? 0 : 1;
}
int compare = v2.compareTo(v1);
if (compare != 0)
{
return compare;
}
Integer h1 = k1.hashCode();
Integer h2 = k2.hashCode();
return h2.compareTo(h1);
}
};
Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
sortedByValues.putAll(map);
return sortedByValues;
}

bustup

Re: Sorting a HashMap by Value

1 year ago

Updated with Processing-friendly code.

PhiLho

Re: Sorting a HashMap by Value

1 year ago

bustup, I tried your code but Processing wasn't liking the syntax...
Moreover, the original poster wants to count the frequency of words (a classical task), so the words are the keys and the integer count are the values.
I started from your code, moved the collection to a .java file just in case Processing didn't like the nested generics, and inverted the types:

SortingMapByValues.pde

import java.util.Map.Entry;
void setup()
{
SortDemo demo = new SortDemo();
demo.put("walnut", 45);
demo.put("orange", 125);
demo.put("apple", 45);
demo.put("nut", 45);
demo.put("pineapple", 12);
demo.put("pear", 76);
demo.put("banana", 56);
demo.put("litchi", 45);
demo.sort();
for (Entry<String, Integer> entry : demo.getSortedData())
{
println(entry.getKey() + " -> " + entry.getValue());
}
exit();
}

SortDemo.java

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortDemo
{
Map<String, Integer> nonSortedMap = new HashMap<String, Integer>();;
SortedSet<Map.Entry<String, Integer>> sortedMap;
public SortDemo()
{
}
public void put(String s, Integer n)
{
nonSortedMap.put(s, n);
}
public void sort()
{
sortedMap = sortByValues(nonSortedMap);
}
public SortedSet<Map.Entry<String, Integer>> getSortedData()
{
return sortedMap;
}
private static <K extends Comparable<? super K>, V extends Comparable<? super V>>
SortedSet<Map.Entry<K, V>>
sortByValues(Map<K, V> map)
{
SortedSet<Map.Entry<K, V>> sortedEntries = new TreeSet<Map.Entry<K, V>>(
new Comparator<Map.Entry<K, V>>()
{
// For some reason, it doesn't accept Override even in a .java file...
//@Override
public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2)
{
int res = e1.getValue().compareTo(e2.getValue());
if (res != 0)
return res; // Different, just give the result
res = e1.getKey().compareTo(e2.getKey());
return res != 0 ? res : 1; // Special fix to preserve items with equal values
}
});
sortedEntries.addAll(map.entrySet());
return sortedEntries;
}
}

A little refinement: for identical values, I also sort the keys...

[EDIT] Ah, you updated your code... I shouldn't post from a message opened yesterday!

Well, perhaps my little refinements are worth a double post. And my remark on the order of types still stands, even if it is easy to fix.

PhiLho

Re: Sorting a HashMap by Value

1 year ago

Also implementing a text file stats, operating on the source code of the sketch for convenience...
I reversed the sort order because we are usually more interested by the most frequent words.

SortingMapByValues.pde

import java.util.Map.Entry;
Map<String, Integer> counts = new HashMap<String, Integer>();
void setup()
{
SortDemo demo = new SortDemo();
demo.put("walnut", 45);
demo.put("orange", 125);
demo.put("apple", 45);
demo.put("nut", 45);
demo.put("pineapple", 12);
demo.put("pear", 76);
demo.put("banana", 56);
demo.put("litchi", 45);
demo.sort();
for (Entry<String, Integer> entry : demo.getSortedData())
{
println(entry.getKey() + " -> " + entry.getValue());
}
println("\nCode stats:\n");
SortDemo stats = new SortDemo();
String[] text1 = loadStrings(sketchPath("SortingMapByValues.pde"));
String[] text2 = loadStrings(sketchPath("SortDemo.java"));
for (String line : text1)
{
parseLine(line);
}
for (String line : text2)
{
parseLine(line);
}
stats.putAll(counts);
stats.sort();
int count = 0;
for (Entry<String, Integer> entry : stats.getSortedData())
{
println(entry.getKey() + " -> " + entry.getValue());
if (++count > 20) break; // Only Top 20
}
exit();
}
void parseLine(String line)
{
String[] words = line.split("[\\W]+");
for (String word : words)
{
if (word.length() == 0)
continue;
if (counts.containsKey(word))
{
counts.put(word, counts.get(word) + 1);
}
else
{
counts.put(word, 1);
}
}
}

SortDemo.java

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.SortedSet;
import java.util.TreeSet;
public class SortDemo
{
Map<String, Integer> nonSortedMap = new HashMap<String, Integer>();;
SortedSet<Map.Entry<String, Integer>> sortedMap;
public SortDemo()
{
}
public void put(String s, Integer n)
{
nonSortedMap.put(s, n);
}
public void putAll(Map<String, Integer> rawMap)
{
nonSortedMap = rawMap;
}
public void sort()
{
sortedMap = sortByValues(nonSortedMap);
}
public SortedSet<Map.Entry<String, Integer>> getSortedData()
{
return sortedMap;
}
private static <K extends Comparable<? super K>, V extends Comparable<? super V>> SortedSet<Map.Entry<K, V>>
sortByValues(Map<K, V> map)
{
SortedSet<Map.Entry<K, V>> sortedEntries = new TreeSet<Map.Entry<K, V>>(
new Comparator<Map.Entry<K, V>>()
{
// For some reason, it doesn't accept Override even in a .java file...
//@Override
public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2)
{
int res = e1.getValue().compareTo(e2.getValue());
if (res != 0)
return -res; // Different, just give the result, negated for reversing order
res = e1.getKey().compareTo(e2.getKey());
return res != 0 ? res : 1; // Special fix to preserve items with equal values
}
});
sortedEntries.addAll(map.entrySet());
return sortedEntries;
}
}

justincou..

Re: Sorting a HashMap by Value

1 year ago

That's amazing phi.lho! I'm not going to pretend like I understand it all but it works beautifully! Is it okay if I use this code in a project I'm working on? This is an early version, but I'll probably be moving away from the table. Thanks again!

PhiLho

Re: Sorting a HashMap by Value

1 year ago

Well, my code is under the zlib/libpng license, so all you have to do to use it is to give credit (ie. don't tell you wrote it all by yourself!

).
Also include the original Stackoverflow reference and bustup which did the search and made a first draft from which I started.

Top Reply