[Development] qHash / QHash changes

[Thiago Macieira]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 190 bytes
Desc: This is a digitally signed message part.
URL: <http://lists.qt-project.org/pipermail/development/attachments/20120319/130a722b/attachment.sig>