Comment

Comment by hnrj95

“Afterwards search will be linear along child[0]”

Yes, I thought this was clear from my statement.

“Rotation would not make a difference”

It would. The offsets generated by the hash would repeat every 32 shifts, but the absolute addresses given in the collision cases are a random construction based on the history of the tree at that point, so despite the offsets’ repeating, the tree’s invariants along the lookup are likely to be preserved.

parent hnrj95 3 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton