In HashSet data structure, we should focus on hash function and collision handling.
Hash Function
A hash function assigns an address to store a given value. So, each unique value should have a unique hash value.
Collision Handling
since the nature of a hash function is to map a value from a space A into a corresponding value in a smaller space B, it could happen that multiple values from space A might be mapped to the same value in space B. This is what we call collision. Therefore, it is indispensable for us to have a strategy to handle the collision.
Overall, there are several strategies to resolve the collisions
Separate Chaining : for values with the same hash key, we keep them in a bucket, and each bucket is independent of each other.
Open Addressing : whenever there is a collision, we keep on probing on the main space with certain strategy until a free slot is found.
2-Choice Hashing: we use two hash functions rather than one, and we pick the generated address with fewer collision.
The origin: 705. Design HashSet, https://leetcode.com