Re: Do we want a hashset type?

On Fri, Jun 9, 2023, at 13:33, jian he wrote:
> Hi, I am quite new about C.....
> The following function I have 3 questions.
> 1. 7691,4201, I assume they are just random prime ints?

Yes, 7691 and 4201 are likely chosen as random prime numbers.
In hash functions, prime numbers are often used to help in evenly distributing
the hash values across the range and reduce the chance of collisions.

> 2. I don't get the last return set, even the return type should be bool.

Thanks, you found a mistake!

The line

return set;

is actually unreachable and should be removed.
The function will always return either true or false within the while loop and
never reach the final return statement.

I've attached a new incremental patch with this fix.

> 3. I don't understand 13 in hash = (hash + 13) % set->maxelements;

The value 13 is used for linear probing [1] in handling hash collisions.
Linear probing sequentially checks the next slot in the array when a collision
occurs. 13, being a small prime number not near a power of 2, helps in uniformly
distributing data and ensuring that all slots are probed, as it's relatively prime
to the hash table size.

Hm, I realise we actually don't ensure the hash table size and step size (13)
are coprime. I've fixed that in the attached patch as well.

[1] https://en.wikipedia.org/wiki/Linear_probing

/Joel