2010/11/2 Kenneth Marshall <k...@rice.edu>: > Given that our hash implimentation mixes the input data well (It does. > I tested it.) then a simple rotate-and-xor method is all that should > be needed to maintain all of the needed information. The original > hash function has done the heavy lifting in this case.
Even with the perfect hash function for the elements, certain combinations of elements could still lead to massive collisions. E.g., if repeated values are typical in the input data we are talking about, then the rotate-and-xor method would still lead to collisions between any array of the same values of certain lengths, regardless of the value. In Tom's implementation, as he mentioned before, those problematical lengths would be multiples of 32 (e.g., an array of 32 1s would collide with an array of 32 2s would collide with an array of 32 3s, etc). Nicolas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
