Timeouts with time-reversed linear probing
Mikkel Thorup · 2011
We consider portable software implementations of hash tables with timeouts. The context is a high volume stream of keyed items. When a new item arrives, we want to know if has been seen recently in terms of a fixed lifespan. This problem has numerous applications as a front-end for Internet traffic processing where the key could be a selection of fields from the header of a packet, e.g., tracing packets through networks, aggregation of netflows from routers, and helping firewalls reuse decisions from recent packets with the same key. We propose time-reversed linear probing tables to deal with timeouts. In experiments, compared with tumbling windows and lazy deletions, our time-reversed tables typically gains at least 25% in speed while using only half the space. The cost per item approaches that of a single random memory access. Our new scheme is cleaner to implement than previous schemes, and also more versatile, e.g., it is trivial to allow different items to have different lifespans; something not possible with tumbling windows. Adding this to the improved time and space efficiency, makes time-reversed linear probing a canonical first choice for hash tables with time-outs.