Question

def hasht (key: str, base: int, table: int) -> int: TI Universal Hash function -post: returns a valid position (0 <= value < table size) - complexity: O(K) where K is the size of the key value 0 for cin key: value (value *base + ord (c)) % table return value I

   

Given the above hash function, when using a base=250726 and tablesize=250767, we get alot of collisions and very long probing chains. This results in a longer running time.

Why do using these numbers causes the mentioned effect??

Please answer in details with full explanation
thank you

Answer 1

I hope what you specified as tablesize is same as the variable table in the code above.

I single word the answer is, the base value should be greater than the tablesize of avoid collision.

Explenation :

I will try to explain this concept with a simple example.

Consider, you have a basket of 10 balls numbered as 1,2,3 etc. and you need to pick 5 balls with replacement. That is, you will take one ball, record the number and put it in the basket itself. Repeat this for 5 times to get the result.

In this case the capacity is 10 and the table size is 5(just saying an example). Here the chance of taking the same ball again (collilsion) is not mandatory,(sometimes it can happen: probalitity is 0.5)

More technical explenation

But when the table size becomes higher than the base,

say,

number of balls to pick (tablesize) = 15

total number of balls in basket( base) = 10

In this case it is sure that, for atleast once, the same ball will be picked(collision will happens).

There is a similar theorem called "Piegion hole principle in mathematics"

More technical explenation:

consider the line in the for loop, which calculated the hash value,

value = (value * base + ord(c)) % table

Here we are redicing the value , up to the value of "table" using the modulus operation("%")

ie, what ever the value of "(value * base + ord(c))" it will be fitted to the size of "table"

for understanding easily,

let

table = 10

and

(value * base + ord(c)) = 123

therefore : " (value * base + ord(c)) % table" will be equal to 3

That is the reason for the collision to happens in the above given values in the quesion.

____________________________________

Hope you understood , post a comment below, if have more doubt in the explenations.

Thank you