Hash in python

Question

Hello dear learners,

Could you please explain how hash method work in python for dictionaries and sets? What is the formula behind it?

And how it reduces the overall speed of the code?

Thank you!

Answer 1

Public source code of the hash function in cpython:
https://github.com/JUMP_LINK__&&__python__&&__JUMP_LINK/cpython/blob/main/Python/pyhash.c

Basically hash is a function that generates a unique identifier which depends on the data itself. You can consider it as the fingerprint of the object. When you lookup keys in a dictionary or elements of a set, it is very quick because only the hashes are compared, not the entire object.

Answer 2

Hash is calculated for each value separately when it is inserted (appended).

Answer 3

Tibor Santa, Thank you for your response!
Could you please explain why it is faster? Logically it requires extra time for computing hashes too.

Answer 4

I suggest you read about hash tables.

https://en.m.wikipedia.org/wiki/Hash_table

You could imagine them as a library catalog, which contains the reference to all the books in the library and makes it really quick to find, on which shelf to find your book.
Hash tables have practically O(1) time complexity for lookup, which means that the speed does not depend on the size of the collection. Even for a large dictionary or set, the lookup by key is instant, Python does not need to browse through all the elements. That is why it's very fast.

Answer 5

Tibor Santa, Thank you! Now it is more clear.
Could you please also explain at what time is the hash value for a dictionary or set calculated? I mean is it already precalculated for all values in python or is it calculated in the time of data set execution?

Answer 6

Tibor Santa Thanks! You helped me a lot. Really appreciate it :)