1. A method for automatically changing the size of a cache, comprising: removing old entries in said cache using an eviction policy; inserting new entries in said cache; maintaining information about regenerated entries and removed old entries; and resizing said cache based on a function of said information about the regenerated entries and the removed old entries, wherein the regenerated entries are ones of the new entries that were previously removed from the cache.