Luego de mirar en diversos repositorios y sitios finalmente descubrimos la solución que te compartimos pronto.
Solución:
TreeMap me parece una obviedad, simplemente debido al requisito “en orden alfabético”. HashMap no tiene ningún orden cuando itera a través de él; TreeMap itera en lo natural key ordenar.
EDITAR: creo que el comentario de Konrad puede haber estado sugiriendo “usar HashMapluego ordene”. Esto es bueno porque aunque inicialmente tendremos N iteraciones, tendremos K <= N keys al final debido a los duplicados. También podríamos guardar la parte costosa (clasificación) hasta el final cuando tengamos menos keys que tomar el golpe pequeño pero no constante de mantenerlo ordenado a medida que avanzamos.
Habiendo dicho eso, me atengo a mi respuesta por el momento: porque es el más simple forma de lograr el objetivo. Realmente no sabemos si el OP está particularmente preocupado por el rendimiento, pero la pregunta implica que está preocupado por la elegancia y la brevedad. Usando un TreeMap hace esto increíblemente breve, lo que me atrae. Sospecho que si el rendimiento es realmente un problema, puede haber una mejor manera de atacarlo que TreeMap o HashMap 🙂
TreeMap supera a HashMap porque TreeMap ya está ordenado para usted.
Sin embargo, es posible que desee considerar el uso de una estructura de datos más adecuada, una bolsa. Consulte Colecciones comunes y la clase TreeBag:
Esto tiene una buena estructura interna optimizada y una API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
EDITAR: Jon respondió la pregunta sobre el rendimiento de HashMap vs TreeMap: HashMap y ordenar pueden ser más rápidos (¡pruébelo!), Pero TreeBag es más fácil. lo mismo es true para bolsas Hay un HashBag y un TreeBag. En función de la implementación (utiliza un entero mutable), una bolsa debería superar al mapa simple equivalente de Integer. La única forma de saberlo con certeza es probar, como con cualquier pregunta de desempeño.
Veo bastantes personas que dicen “La búsqueda de TreeMap requiere O(n log n)“!! ¿Cómo?
No sé cómo se ha implementado, pero en mi cabeza se necesita O(log n).
Esto se debe a que la búsqueda en un árbol se puede realizar en O(log n). No ordena todo el árbol cada vez que inserta un elemento en él. ¡Esa es la idea de usar un árbol!
Por lo tanto, volviendo a la pregunta original, las cifras de comparación resultan ser:
Enfoque HashMap:O(n + k log k) caso promedio, el peor de los casos podría ser mucho mayor
Enfoque TreeMap:O(k + n log k) peor de los casos
donde n = número de palabras en el texto, k = número de palabras distintas en el texto.
Comentarios y valoraciones del tutorial
Acuérdate de que puedes permitirte valorar esta noticia si te fue de ayuda.