HashMap drain from iterator

I have a HashMap which should from time to time filter out nodes (either remove them immediately, or split them out into a new HashMap) according to two rules:

  • If nodes have expired, they should be removed or moved out of the HashMap.
  • If the number of nodes have exceeded a threshold, the excess should be removed or moved out but it should select the oldest nodes for removal/move.

Handling expired entries is easy and will be even easier once HashMap::drain_filter() is stabilized.

Enforcing the maximum number of nodes is a little more complicated, because information about all nodes is needed in order to know which nodes are the "oldest".

I have a working solution for all cases I need, but some of them rely on HashMap::drain():ing the entire map, enforcing constraints, and then putting the "untouched" nodes back into the map.

I'm wondering if it would be possible to do something similar to HashMap::drain_filter but rather HashMap::drain_from_iter()? So my application would generate a list of key references (from the HashMap), transform that list into an iterator and then move it to HashMap::drain_from_iter(), which would output a Drain iterator of all the selected key/value pairs.

Would this be possible?

More specifically, I know it's not allowed to hold references to the HashMap's keys and call mutable HashMap functions, but would it be allowed to move an iterator of key references into a mutable method?

Is this not a LRU cache? You can usually solve the problem of removing and putting back all the items in the HashMap by maintaining a separate list of nodes which is sorted on removal time, most often it's a priority queue or a heap or something like that. These data structures allow for fast (constant or logarithmic-time) lookup of the maximal element, so removing the excess should only take O(excess) time, instead of O(all items).

1 Like

You can use drain_filter in stable Rust today by using the hashbrown crate directly. Or you can use the standard library’s retain method, for cases where you don't need to access the removed items.

You might be able to implement something like this on indexmap which lets you store usize indices to its entries, as an alternative to references.