WeakHashMap, in fact, does not store a pair of ";key - value"; and a pair of "weak link to the key - value". Particularity of weak links (WeakReference) is that they are ignored by the garbage collector, i.e. if there are no other references to the key-object it is destroyed.
Before any appeal to WeakHashMap (get (), put (), size (), etc.) invalid links are analyzed and the corresponding pair is removed.
Code to demonstrate:
Map<Object,String> map = new WeakHashMap<Object, String="">();
Object obj = new Object(); // we create an object
map.put(obj, "object"); // put it into the map
System.out.println(map.size()); // one element in the map
obj = null; // we clean the reference
System.gc(); // we play with the garbage collector
System.out.println(map.size()); // the map has to become blank