可能なすべてのnbrについて、ビットマップを使用して記録するのはどうですか 、その値が使用されているかどうか？
値が取得されたことを記録するには、SETBITを使用します ：
SETBIT key [nbr] 1
無料のnbrを見つけるには BITPOSを使用する ：
BITPOS key 0
競合状態を回避するには、get-and-setがアトミックであることを確認する必要があります。 [OPはフォローアップの質問でこれに対処します。]
これにはほとんどメモリが必要ありません（65536の可能な値に対して8Kバイト）。 BITPOS はO（n）ですが、それが実際の問題になる可能性は低いです。