But fundamentally, one could argue that O(N/100) is still really O(N)...

My fear is in delivering a module to the CPAN, which is not complete (and hence you could say buggy) by design, algorithmically, although it doesn't necessarily have to be, technical difficulties aside.

For my data sets, which die rather quickly, I doubt 1000 accesses could be made before the hash is cleaned up anyway. For someone else, however, the hash may be seldom accessed, but large, and with many disappearing references as keys. Both of us don't gain much from such a solution.

I agree it is better than just leaving it that way, in that it mostly works most of the time. I think that for my purposes, though, ysth's solution seems like the most promising way to feel good about it. I reckon eventually I'll write several subclasses, that are interchangable, and chosen at use time.

Anyway, thanks... and I wondered how CDBI did it, but was too busy to look (with other stuff) since the problem came up... ;-)

You could make the number of accesses between cleanings proportional to the size of the hash. That maintains O(1) average overhead for keeping things clean, divided unfairly. Perl internally uses many variations on this strategy.

There are scenarios in which this compromise is the wrong thing to do. My answer to that is that no solution ever strikes a perfect balance. Find a good enough one and move on. Make it pluggable (as you suggest) if that isn't good enough.

In Class::DBI, we make the number of accesses configurable by the user, so that someone who doesn't care can skip the cleanup and someone who is really paranoid about it can do it frequently.