Ja zaproponuje takie rozwiązanie.

1. Oprócz mapy kluczy, utworzyć kolejkę par [ID, Item].
2. W konstruktorze obiektu Item
a) pobrać N > 1 par z kolejki,
b) usunąć z mapy wpisy z martwymi referencjami,
c) pary z żywymi referencjami dodać na koniec kolejki,
d) utworzyć parę [ID, Item] dla bieżącego obiektu i dodać ja do mapy,
oraz na koniec kolejki.

Dla przyjętej wartości N można wyliczyć, procentową zajętość
niewykorzystanej pamięci, dla pesymistycznego przypadku.

Pozdrawiam,
- Bastek -