How can I create 10-character, unique codes with no collisions, but without being predictable?

Here is a process to hand out unique codes, without requiring any storage or memory:

Step 1. Use format-preserving encryption to define a block cipher that maps an integer from ${0,1,dots,36^{10}-1}$ to an integer from ${0,1,dots,36^{10}-1}$.

Step 2. Pick a secret key for this block cipher.

Step 3. The $i$th code you hand out will be the encryption of $i$ under your secret key. Now you only need to store a counter with the largest value of $i$ you have used so far.

To keep track of which codes have been redeemed, you need storage proportional to the number of codes redeemed. So, store a list of codes that were previously redeemed, or use a bitmap, or use any other data structure. There's no way to avoid that much storage.

$36^{10}$ is approximately 52-bit. Now;

• Generate a secret key $k$ for AES-128
• Encrypt the rowID with $text{unique_code} = operatorname{AES}_k(rowID)$, and assuming that the key never changes.

Since AES with a key selects permutation for all possible permutations from $2^{ell}$ to $2^{ell}$, where $ell$ with a key, then by fixing a key, you fixed a secret permutation. Therefore the output is distinct for every distinct input. It is unpredictable since AES is assumed to be secure against Known-Plaintext Attacks.

You could use a bitmap. Map the values to some sort of numerical order and then use that number as a map the proper bit. The first int (assuming 32-bit and unsigned) would store values 0-4,294,967,295 the second int would store 4,294,967,296 - ... and so on. Even with some overhead this should all easily fit into 10 MB and lookup/setting values is quick since you know the size beforehand and everything can be done with bit manipulation.

Once you get a code in you check if that bit has been set to 1, if not then its valid and you set that bit to 1.