Google Linux servers hit with $5m patent infringement verdict (The Register)

Knuth also raises (in my 2d edition copy) a case where there might be pointers to records from other than the hash-table index and some sort of reference counting might be needed to avoid deleting or reusing the actual record until the record actually becomes unreachable. This is the closest I have found that is a kind of "expiration." I don't know if that was in the 1973 edition cited in the patent itself. I obsserve that this is a situation that can arise in operating-system work, of course, and then race-condition avoidance, locking, and such come into the picture as well.

None of the other discussion of this kind of hash-table indexing, including in the exercises, touch any further on that nor the very specific claim of the patent.

The patent deals with removals where the expiration of a record is not by an effort to delete it by key but by virtue of some other condition that arises independent of use of the hash-table index. As I said, what the patent applies to is methods of removal that discover such expired records on the linked-list while it is being traversed on behalf of some other operation involving a record with the same hash code. The patent is quite specific about that, with some additional claims around details for limiting the number of such deletions done at one time.

An earlier comment mentioned a network application where some connections or network probes might time out. Another case might be indexes to the active records for running processes, or shared libraries and their stickiness, or something like that. I don't see this method being essential to any of those, but if it has been so used in Linux (or in some other way), an alternative is called for.