I have what I believe is an interesting problem: I have a function which calculates something which is really costly. I would like to add a cache to it. The input is a single 64 bit integer and the output is also a single 64 bit integer. Ideally, I would allocate the cache on the stack before calling the function and it would be really small because the number of really widely used entries is really small (maybe 10 to 30).

There are many solutions to this problem (all sorts of hash tables, etc.) but I have the feeling that my interest is to make sure that the really hot entries are always in the cache so I am interested in finding a good algorithm to decide what entry gets into the cache and what entries get removed from it while minimizing the size of the cache. Obviously, there is a large design space here with lots of compromises to be made (speed, accuracy of the cache with regard to hotness and cache size) but I wonder whether there exist a clear winning technique to do this.