Not true. The process uses a different seed each time specifically to prevent this.
That’s exactly what happens. But it only needs to check against filenames. It depends on the file system and hardware, but on my slowest node hardware this process can take hours. On the fastest which is ssd accelerated, it takes a few minutes at most. If you turn on debug logging you can see the retain process running and going through files which are moved to trash.