3 ms·
I think if you do it this way you can extend the tree without recalculating all the entries. I can just add the next prime to the list of primes.
by doomrobo 11y ago
I think if you do it this way you can extend the tree without recalculating all the entries. I can just add the next prime to the list of primes.
- ball_of_lint 11y agoIn that case you could just use a binary tree taking from lsb to msb, and then expand down a level only on collisions. The reason for primes is that it is more likely to distinguish between numbers earlier in the tree so that it doesn't get as deep as fast. Where a binary tree couldn't tell 0 and 256 apart until the 8th level, this could tell them apart at the second level: 0 mod 3 = 0, 256 mod 3 = 1