I want to map an integer (let's say 32bits) to a valid path. The integer is an autoincrement value stored in the database.
I also don't want at any case any folder to have more than N subfolders. That is because in WIN-NTFS (for example) after a specific number (around 1000) things are going really slow.
So I devised a pattern where each integer is mapped to hex groupped in two digits. That creates 4 folders for each integer
1 -> '00/00/00/01' 2000 -> '00/00/07/D0' 70000 -> '00/01/11/70' etc
All nice and well.
But if you notice after creating the first 257 entries
the folder '00/00/00' will have 256 entries ('00' to 'FF') folder '00/00/01' will have one entry folder '00/00' will have 2 entries ('00' and '01') and last folder '00' will have just one entry.
The graph is higly unbalanced, the OS to finally find the folder '00/00/00/55' will have to search between 1+1+2+256 = 260 entries. If the graph was balanced it would be a search of 4 * Pow(257,1/4) =~ 16 entries
And my question is:
Is anyway I can transform the integer A to an integer A' that has the following properties:
- It's 1:1 transformation
- Can be inversed (for each A' I can can easily find A)
- For each 1..N, creating folders using the A' hex value, each folder has no more than Pow(N,1/4) entries
EDIT: I did test the two ciphers. The problem is that crypt functions output the whole 32bit range. I mean after 1000 increments and after each byte has a random value, the root folder has 256 different values (subfolders) and each of them have 1 or 2 entries. It's the same situation I started with. It's only inversed