Preciso ter um automaticamente mapa classificado por valores em Java - para que continue sendo classificado a qualquer momento enquanto adiciono novos pares de valores-chave ou atualizo o valor de um par de valores-chave existente ou até mesmo excluo alguma entrad

Lembre-se também de que este mapa será realmente grande (centenas de milhares ou até dezenas de milhões de entradas em tamanho

Então, basicamente, estou procurando a seguinte funcionalidade:

Supõe que tínhamos uma classe 'SortedByValuesMap' que implementa a funcionalidade mencionada acima e que temos o seguinte 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));
}

a saída deve ser:

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

Em particular, o que é realmente importante para mim é poder obter a entrada com o menor valor a qualquer momento - usando um comando como:

smallestItem = sorted_map.lastEntry();

que deve me dar a entrada 'laranjas'

EDIT: Eu sou um novato em Java, por favor elabore um pouco em suas respostas - obrigado

EDIT2: Isso pode ajudar: Estou usando isso para contar palavras (para aqueles que são familiares: n gramas em particular) em grandes arquivos de texto. Então, eu preciso construir um mapa onde chaves são palavras e valores são as frequências dessas palavras. No entanto, devido a limitações (como RAM), eu quero manter apenas as palavras mais frequentes do X - mas você não pode saber de antemão quais serão as palavras mais frequentes, é claro. Assim, da maneira que pensei que poderia funcionar (como uma aproximação), comece a contar palavras e, quando o mapa atingir um limite máximo (como entradas de 1 mil), a entrada menos frequente será excluída para manter o tamanho do mapa 1 mil sempre.