public inbox for [email protected]
help / color / mirror / Atom feedFrom: Joel Jacobson <[email protected]>
To: jian he <[email protected]>
Cc: Tomas Vondra <[email protected]>
Cc: [email protected]
Subject: Re: Do we want a hashset type?
Date: Fri, 09 Jun 2023 13:56:28 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <CACJufxE=QbDzYYay4Z6MJ=BqdkYiHi_P34YOKduyQ0yyXmMhOw@mail.gmail.com>
References: <[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<CACJufxE=QbDzYYay4Z6MJ=BqdkYiHi_P34YOKduyQ0yyXmMhOw@mail.gmail.com>
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
Attachments:
[application/octet-stream] hashset-1.0.0-joel-0002.patch (687B, ../[email protected]/3-hashset-1.0.0-joel-0002.patch)
download | inline diff:
diff --git a/hashset.c b/hashset.c
index d60ccc8..93c8d8c 100644
--- a/hashset.c
+++ b/hashset.c
@@ -80,6 +80,15 @@ hashset_allocate(int maxelements)
hashset_t *set;
char *ptr;
+ /*
+ * Ensure that maxelements is not divisible by 13;
+ * i.e. the step size used in hashset_add_element()
+ * and hashset_contains_element().
+ */
+ while (maxelements % 13 == 0) {
+ maxelements++;
+ }
+
len = offsetof(hashset_t, data);
len += (maxelements + 7) / 8;
len += maxelements * sizeof(int32);
@@ -387,8 +396,6 @@ hashset_contains_element(hashset_t *set, int32 value)
/* move to the next element */
hash = (hash + 13) % set->maxelements;
}
-
- return set;
}
Datum
view thread (18+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: Do we want a hashset type?
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox