From 7149b128dc12ece64c182962dc4f882ea7559d0c Mon Sep 17 00:00:00 2001 From: Robert Haas Date: Mon, 23 May 2011 15:17:18 -0400 Subject: Improve hash_array() logic for combining hash values. The new logic is less vulnerable to transpositions. This invalidates the contents of hash indexes built with the old functions; hence, bump catversion. Dean Rasheed --- src/backend/utils/adt/arrayfuncs.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'src/backend/utils/adt/arrayfuncs.c') diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c index a8af6f09537..3e43e951e10 100644 --- a/src/backend/utils/adt/arrayfuncs.c +++ b/src/backend/utils/adt/arrayfuncs.c @@ -3533,7 +3533,7 @@ hash_array(PG_FUNCTION_ARGS) int ndims = ARR_NDIM(array); int *dims = ARR_DIMS(array); Oid element_type = ARR_ELEMTYPE(array); - uint32 result = 0; + uint32 result = 1; int nitems; TypeCacheEntry *typentry; int typlen; @@ -3617,11 +3617,17 @@ hash_array(PG_FUNCTION_ARGS) } /* - * Combine hash values of successive elements by rotating the previous - * value left 1 bit, then XOR'ing in the new element's hash value. + * Combine hash values of successive elements by multiplying the + * current value by 31 and adding on the new element's hash value. + * + * The result is a sum in which each element's hash value is + * multiplied by a different power of 31. This is modulo 2^32 + * arithmetic, and the powers of 31 modulo 2^32 form a cyclic group of + * order 2^27. So for arrays of up to 2^27 elements, each element's + * hash value is multiplied by a different (odd) number, resulting in + * a good mixing of all the elements' hash values. */ - result = (result << 1) | (result >> 31); - result ^= elthash; + result = (result << 5) - result + elthash; } /* Avoid leaking memory when handed toasted input. */ -- cgit v1.2.3