educative.io

Don't understand the diagram and "The element X definitely is not in the set, since it hashes to a bit position containing 0."

Courses
, ,
#1
  • The element X definitely is not in the set, since it hashes to a bit position containing 0.

The diagram has spots where it is pointing to 1. Can this be explained in more detail?

#2

If ANY of the bits is zero, then the element is definitely not present in the set.

From the lesson, here is how we find out if an element could be present or definitely not present in the set:

To test if an element is in the set, feed it to the hash functions to get k bit positions.

  • If any of the bits at these positions is 0, the element is definitely not in the set.
  • If all are 1, then the element may be in the set.
#3

Hi, two questions:

  1. Can you please explain further why for the given hash functions, some might return 1 while others might return 0?

  2. Why do all bits equaling one still present the possibility of a false positive? What is the cause?

Thank you!