Necesito tener unautomáticament mapa ordenado por valores en Java, de modo que se sigue ordenando en cualquier momento mientras agrego nuevos pares clave-valor o actualizo el valor de un par clave-valor existente, o incluso elimino alguna entrada.

Tenga también en cuenta que este mapa será realmente grande (cientos de miles o incluso 10 de millones de entradas de tamaño).

Así que básicamente estoy buscando la siguiente funcionalidad:

Supuse que teníamos una clase 'SortedByValuesMap' que implementa la funcionalidad mencionada anteriormente y tenemos el siguiente código:

SortedByValuesMap<String,Long> sorted_map = new SortedByValuesMap<String, Long>();
sorted_map.put("apples", 4);
sorted_map.put("oranges", 2);
sorted_map.put("bananas", 1);
sorted_map.put("lemons", 3);
sorted_map.put("bananas", 6);

for (String key : sorted_map.keySet()) {
  System.out.println(key + ":" + sorted_map.get(key));
}

la salida debe ser:

bananas:6
apples:4
lemons:3
oranges:2

n particular, lo que es realmente importante para mí es poder obtener la entrada con el valor más bajo en cualquier momento, usando un comando como:

smallestItem = sorted_map.lastEntry();

que debería darme la entrada 'naranjas'

EDIT: Soy un novato en Java, así que por favor explique un poco sus respuestas - gracias

EDIT2: Esto podría ayudar: estoy usando esto para contar palabras (para aquellos que están familiarizados: n-gramos en particular) en grandes archivos de texto. Así que necesito construir un mapa donde las claves son palabras y los valores son las frecuencias de esas palabras. Sin embargo, debido a limitaciones (como RAM), quiero mantener solo las X palabras más frecuentes, pero por supuesto, no puede saber de antemano cuáles serán las palabras más frecuentes. Entonces, la forma en que pensé que podría funcionar (como una aproximación) es comenzar a contar palabras y cuando el mapa alcanza un límite superior (como 1 mil entradas), la entrada menos frecuente se eliminará para mantener el tamaño del mapa en 1 mil siempre.