Hash table linear probing

[@manhhiep1627]

best explanation ever. this channel is so underrated

[@brunokawka]

Your explanations are truly fantastic; concise and crystal clear with the readable and consistent design system

[@Indian73641]

I was struggling to understand prime number requirement, you explained so clearly…Thank You

[@augustina3657]

Oh thank god. I've been looking everywhere for something like this

[@pushkar260]

b will be obselete, because it's not doing anything. If there is a cycle the cycle will just be offseted by the value 'b' and thus has no real effect

[@User-cv4ee]

offset by b or (b mod n)

[@aparup53]

@@User-cv4ee b mod N

[@daumtto]

Thanks bruh

[@brooklynwright7109]

thank you so so much for your crystal clear explanations! they were super useful :) keep up with the good work

[@ioanacrisan3684]

Thank you for these series!

[@svrmmb]

The reason b is sometimes referred to as "obsolete" is that it doesn't contribute to the generation of distinct probe sequences as much as a does. The offset b is often considered a constant that can be adjusted, but it doesn't affect the periodicity of the probe sequence.

[@jadalhamwi1543]

About b Obsoletion at the first part when x is tiny(x = 1 , 2 , 3) b won't be an obsolete but when we reach a particular value the b will reach to obsoletion state because it makes not that much impact on the probing function for higher values of x not sure if that's right but that's my point of view

[@bluejimmy168]

At 8:25, you said that 1 is a popular choice because GCD(N,1) is good no matter what the choice of N is. If that is the case, why would I ever choose 5 like your next example? If 1 works and is good for any size of N table size, is there any benefit of not choosing 1?

[@jadalhamwi1543]

Phenomenal Explaination Thank you very much Keep it up !!

[@MuhammadAhmad-qt6yq]

TOO GOOD EXPLANATION

[@pedramhaqiqi7030]

is that a mistake where the keyhash is not mod N, in the other videos the key hash is H(k) mod N before u probe

[@marcc1179]

Hi, the teacher said the linear probing can cause clustering. Could you please make video to explain this?

[@alikhansmt]

I think thats what he calls cycles that are less than size of the table. That is some slots/indices of hash tables may never get utilized if the linear probing parameters (a,b) are not chosen carefully.

[@constantijndekker8343]

I think your teacher was referring to something different. This is a phenomenon that occurs when your hash function is not good enough. Many consecutive elements in your table will form groups (cluster together) and if you insert into such a large group, it could take a lot of time. Clustering can be avoided by using quadratic probing, but linear probing has better cache performance.

[@huyvole9724]

Teacher, in the previous example you have a = 6 and N = 9 and you have alpha = a / N = 0.67 Why in the next example you have a = 5 and N = 12 and you have alpha = a / N = 0.35. Why not 5 / 12 = 0.4167 ???

[@WilliamFiset-videos]

The threshold is computed with multiplication, so T = α * N. Remember alpha is usually a constant so it does not change.

[@huyvole9724]

Thank you teacher. Where did alpha appear?

[@WilliamFiset-videos]

It's a constant you define between 0 and 1. It's just a percentage you define to determine when you should increase the size of the table.

[@huyvole9724]

So in the test at school, the question in the test will give me alpha, right?

[@WilliamFiset-videos]

Think of it as the threshold is the number of elements once reached you need to increase the hash table size and Alpha as the percentage of elements you need to reach to increase the table size