When I ported all of our C++ code over to Java, one of the things I was told was "You don't have to worry about the speed of looking things up in hash maps. They're really fast." And since maintaining shared references to a single copy of an object was a pain in the butt, I started storing keys to the objects and looking them up in a master hash map for each of the different types of objects.

Then I found out that I was spending too much time looking up some of the things in the hash maps. So I made sure that the keys for the most frequently accessed object were immutable and shared via a common cache. And then I stored the pre-computed hash code inside the key, because not having to hash the key every time would speed up the searches a lot.

But the C++ code was running too slow, as I'd replaced the old shared pointers there. So I did the same trick in C++ that I done with the shared immutable cached keys with the pre-computed hash codes. Still not fast enough though.

Well, there was this value that I had previously pre-computed and stored, but was now looking up on the fly in a hash map with potentially multiple checks per value. Let's try putting that stored value back and only updating it when it needs to be updated.

Yes, that is fast enough.

*sigh*