Hola, Kuu,
no soy un experto en java. Pero intento darte mi punto de vista por si te puede ayudar.
Creo que todo va a depender del número de palabras que vayas a usar. Si son pocas una lista ordenada con la clave como palabra y el número de apariciones como valor sería suficiente.
Supongo que esto lo preguntas porque no van a ser pocas palabras ;)
Una forma que se me ocurre es simular una estructura de árbol en java. Podrías tener una lista ordenada cuya clave sea la inicial y el valor una lista ordenada cuya clave sea la palabra (que empieza por esa inicial) y el valor el número de apariciones. Si el número de palabras es aún muy grande puedes añadir más ramas al árbol, por ejemplo, el valor de la lista inicial sería otra lista de letras, que serían la segunda letra de la palabra.
Algo así (igual no es un java muy correcto, pero creo que la idea se ve):
TreeMap<String, TreeMap<String, Integer> > listaRaiz = new TreeMap();
listaRaiz.put("a",new TreeMap<String, Integer>());
listaRaiz.get("a").put("abracadabra", 1);
Como curiosidad, ¿qué haces con palabras como "programas" y "programa", son 2 palabras o una? ¿y "programó" con "programaba"? Porque según lo que estés haciendo deberías hacer algo que identifique lexemas (igual ya lo tienes :).
Un abrazo, Javi.