[Mesa-dev] [PATCH 3/4] util: Change util/set to use quadratic probing

[Jan Ziak]

On Fri, Feb 10, 2017 at 7:03 AM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> On Thu, Feb 9, 2017 at 4:16 PM, Jan Ziak <0xe2.0x9a.0x9b at gmail.com> wrote:
>> Hello
>>
>> IMPORTANT NOTE: Using the uint32_t data type, quad_hash*quad_hash will
>> overflow as soon as the hash table has more than 2**16=65536=64K
>> elements. To enable more than 64K elements in hash table, the data
>> types need to be changed to uint64_t - unfortunately uint64_t
>> arithmetic operations will slow down the hash table in 32-bit OpenGL
>> apps.
>
> This actually doesn't matter, since at the end of the day we only need
> the result modulo the table size which is a power of two -- even if
> the multiplication overflows, the lowest n bits (if the table size is
> 2^n) are still correct, so we get the same answer as long as we use at
> least n bits.

Yes, you are right. I sent the post before realizing it.

(k+x*x)%m
= (k+(x*x)%m)%m
= (k+((x*x)%A)%m)%m, A=n*m, A>=m, n>=1

m: hash table size, a power of 2
A: 2**32 in case of uint32_t