"Hashing" kavramını araştırabilirsiniz hocam.

Edit: Biraz yanlış anlamışım demek istediğinizi.

getID'de verdiğiniz en son değerin bir fazlasını bir değişkende tutun. Örneğin en son 5 döndüyse enSon adlı değişkende 6 olsun.
Bir adet min priority queue(min heap) olsun.
Her remove fonksiyonunda sildiğiniz değeri bu heape atın. getIDde ise ilk başta heape bakın heap boş değilse en küçük elemanı çeksin heap boşsa da enSon adlı değişkendeki değeri dönsün ve enSon adlı değeri tekrar döndüğü sayının bir fazlasına eşitlesin.