Time complexity of accessing a Python dict

by

See Time Complexity. The python dict is a hashmap, its worst case is therefore O(n) if the hash function is bad and results in a lot of collisions. However that is a very rare case where every item added has the same hash and so is added to the same chain which for a major Python implementation would be extremely unlikely. The average time complexity is of course O(1).

The best method would be to check and take a look at the hashs of the objects you are using. The CPython Dict uses int PyObject_Hash (PyObject *o) which is the equivalent of hash(o).

After a quick check, I have not yet managed to find two tuples that hash to the same value, which would indicate that the lookup is O(1)

l = []
for x in range(0, 50):
    for y in range(0, 50):
        if hash((x,y)) in l:
            print "Fail: ", (x,y)
        l.append(hash((x,y)))
print "Test Finished"

CodePad (Available for 24 hours)

More Related Contents:

  1. Why can a Python dict have multiple keys with the same hash?
  2. Hashing a dictionary?
  3. Is a Python dictionary an example of a hash table?
  4. Python dictionary keys. “In” complexity
  5. Python dictionary : TypeError: unhashable type: ‘list’
  6. How to sum all the values in a dictionary?
  7. Iterating over dictionaries using ‘for’ loops
  8. Delete an element from a dictionary
  9. How to merge multiple dicts with same key or different key?
  10. Rename a dictionary key
  11. Modifying a Python dict while iterating over it
  12. Safe method to get value of nested dictionary
  13. How to convert an XML string to a dictionary?
  14. How to sum dict elements
  15. Why do -1 and -2 both hash to -2 in CPython? [duplicate]
  16. How to print a dictionary’s key?
  17. How to print a dictionary line by line in Python?
  18. TypeError: unhashable type: ‘dict’, when dict used as a key for another dict [duplicate]
  19. How to create a dictionary from a line of text?
  20. Convert list of strings to dictionary
  21. Return first N key:value pairs from dict
  22. Python: Elegantly merge dictionaries with sum() of values [duplicate]
  23. Efficient way to remove keys with empty strings from a dict
  24. How to convert a list to a dictionary with indexes as values?
  25. “unpacking” a passed dictionary into the function’s name space in Python?
  26. How to detect if any element in a dictionary changes?
  27. Python Pickling Dictionary EOFError
  28. Mapping dictionary value to list
  29. How can I combine dictionaries with the same keys?
  30. How to sort a list of dictionaries by a value of the dictionary in Python?

Leave a Comment