A ver, lo repito de otra forma, cuando usas una sola clase en un hasmap, significa que para la key estarás usando un integer o un String, en ese caso containskey o remove funcionan, porque java sabe como comparar las keys.
Si usas una clase tuya como key, java no sabe como compararlas, por eso necesitas modificar los dos métodos que te he dicho, para que containskey y remove sepan cómo comparar los objetos. Containskey, get o remove lo que hacen es llamar al método equals()/hascode(), por eso tienes que modificarlos.
Los métodos que se usan para comparar no son los mismos para un Set que para un Hashmap o una lista. Pero en todos ellos necesitas decirle como comparar.
Por otra parte,
Cita: Set<Object> s = matriculas.keySet();
Iterator<Object> it2 = s.iterator();
while(it2.hasNext()){
MatriculaCoche ma = (MatriculaCoche)it2.next();
System.out.println(ma + " - " + matriculas.get(ma));
No entiendo lo que dices de que no usas HashMap, aquí recuperas un Set de matrículas y le pides al hashmap que te devuelva el objeto al que le has asignado como key cada matrícula. Y como se lo pides a un hashmap, necesitas el equals y el hashcode.
Creo que necesitas olvidar lo que has hecho y que crees que funciona, y centrarte en lo que te estamos diciendo, que es como realmente funcionan las cosas.
No tienes que cambiar código, sólo modificar lo que te hemos dicho.
Edito:
jeisongutierrez
en un hasmap también hay que modificar el hashcode
http://glnconsultora.com/blog/?p=73