Como remover dados de um hashMap em tempo de execução

Não entendi exatamente a questão, mas, se foi o que eu entendi, você pode sim remover, inclusive, a classe HashMap possui um método chamado remove, conform consta no javadoc da mesma

Solução extremamente elegante

O problema é que você está tentando remover um índice ao qual está sendo utilizado como recurso do loop. Para não ter problemas de integridade e outros, o Java não permite vc fazer este tipo de operação desta forma. Isto ocorre com as Maps e Lists da vida.
A solução de contorno é criar uma hash de excluídos externo ao loop em questão e após a conclusão do loop remover os índices da hasmap originial com base na de excluídos. Outro ponto de sugestão é trabalhar com o entrySet() ao invés do keySet(), pois existe um impacto de desempenho entre eles. Segue um exemplo básico de como fazer que com certeza merecerá ser evoluído…rs

Map<Integer, String> list = new HashMap();
list.put(1, "Banana");
list.put(2, "Maça");
list.put(3, "Pera");
list.put(4, "Uva");

Map<Integer, String> removidos = new HashMap();

for(Map.Entry entry : list.entrySet()){
	if("Banana".equals(entry.getValue().toString()) ||
			"Uva".equals(entry.getValue().toString())){
		removidos.put((Integer)entry.getKey(), entry.getValue().toString());
	}
}

// VALIDANDO FRUTAS PARA REMOÇÃO

for(Map.Entry key : removidos.entrySet()){
	System.out.println("Removendo o item: " + key.getValue());
}

// REMOVENDO AS FRUTAS

for(Map.Entry entry : removidos.entrySet()){
	list.remove(entry.getKey());
}

// VALIADNDO A LISTA ORIGINAL SEM AS FRUTAS REMOVIDAS
System.out.println("## LISTA ORIGINAL ##");
for(Map.Entry key : list.entrySet()){
	System.out.println(key.getValue());
}

Saída do console:

Removendo o item: Banana
Removendo o item: Uva
## LISTA ORIGINAL ##
Maça
Pera

Ah, é importante saber que essa alteração é válida se vc não tiver elementos com a mesma chave no Map, pois o entrySet() retorna um conjunto de dados sem valores repetidos.

Em que situações é possível ter mais de um elemento com a mesma chave no mapa?
Se eu faço

Map<Integer, String> mapa = new HashMap<Integer, String>();
mapa.put(1, "João");
mapa.put(1, "Anselmo");

Eu não tenho um mapa com uma posição cuja chave é 1 e o valor é “Anselmo”?

Você tem razão!!! Comi bola na explicação. O map atualiza o índice com base na última inserção. Em outros casos de Hashes faz mais sentido. Obrigado pela correção!

Se usares explicitamente um iterator podes remover diretamente no ciclo.

Iterator it =  map.keySet().iterator();

 while(it.hasNext()) {
     Object key=it.next();
     System.out.println("Valor: " + list.get(key));   
     it.remove();
 }

Exato.

Eu nao tinha certeza o que aconteceria com o valor alocado no mapa se você só removesse a key.

Quando tive a chance, eu notei que o Set do map é uma classe específica que remove o par inteiro (key, value) e nao apenas a key, sendo uma boa alternativa.

Mas como soluçao melhor, com Java 8, eu prefiro usar o map.keySet().removeIf(pred)