4 ms·
With a 10 digit hash like that, collisions are already extremely unlikely, on the order of 1 in a trillion.
by anamexis 5y ago
With a 10 digit hash like that, collisions are already extremely unlikely, on the order of 1 in a trillion.
- CodesInChaos 5y agoMost repositories contain more than 2 commits.
- anamexis 5y agoFine, 3 in a trillion.
- CodesInChaos 5y agoYou're right that the chance that two specific 10 digit hashes collide is 1 in a trillion. But the chance of a collision between a specific commit and any other commit goes up linearly, so for the Linux repository it's about 1 million / 1 trillion so 1 in a million. The chance of a collision between a any two commits goes up quadratically (while it's small), and becomes ~50% when you reach the square-root of 1 trillion, i.e. 1 million. So there is a good chance the Linux repository already contains colliding 10 digit hashes, and if they don't exist yet, it'll likely happen during the next couple of years.
- faho 5y agoWhat you are alluding to is the "Birthday problem". https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem
- anamexis 5y agoYes, there is a good chance there is already a 10 digit hash collision in the Linux repository. But if you pick an arbitrary commit to cite in a research paper, it's still 1 in a million that that particular commit has a collision. And this is for a repo which has to be in the 99.999th percentile of number of commits.
- faho 5y agoThe linux kernel had 3 of those, in 2013: https://blog.cuviper.com/2013/11/10/how-short-can-git-abbreviate/ https://blog.cuviper.com/2013/11/10/how-short-can-git-abbrev... By now it's up to at least 7 (going by my clone of 5.12-rc1 that I had lying around), and it's becoming more likely. Those collisions happened with objects other than commits (of which there are more), but that's by no means guaranteed.