"Another probing sequence used in Python dictionaries is quadratic probing" is contradicted by the very source code you link to.
Compare your "but it can also cause some slots to be skipped or repeated" with dictobject.c's "repeating that 2^i times generates each int in range(2^i) exactly once (see any text on random-number generation for proof)."
How are you coming up with all of these wrong things? Start with why you thought Python used MurmurHash3.
I wrote it as a general article on python dictionaries.
>>Regarding Compare your "but it can also cause some slots to be skipped or repeated"
- I think its correct - Let me try to explain this means that some slots may never be probed or may be probed more than once, which wastes time and space. For example, if the array size is 8 and the original index is 3, then quadratic probing will try the following indexes: 3, 4, 7, 4 (repeated), 3 (repeated), 4 (repeated), and so on. As you can see, indexes 0, 1, 2, 5, and 6 are never probed.
And yes you are correct - Python does not use the MurmurHash3 algorithm for hashing objects in dictionaries. My bad I mixed up two different things and though it uses this mmh3 for hashing. I have updated it now and made it more like my understanding of python dictionaries.
Thanks, for your review and pointers to fix it. Will keep it in my mind to get it reviewed before publishing any article.
eesmith|2 years ago
You've made it a different sort of wrong.
"Another probing sequence used in Python dictionaries is quadratic probing" is contradicted by the very source code you link to.
Compare your "but it can also cause some slots to be skipped or repeated" with dictobject.c's "repeating that 2^i times generates each int in range(2^i) exactly once (see any text on random-number generation for proof)."
How are you coming up with all of these wrong things? Start with why you thought Python used MurmurHash3.
ankit_it09|2 years ago
>>Regarding Compare your "but it can also cause some slots to be skipped or repeated" - I think its correct - Let me try to explain this means that some slots may never be probed or may be probed more than once, which wastes time and space. For example, if the array size is 8 and the original index is 3, then quadratic probing will try the following indexes: 3, 4, 7, 4 (repeated), 3 (repeated), 4 (repeated), and so on. As you can see, indexes 0, 1, 2, 5, and 6 are never probed.
And yes you are correct - Python does not use the MurmurHash3 algorithm for hashing objects in dictionaries. My bad I mixed up two different things and though it uses this mmh3 for hashing. I have updated it now and made it more like my understanding of python dictionaries.
Thanks, for your review and pointers to fix it. Will keep it in my mind to get it reviewed before publishing any article.