python dictionaries search complexity compared to java hashmap/hashtable

Question

Possible Duplicate:
How are Python’s Built In Dictionaries Implemented

I am fairly new to python and have a background in java. I was wondering whether the dictionary in python has the same search complexity as for hash maps in java. Example: searching for a key in a hash table/map in java is a constant time operation, I was wondering whether searching for a key in a dictionary in python is also a constant time operation. I have read through a few pages of python documentation regarding mapping but it doesn't seem to indicate any hashing of keys of dictionary in python so I was wondering whether:

searching keys in a dictionary in python was constant time operation.
If so how do they achieve this constant time search without hashing?

What made you so sure that `dict` wasn't based on a hash table in the first place? — abarnert, Jan 08 '13 at 23:14

score 2 · Accepted Answer · answered Jan 08 '13 at 22:13

2

Python dictionaries have O(1) search complexity.

See the Time complexity wiki page.

Python dictionaries are implemented as a hash table, and keys are hashed; you can influence the hashing by implementing a __hash__ method.

answered Jan 08 '13 at 22:13

Martijn Pieters

1,048,767
296
4,058
3,343

And the OPs point 2 would be redundant – Jon Clements Jan 08 '13 at 22:14
do you know if they achieve this by hashing the keys in the dictionaries or by some other method? I would really appreciate some input regarding this matter. – anonuser0428 Jan 08 '13 at 22:14

python dictionaries search complexity compared to java hashmap/hashtable

1 Answers1