And a less satisfying solution, that still keeps good bounds and that can use off-the-shelf collections: Keep a max-heap current of currently used identifiers, and a min-heap freed. If you want a new id, use the minimum of the smallest id in freed and the the successor of the largest element in current. When using an id from freed, remove it from freed, when using any id, add it to current, when stopping usage of an id, move it from current to freed.