1

I learned that dictionary uses hashing for it's keys. Suppose I have a dictionary defined as 

dict = { 1.1 : 'hello', 2 : 'bye' }

I can get hello like this

dict.get(1.1)

What I want to do is get the 'hello' through the hash value of the key, something like

dict.get(hash(1.1))

Something like this? How can I do this? I want to check if the hash value is computed or not by python? If it is actually generated than I can directly go to that address and get the value of 'hello', right?

Hemant Yadav
  • 165
  • 1
  • 8
  • 4
    Your premise is flawed because you are not guaranteed to find a single value given the hash of a key. There may be collisions so there might be multiple values for a single key, at which point you have to do a secondary lookup within that bucket. Therefore you must search by the key as that is the only way to find the unique corresponding value. [See here](https://stackoverflow.com/questions/9010222/how-can-python-dict-have-multiple-keys-with-same-hash) – Cory Kramer Oct 09 '17 at 12:00
  • One hash value can be related to more than one object. You're assuming hashing always maps one-to-one. – Moses Koledoye Oct 09 '17 at 12:01
  • @CoryKramer That's okay, can I get all the objects mapped to that hash value in the dictionary that I created? I don't want a unique value, I just want to see all the objects mapped to that hash? – Hemant Yadav Oct 09 '17 at 12:08
  • @JamesJordanTaylor We’re talking about Python here. – bfontaine Oct 09 '17 at 12:26

1 Answers1

0

When a dictionary stores a value it is not guaranteed to store it one-to-one. This is why accessing and storing into a dictionary is O(n) worst case time complexity - meaning it is possible that when storing or retrieving from a dictionary, we might have the values point to the same hash n times (the length of the input).

So each retrieval/storage could require us to pass through every single other value before we get what we needed (same as when we get an item from the last position in an array and we started searching at the first position).

Therefor, you wouldn't be able to retrieve 'hello' exactly, with any certainty. Also something like:

dict.get(hash(1.1))

Would be getting the index of hash 1.1, which is entirely different to index of 1.1.

Rrr
  • 102
  • 1
  • 2
  • 13
  • Well in that case, can I get all the objects in my dictionary, if I call a search for object associated with that hash? In my case can I get 'hello' and 'bye' both (worst case) if I search for the value associated with that hash? – Hemant Yadav Oct 09 '17 at 12:26
  • I know that python looks for hash value and if it gets collision than it performs another level of hashing check, all I want is return me the values of first hash check only, even if all the elements in my dictionary are mapped to that hash value? – Hemant Yadav Oct 09 '17 at 12:27
  • You could very much do that if you created your own data structure of a hash map. Which if this is for an assignment they probably intend for you to do. But using the dictionary that's inbuilt - I'm not entirely sure if it's possible. – Rrr Oct 09 '17 at 12:28