Question

What will be the size of the hash table in case of linear probing, if our hash function does something like this, value%20 ?

Answer 1

Can you be more specific? What language are you coding in? What are you trying to do?

Answer 2

i'm coding in C++ . I'm just preparing for my exam so i want to know that if the hash function does something of this sort, value%20 , then what should be the size of our hash table , if we are to insert and search the value using linear probing.

Answer 3

%20 would generate values in between 0 and 19 , so should the size of the hash table be 20 or double of that, 40 ?

Answer 4

It depends on how you implement the linear probing and how many total items you want your hash table to hold. If you're implementing linear probing by basically leaving an empty spot adjacent to each spot you'll try to put an item in first, then yes, it'll have to be size 40. Also, if you want more than 40 items in the table, then you'll need your table to be bigger than 40 slots.

Answer 5

It'll be of size 20, not 40. Having an array size of 40 when your hash function only hashes to slots 0-19 would be pointless. The only way linear probing affects this question is that you wouldn't have to worry about small array sizes as would be the cash with quadratic probing.

Just remember, the point of a hash function is to distribute keys and evenly as possible. If you are hashing to slots 0-19 and used an array of size 40, the keys are on average only being distributed to the first half of all the available space, meaning more collisions and decreased performance