The described technology is directed towards efficiently invalidating cached data (e.g., expired data) in a hash-mapped cache, e.g., on a timed basis. As a result, data is able returned from the cache without checking for whether that data is expired, (if desired and acceptable), because if expired, the data is only briefly expired since the last invalidation run. To this end, a data structure such as a linked list is maintained to track information representative of hash-mapped cache locations of a hash-mapped cache, in which the information tracks a sequential order of entering data into each hash-mapped cache location. An invalidation run is performed on part of the hash mapped cache, including using the tracking information to invalidate a sequence of one or more cache locations, e.g., only the sequence of those locations that contain expired data.