[issue30671] dict: improve lookup function

Tim Peters added the comment: Actually, there is something to be gained here, for smaller tables. The simple formulas for the expected number of probes under uniform hashing are upper bounds, and are significantly overstated when the load factor is very high (not a concern for Python) or the

[issue30671] dict: improve lookup function

Tim Peters added the comment: BTW, I should have spelled this out earlier: recall that x and y collide on the first probe if and only if x = y (mod 2**k) [1] The second probe never happens unless they do collide on the first probe, so when looking at the second probe we can assume

[issue30671] dict: improve lookup function

Tim Peters added the comment: Dmitry, I suggest you spend more of the time you give to thinking to writing code instead ;-) But, really, that's the easiest & surest way to discover for yourself where your analysis is going off in the weeds. For example, issue 28201 was both simpler and worse

[issue30671] dict: improve lookup function

Dmitry Rubanovich added the comment: A few notes on my motivation and other comments I made(not necessarily in the order of significance): 1. I started looking at this because of the fix in Issue28201. It effectively improves on the difference between

[issue30671] dict: improve lookup function

Tim Peters added the comment: I don't see a reason to keep this open, but I haven't been able to follow the OP's line of argument. My best _guess_ is that they're chasing illusions based on not understanding (or grossly undervaluing) that the primary point of the perturb logic is to

[issue30671] dict: improve lookup function

Raymond Hettinger added the comment: Can this be closed now? -- ___ Python tracker ___ ___ Python-bugs-list

[issue30671] dict: improve lookup function

Tim Peters added the comment: The attached hashsim.py pretty much convinces me there's nothing left to be gained here. It shows that the current scheme essentially achieves the performance of theoretical "uniform hashing" for string keys, for both successful and unsuccessful searches, as

[issue30671] dict: improve lookup function

Serhiy Storchaka added the comment: I totally concur with Tim. Your script test all hash codes in range(1<

[issue30671] dict: improve lookup function

Tim Peters added the comment: Yes, any scheme whatsoever that guarantees to visit every int in range(2**i) meets the "correctness" part. But I concur with Inada: "head arguments" aren't compelling here, not even if I understood what they were saying ;-) If you implement it and demonstrate

[issue30671] dict: improve lookup function

Dmitry Rubanovich added the comment: Changing the title, to remove "simplify", since the discussion revealed that the potential improvement would have to be treated as a special case and, therefore, would not simplify the code. -- title: dict: simplify and improve lookup function ->