How can I make anagram program code faster? (java)

Question

I am a not so experienced programmer. I've written an anagram program and the only problem is that its not fast enough. I've been told that my nested for loop is the problem, but i can't figure how to fix it (set1 is a HashSet with all the words I'm working on, map is a LinkedHashMap<String, String> and anagram a TreeMap<String, TreeSet<String>>):

for (String element : set1) {
    char[] woord = element.toCharArray(); //alfabetical order of each word
    Arrays.sort(woord);
    String chartostring = new String(woord);
    map.put(element, chartostring); // add each word with its sorted letters
    TreeSet<String> order_words = new TreeSet<String>(); //creating list of anagrams
    for (String o : map.keySet()) { //for each word
        if (map.get(o).equals(chartostring)) { //check if there is a value in map which is equal to the sorted letters
            order_words.add(o); //add word to list of anagrams
            if (order_words.size() > 1) { //we want anagrams so only print if there are atleast 2 words
                anagram.put(chartostring, order_words);
            }
        }
    }
}

Can someone please help me out? Thanks a lot.

Answer 1

The nested loop is, indeed, slow, because you iterate a map as if it were a list. Wouldn't it be nice if you could replace the nested loop with a quick look-up in a hash map? Unfortunately, this is not an option when you deal with Map<String,String>, because multiple words will have identical sorted representation. That is why you built a map from a word to its sorted representation, not the other way around.

What this means, however, is that you can build a map from a sorted representation to a list of words:

Map<String,List<String>> sortedRepToWords

You can build this map in a single loop, before doing any matching. With this map-of-lists in place, you can eliminate the nested loop, replacing it with a look-up of the entire list from sortedRepToWords.

Answer 2

Introducing Java 8...

import java.util.stream.Stream;
import static java.util.stream.Collectors.*;

Map<String, List<String>> tmp = set1.parallelStream() // Possibly using multiple cores...
    .collect(groupingBy(s-> sortMe(s))); // One liner!

List<List<String>> result = tmp.values().stream()
    .filter(l -> l.size() > 1)  // At least 2 anagrams
    .collect(toList());

System.out.println(tmp);
System.out.println(result);

//...//

// If you really want to use Java 8 for sorting a String...
private String sortMe(String input) {
    return Stream.of(input.split("")).sorted().collect(joining());
}