I came across a similar problem and my performance hit was very similar to the one described by Tux.
I got around this by using File::Cache. Considering you seem to be fine with trading run time for memory this might be an option.
A slightly faster but more CPU intensive approach ( that I finally settled on ) was to selectively keep elements in the hash - So essentially the solution was a multi level cache with the first level being the hash and elements in that expire based on either time or frequency of access, and when a cache miss on the hash is generated you look it up in File::Cache - Of course the additional CPU usage comes in when handling the removal of expired hash cache elements.