Que tal usar Bitmaps para gravar, para cada possível
nbr , se esse valor é usado ou não? Para registrar que um valor foi obtido, use
SETBIT :SETBIT key [nbr] 1
Para encontrar um
nbr gratuito use BITPOS :BITPOS key 0
Para evitar condições de corrida, você deve certificar-se de que seu get-and-set seja atômico. [O OP aborda isso em uma pergunta de acompanhamento.]
Isso exigirá muito pouca memória (8K bytes para 65.536 valores possíveis).
BITPOS é O(n), mas é improvável que seja um problema real. 
