Use primes for hashtable size

[Maxim Dounin]

Hello!

On Tue, May 30, 2017 at 03:28:03PM +0500, Andrew Borodin wrote:

> Hi, nginxers!
> 
> We often use hashtable sizes equal to the power of 2. This can be
> damaging for a hashtable. I haven't found any mitigation for this in
> nginx code. So I made my own. If this issue is addressed somewhere
> just ignore my message. Or I'd be happy if someone will point me it.
> 
> For the explanation of problem see
> https://stackoverflow.com/questions/3980117/hash-table-why-size-should-be-prime
> 
> Code is checked for correctness of ngx_hash_min_prime(), I haven't
> done any regression testing, sorry.

The maximum size of hash table as specified by the hinit->max_size 
field is indeed maximum size, and not the size of the hash table.  
Following code in the ngx_hash_init() will try hard to find to 
find out an optimal hash size for a given set of values within the 
maximum size specified, and will test all the prime numbers as 
well.

I see no reasons to additionally limit the maximum size to a prime 
number.  If you think there are some, please be more specific.

-- 
Maxim Dounin
http://nginx.org/