I plan to build a unique file name based on its content. For example, by its SHA256 hash. Files with the same content must have the same name.

The easiest way is to convert hash to a hex string. A file name will be 32 bytes length * 2 = 64 characters. This is pretty long name to operate with. How to make it shorter?

I implemented a sort of "Base32" coding - a vocabulary string that includes digits and 22 letters. I use only five bits of every byte to build file name with 32 characters. Much better.

I am looking for a balance between file name length and low collision probability. If the number of files is expected to be less than 500K, how long should the filename be? 8? 16? 24? 32?

Is there any recommended method to build short unique filenames at all?

CodePudding user response：

If you use an N-bit cryptographic hash on M files, you can estimate the probability of at least one collision to be M²/2^{N 1}

For 500K files, that's about 1/2^N-37

Using base32, 16 chars gives probability of collision 1/2⁴³ -- a few trillion to 1 odds.

If that won't do, then 24 chars gives 1/2⁸³.

If you're willing to check them all and re-generate on collision, then 8 chars is fine.

CodePudding user response：

Number of collisions depend on the content of the files, the hash-algorithm and the length of the hash.

In general: The longer the hash-value is the less likely are collisions (if your content does not especially provoke collisions).

You cannot avoid the possibility of collisions unless you use the content as file-name (or a lossless compression of it).

To shorten the filenames you could allow more different characters for the file-name. (But we aware what characters your OS allows and which you are willing to use).

I would go for a kind of base32 encoding to avoid problems with filesystems that do not distinguish between upper and lower case character.