[Python-ideas] incremental hashing in __hash__

[jab at math.brown.edu]

On Fri, Dec 30, 2016 at 7:20 PM, Ethan Furman <ethan at stoneleaf.us> wrote:

> On 12/30/2016 03:36 PM, jab at math.brown.edu wrote:
>
> In the use cases I described, the objects' members are ordered. So in the
>> unlikely event that two objects hash to the same value but are unequal, the
>> __eq__ call should be cheap, because they probably differ in length or on
>> their first member, and can skip further comparison. After a successful
>> hash lookup of an object that's already in a set or dict, a successful
>> identity check avoids an expensive equality check. Perhaps I misunderstood?
>>
>
> If you are relying on an identity check for equality then no two
> FrozenOrderedCollection instances can be equal.  Was that your intention?
> It it was, then just hash the instance's id() and you're done.
>


No, I was talking about the identity check done by a set or dict when doing
a lookup to check if the object in a hash bucket is identical to the object
being looked up. In that case, there is no need for the set or dict to even
call __eq__. Right?

The FrozenOrderedCollection.__eq__ implementation I sketched out was as
intended -- no identity check there.


If that wasn't your intention then, while there can certainly be a few
> quick checks to rule out equality (such as length) if those match, the
> expensive full equality check will have to happen.


I think we're misunderstanding each other, but at the risk of saying the
same thing again: Because it's an ordered collection, the equality check
for two unequal instances with the same hash value will very likely be able
to bail after comparing lengths or the first items. With a good hash
function, the odds of two unequal instances both hashing to the same value
and having their first N items equal should be vanishingly small, no?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20161230/bbecf12f/attachment.html>