[hnrj95]

Great article, but slight issue. The iteration expression shifts left by 2, effectively limiting the height of the tree to 32. You probably want a rotation instead; otherwise you’ll be locked into child 0 from depth 32 down. I suppose with a good hash the manifestation would be rare.

[cruegge]

It's not limited to 32, but afterwards search will be linear along child[0]. Using rotation would not make a difference, since you're in the collision case already, so you would effectively always branch to the same child for levels below 32.

[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.

[cruegge]

> Yes, I thought this was clear from my statement.

Yeah, sorry, wasn't really necessary to repeat that point. I was too focused on the "limiting the height of the tree to 32" formulation.

I have to admit that I don't quite understand what invariants along the lookup you mean. All lookups that reach a particular node on level 32 have the same hash, so regardless of how you compute the branch from the hash below level 32, they will always follow the same path starting from there (except for terminating at different levels, obviously). So nodes only ever have one child at most, and there's no loss in simply picking child 0 in all cases.

Sorry if what I'm describing is again obvious, maybe I just don't understand your point correctly.