Yes. Another simple representation if you assume a maximum number of occurrences per letter:

  (defvar *alphabet* "abcdefghijklmnopqrstuvwxyz")
  
  (defconstant capacity-in-bits 3)
  
  (defun key (word)
    (loop with key = 0
          with max-occurrences = (1- (ash 1 capacity-in-bits))
          for letter across *alphabet*
          for i upfrom 0
          for occurrences = (count letter word)
          do (if (> occurrences max-occurrences)
                 (error "too many occurrences")
                 (setf (ldb (byte capacity-in-bits (* i capacity-in-bits)) key)
                       occurrences))
          finally (return key)))

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.