used for searching an element in an ordered set of elements.
similar to balanced trees
like in a linked list, elements are connected one to the other, and we have to traverse the list elements, one by one.
but in a skip list, the elements can be skipped.
consider a sorted linked list as the slowest lane, as there are lots of elements in it.
consider another subsequence of the same linked list, where only first and last elements are connected, as the fastest lane
also another subsequence where first, middle and last elements are connected as another lane.
How searching works in skip list
lets say we are trying to find a node with value V
we try to find a node whose next value is greater than V
the search starts in the top left(express lane), starting from first element.
If we find the element we are done.
If we find an element which is less than V and whose next element is greater than V, we drop down to the below level, and continue doing the same
Time complexity of different operations in skip list(similar to balanced trees)
Search => Average => O(log n), Worst => O(n)
Insert => Average => O(log n), Worst => O(n)
Search => Average => O(log n), Worst => O(n)
Search => Average => O(log n), Worst => O(n)
Bloom Filter
space-efficient probabilistic data structure to test the existence of an element in the set.
mostly implemented using a bitset of size N and K hash functions.
returns either "definitely not in set" or "may be in set"
the above means that false positives are possible(algo returned false result that it was in set when it was not) but there are no false negatives(algo returned false result that it was not present in set when it was)
How it works
Each implementation of bloom filter uses one or more hash functions.
Lets say a bloom filter uses 2 different hash functions.
Each value present in the set is converted to one hashvalue by each of the hash functions.
So, lets say we have a set S in which we have element E which has two hash values H1 and H2 for hash functions.
How hash functions H1 and H2 hash the value E to turn on a bit B
In checking whether a value 'e' is present in the Set S, we will again hash 'e' using H1 and H2 hash functions
If it falls on a turned off bit, that means that 'e' is definitely not present in S
If it falls on a turned on bit, that means that 'e' may be present, because that bit could be turned on by someone else other than 'e'.
applications of bloom filter
checking whether an element exists on disk before doing an I/O. If it doesn't exist on disk, don't do the io.
approximating user counts, if the user doesn't exist in set, increment the count, if may be exists, don't increment.
have you seen an article before, if no, show it to the user, if may be, don't show.