How to generate a random and unique id efficiently Python.
Using Python
So recently I came across a problem, we needed to generate a unique and random integer id for each new row in our relational SQL database. The problem statement was quite simple, we just wanted an integer based display id to be shown to the customer for each record, but we can’t show the incremental id as we don’t want to expose the number of records in our relation to the outside world.
As alpha-numeric characters were not allowed for some celestial reasons (pun intended), uuid and string hashing in hex digits was out of the picture.
One possible solution is to use a PSRN (pseudo random number generator), just like python’s random function, but there is no guarantee of uniqueness, as same number can occur multiple times in a random generator, an immediate fix is to keep track of all numbers that have already occurred and keep calling the function in hopes of finding a new number.
We could use an integer array to store all previously occurred numbers in sorted fashion as we get them and use binary search to check if the new generated number is present in the array.
Another possible solution is to use an array containing all possible 32-bit integers, and shuffle the first 10000000 values out of the array to obtain our sequence.
But the problem is that all these approaches work in non linear time and takes huge amount of space as well.
What we need is a Non-Repeating PSRN which can generate random integers which are also unique at the same time.
The solution lies in number theory called quadratic residues, lets say we want to have 2³² unique values each 2³² times the function is called, we then basically need a mapping for each number to a different number within our range.
This can be achieved by the expression x*x % p for input value x which should be less than p/2, where p is a prime number which follows the property of p ≡ 3 mod 4 (which in laymen terms means that p+1 should be completely divisible by 4).
For verifying the approach lets take p as 11 which satisfies p ≡ 3 mod 4 and call our function with values 1,2,3,4 and 5, we can see that the distribution is completely random.
0² mod11≡0
1²mod11≡1
2²mod11≡4
3²mod11≡9
4²mod11≡5
5²mod11≡3
Because Math loves symmetry, it just so happens that for values between p/2 and p, p minus x*x % p fits perfectly into the gaps.
So this way we can have a random and unique number for each number within the range of our magical prime number p.
The biggest prime number within 32 -bit integer range which follows p ≡ 3 mod 4 is 4294967291, which can be used to generate random numbers within this numbers range.
But lets say our table is used very less often and we don’t want such a big range, then what we can do is simply choose the prime number p which fits into our desired range.
This simple code can help us achieve that —
n = 100000 # our desired range
is_prime = [False, False] + [True] * (n - 1)
primes = [2]
for j in range(4, n + 1, 2):
is_prime[j] = False
for i in range(3, n + 1, 2):
if is_prime[i] and (i+1)%4 == 0:
primes.append(i)
for j in range(i * i, n + 1, i):
is_prime[j] = Falseprint(is_prime)# all primes within the range n that follow p≡3mod4
If you are very skeptical and still wanna test this, you can verify the uniqueness by this piece of code —
mp = 4294967291def unique_digit_hash(digit, mp):
if digit > mp:
print('not allowed')
else:
residue = (digit * digit) % mp
return residue if digit <= mp/2 else mp - residue
# Test uniqueness .....
test_set = dict()
for i in range(mp):
num = unique_digit_hash(i, mp)
if num in test_set:
print('math fails......!!!!!')
test_set[num] = '.'
As a result we can see that Math never fails.
Now, all that is left to do is utilize this in our original problem. Whenever we add a new item in the database, we can just flush the current session to obtain the incremental integer id and calculate its corresponding prime residue as display id and finally commit it.
