Dictionary in Python

[Jason Stokes]

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.