It could be. Here's a python implementation:

  from collections import Counter
  
  freq_to_words = {}
  make_freq = lambda word: tuple(sorted(dict(Counter(word)).items()))
  
  with open('/usr/share/dict/words', 'r') as f:
      for line in f.read().split('\n'):
          freq = make_freq(line)
          if freq not in freq_to_words:
              freq_to_words[freq] = []
          freq_to_words[freq].append(line)
  
  print freq_to_words[make_freq('gas')] # ['gas', 'sag']

For time complexities, this requires O(n) preprocessing but can do O(1) lookups, since it's a hash structure.