0

I've been learning Python for a year now and I have taken an interest in data structures and algorithms. I was watching a video on hash maps and the instructor said that to solve hash map collisions, you should use a linked list. I thought about it and I wondered whether you could use a nested hash map. Wouldn't this increase the efficiency?

A general explanation of this would be amazing but one from a Python perspective would be incredible.

Thanks.

chai
  • 418
  • 6
  • 17
  • 1
    There are no hash collisions in Python's dicts that you need to worry about. Dicts mitigate them internally, you will never get the wrong value out. See https://stackoverflow.com/questions/9010222/why-can-a-python-dict-have-multiple-keys-with-the-same-hash – Tomalak Aug 26 '21 at 09:36
  • 1
    If that was not the direction you were going with your question, you need to give more context, i.e. verbal algorithm descriptions, or sample code. In any case it can be useful to look at how dicts solve the hash collision issue. – Tomalak Aug 26 '21 at 09:46
  • How can Python's dict have absolutely no hash collisions? I didn't think that was possible. Plus, what do you mean my 'dicts mitigate them internally'? – chai Aug 26 '21 at 10:24
  • 1
    Oh it has hash collisions. Hash collisions are unavoidable - they are the logical consequence of mapping an infinite input space to a finite result space. But the dict (and any hash table data structure in any other language) is implemented in such a way that collisions are expected and worked around, so that the primary function (key in, associated value out) is not impacted. The other thread has a couple of answers that are worth reading. – Tomalak Aug 26 '21 at 10:32
  • 1
    (I did not say *"There are no hash collisions in Python's dicts"*, I said *"There are no hash collisions in Python's dicts that you need to worry about."*) – Tomalak Aug 26 '21 at 10:41

0 Answers0