Timeouts With Time-Reversed Linear Probing

The authors consider portable software implementations of hash tables with timeouts. The context is a high volume stream of keyed items. When a new item arrives, they 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 net-flows from routers, and helping firewalls reuse decisions from recent packets with the same key.