On segunda-feira, 19 de março de 2012 10.42.44, Thiago Macieira wrote: > [1] note that the order is stable. Two hashing tables with the same > elements must produce the same order.
Actually, thinking a little more about this, I might be wrong.
If two elements produce the same hashing value (be it a collision or because
of multiple insertions of the same item), their order is arbitrary. So suppose
that B and C produce the same hashing, the following two hashing tables are
still equal:
A, B, C
A, C, B
Moreover, two elements may be stored in the same bucket even if they have
different hashing values. And taken to an extreme, a degenerate hashing table
(all elements in the same bucket) could have any order and still be
equivalent.
Given those properties, I think we can safely say that relying on two hashing
tables with the same elements to have the same order is not acceptable.
I think that's the rule that I violated in the test. And note that Robin's
change wasn't intended to change the order of tables with the same elements --
as is Giuseppe's proposal -- but just to change the hashing function. I've
been trying to figure out how changing the function could have broken the test
and I guess I can explain now: iterating forward two hashes relies on undefined
behaviour related to collisions. The data used happened to work with the old
function by accident.
--
Thiago Macieira - thiago.macieira (AT) intel.com
Software Architect - Intel Open Source Technology Center
Intel Sweden AB - Registration Number: 556189-6027
Knarrarnäsgatan 15, 164 40 Kista, Stockholm, Sweden
signature.asc
Description: This is a digitally signed message part.
_______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
