Dictionary in Python
jstok at bluedog.apana.org.au
Tue Mar 14 15:19:16 CET 2000
Hrvoje Niksic wrote in message <9t9pusynelo.fsf at mraz.iskon.hr>...
>Alex <alex at somewhere.round.here> writes:
>> > Does anyone know how dictionary is implemented in Python(such as hash
>> > table, heap, linked list)? If my dictionary increases in size, how
>> > much is the impact on performace?
>> Based on discussions I've seen in the newsgroup, I'm pretty sure
>> it's a hash table. My experience has been that I can stick about
>> 1.5 million string keys in a dictionary before collisions start to
>> hurt me.
>Maybe your problem are not collisions, but cache misses.
I've been reading the sources. Python dictionaries are dynamically
resizable hash tables with collisions resolved by probing.
More information about the Python-list