I agree with the first sentence. For the second part, what are you thinking of? For reads, there's very low overhead for using an implementation like Java's ConcurrentHashMap. The overhead for insertions is more significant, but not enormous.