0

I am learning Hashing in python(3.9) where we calculate a hash value via a hash function and map accordingly using two lists.

I just wanted to know if the python dictionary is an implementation of the hash map or not? And if it is, why don't we just use the dictionary to implement maps instead of creating long codes?

Please explain this to me. I have read on google and all but couldn't get my doubt cleared.

EDIT: If I use dictionary to implement my hash map, is it possible to implement linear probing on it to prevent clustering?

Walter White
  • 1
  • 3
  • A python dictionary is roughly equivalent to what other languages call a hash map. – President James K. Polk Oct 21 '21 at 02:11
  • 1
    "And if it is, why don't we just use the dictionary to implement maps instead of creating long codes?" - because the point of your assignment is to learn how hash tables work, not just to learn how to use them. – user2357112 Oct 21 '21 at 02:13
  • @PresidentJamesK.Polk so should we just use dictionary or create hash map code? – Walter White Oct 21 '21 at 02:14
  • You might as well ask why your carpentry class has you building a chair when there are perfectly good chairs at the furniture store already. – user2357112 Oct 21 '21 at 02:14
  • 1
    I don't understand what you are asking. Where are you using a "hash map code" in place of a dictionary? – President James K. Polk Oct 21 '21 at 02:15
  • @user2357112supportsMonica I get what you're saying... I understand how the hash map works and how its code works but just wanted to know that in real world implementation, is it ok to use dictionary or should I continue with the vanilla method – Walter White Oct 21 '21 at 02:16
  • You should use a dict... until you hit a situation where you want a different type of hashing or a different mechanism to relate a hash to an object. That isn't common. – tdelaney Oct 21 '21 at 02:16
  • @tdelaney ok and how should I tackle the problem of clustering? I can use chaining but is linear probing available in dictionary? – Walter White Oct 21 '21 at 02:21
  • I'm not sure how `dict` does it. You can find the source at https://github.com/python/cpython/blob/main/Objects/dictobject.c. I think when you hit a cluster, python has to do a linear equality check... don't quote me on that, though! – tdelaney Oct 21 '21 at 02:30
  • 1
    @WalterWhite the python `dict` already implements a collision resolution technique. Why do you think you would need to try to implement a better one? Are you encountering performance issues using the built-in `dict`? – juanpa.arrivillaga Oct 21 '21 at 04:19
  • @tdelaney it's actually explained in some comments, and there's a good summary in the linked duplicate (the highest voted answer), but Python uses an open-addressing strategy with random probing. – juanpa.arrivillaga Oct 21 '21 at 04:26
  • @WalterWhite so, in your courses, you are going to implement a lot of data structures. But for a lot of programming out there, you won't actually implement the basic data types and will rely on a languages standard library. Of course, this doesn't apply to *everyone*, but it is a good generalization. – juanpa.arrivillaga Oct 21 '21 at 04:28
  • @juanpa.arrivillaga No I am not facing issues I'm just curious. Also, is it ok for programmers to use the language's standard library and data type or should one try to implement the basic data types more? – Walter White Oct 22 '21 at 00:59

0 Answers0