So, the question is: does a hashmap implementation exist where accessing and normal writing is not serialized, but expanding the table has the appropriate locks?
If you're particularly interested in pushing this to the edge, check out Cliff Click's non-block hash map.
Collections.synchronizedMap(new HashMap());