Algorithm to write a dictionary using thousands of words to find all anagrams for a given string with O(1) complexity Problem Statement:
Suppose we have a thousands of words and we need to maintain these words in a data structure in such a way that we should be able to find all anagrams for a given string.
I tried to achieve this with O(1) complexity.

I am looking for a algorithm to implement above scenario. I implemented this problem with below algo, but I feel that we can improve its complexity. Any suggestion will be helpful.

Algorithm:

Here is trick to utilise hash code, we can also use character histogram.

Step 1:Create an array of prime numbers.

   int primes[] = {2, 3, 5, 7, ...};

   We are using prime number to avoid false collisions.


Step 2:Create a method to calculate hash code of a word\string.

   int getHashCode(String str){
     int hash = 31;
     for(i =0 to length of str){
        hash = hash*primes['a' - str.charAt[i]];
     }
     return hash;
   }


Step 3: Now store all words in a HashMap.

void loadDictionary(String[] words){

  for( word from words for i = 0 to length of words)   {
     int hash  = getHashCode(word);
     List&lt;String&gt; anagrams = dictionary.get(hash);
     if(anagrams ! = null){
         anagrams.add(word);
     } else
        List&lt;String&gt; newAnagrams = new ArrayList&lt;String&gt;();
        newAnagrams.add(word);
        dictionary.put(hash, newAnagrams);
     }
  }
}


Step 4: Now here is the approach to find anagrams:

   int findNumberOfAnagrams(String str){
      List&lt;String&gt; anagrams = dictionary.get(getHashCode(str));
      return anagrams.size();
   }
You may get some inspiration from the articles The world's fastest scrabble program by Andrew W. Appel and A Faster Scrabble Move Generation
Algorithm by Steven A. Gordon.
Both algorithms rely on a clever use of finite automata.

See also this question on Stackoverflow.