Ajuda com HashMap - Reaproveitamento de Key

Boa tarde, estou com uma dúvida e queria se já há alguma forma de fazer isso. É o seguinte: Gostaria de criar um HashMap para funcionar como id/valor, até aí tudo bem, mas há vezes que um valor é removido desse map e gostaria de reutilizar a posição dele quando for adicionar um novo elemento.
Exemplo:

Valores iniciar (keys): 1 2 3 4 5 6
Valor removido = 5
Valores atuais (keys): 1 2 3 4 6
Adicionar valor a key 5 (Como fazer isso?)

Daí ao invés de eu add e dar a key de 7, gostaria de colocar a key como 5.

Pensei em fazer um for até encontrar uma key inexistente, mas estou achando que isso será ineficiente, há outro modo?

para verificar se o seu hashmap tem a chave não precisa de um for é só utilizar o metodo:

// todos os nomes de variveis que eu usei são ilustrativos.
 //faça a seguinte verificação
  if(!seuhashMap.containsKey(valor)){// se a chave não existir no seu HashMap
     //seu codigo
  }

Hashmap trabalha com um conceito diferente de lista, array e outras coleções que utilizam posições.
Se você precisa de ordenação utilize TreeMap ou mesmo LinkedHashMap.