In Java, use ConcurrentHashMap.

If you're particularly interested in pushing this to the edge, check out Cliff Click's non-block hash map.