0

I have a question about collisions in 'Dict' structure in Python. Search, insertion and deletion in 'Dict' structure (built in Python) is about O(1) time complexity on average. We all know this is becuase collisions, that might happen if the hash function maps some objects (according to their keys) to the same place in the dictionary. My question: I am going to insert to the Dictionay (built in Python) the keys: "a","b","c",...,"z". Is there any possibility to have a collision in the hash mapping with these keys? Will it be for sure O(1) time complxity [worst case] becuase where will not be collisions? Who can ensure to me that collisions with these keys will not happen? How Python's hash function works? Thank you for helping.

Yoni4949
  • 15
  • 3
  • 1
    Possible duplicate of [How are Python's Built In Dictionaries Implemented](http://stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented) – hashcode55 Feb 26 '17 at 11:57
  • 2
    You're inserting a whopping 26 keys into your dict and are worried about time complexity? Why? – Aran-Fey Feb 26 '17 at 11:57
  • @Rawing: I had an exam in university. I need to be sure that the program works on O(1) time complexity WORST CASE. I need to prove my lecturer that in this case I won't have any collision. I dont know how to prove it. Please help me :P – Yoni4949 Feb 26 '17 at 12:22
  • This is a terrible exam question. Whether or not a hash collision occurs depends on the hash function used, __and__ the exact implementation of the dict. While python's built-in `hash` produces a different hash for each character a-z (i.e. there are no collisions), if the dict internally only has 2 buckets and computes `hash(...)%2`, there are __still__ going to be collisions. – Aran-Fey Feb 26 '17 at 12:52

1 Answers1

2

I think this is what you are looking for

http://www.laurentluce.com/posts/python-dictionary-implementation/

farghal
  • 281
  • 1
  • 5