18

What is the best way to generate a unique key for the contents of a dictionary. My intention is to store each dictionary in a document store along with a unique id or hash so that I don't have to load the whole dictionary from the store to check if it exists already or not. Dictionaries with the same keys and values should generate the same id or hash.

I have the following code:

import hashlib a={'name':'Danish', 'age':107} b={'age':107, 'name':'Danish'} print str(a) print hashlib.sha1(str(a)).hexdigest() print hashlib.sha1(str(b)).hexdigest()

The last two print statements generate the same string. Is this is a good implementation? or are there any pitfalls with this approach? Is there a better way to do this?

Update

Combining suggestions from the answers below, the following might be a good implementation

import hashlib a={'name':'Danish', 'age':107} b={'age':107, 'name':'Danish'} def get_id_for_dict(dict): unique_str = ''.join(["'%s':'%s';"%(key, val) for (key, val) in sorted(dict.items())]) return hashlib.sha1(unique_str).hexdigest() print get_id_for_dict(a) print get_id_for_dict(b)
Improve this question
6
  • Your implementation in update is very wrong: try this: get_id_for_dict({'foo':'bar'}) or get_id_for_dict({'fo':'obar'}) or get_id_for_dict({'f':'o','o':'bar'}). They all return 8843d7f92416211de9ebb963ff4ce28125932878. Better use unique_str = join(['%s%s'%(hashlib.sha1(key), hashlib.sha1(val)) for (key, val) in sorted(dict.items())]) Commented Apr 19, 2013 at 7:45
  • @Tometzky Thanks for pointing out my mistake. I tried your suggestion, but it fails if keys or values are not of type string. Instead, I just changed the string format to enclose key & value in quotes and put a colon character between them Commented Apr 19, 2013 at 13:05
  • Still not good if there can be a ', : and ; in key or value. Use unique_str = join(['%s%s'%(hashlib.sha1(str(key)), hashlib.sha1(str(val))) for (key, val) in sorted(dict.items())]) Commented Apr 19, 2013 at 13:56
  • Can you provide an example where the current implementation would not work? Commented Apr 19, 2013 at 14:10
  • {'b':"ar';'f':'oo"} and {'b':'ar','f':'oo'} would both get the same unique_str: 'b':'ar';'f':'oo'; and the same hash Commented Apr 19, 2013 at 14:36

3 Answers 3

Reset to default
40

I prefer serializing the dict as JSON and hashing that:

import hashlib import json a={'name':'Danish', 'age':107} b={'age':107, 'name':'Danish'} # Python 2 print hashlib.sha1(json.dumps(a, sort_keys=True)).hexdigest() print hashlib.sha1(json.dumps(b, sort_keys=True)).hexdigest() # Python 3 print(hashlib.sha1(json.dumps(a, sort_keys=True).encode()).hexdigest()) print(hashlib.sha1(json.dumps(b, sort_keys=True).encode()).hexdigest())

Returns:

71083588011445f0e65e11c80524640668d3797d 71083588011445f0e65e11c80524640668d3797d
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks! This is an elegant solution indeed, which takes care of differentiating between {'b':"ar';'f':'oo"} and {'b':'ar','f':'oo'} as well.
7

No - you can't rely on particular order of elements when converting dictionary to a string.

You can, however, convert it to sorted list of (key,value) tuples, convert it to a string and compute a hash like this:

a_sorted_list = [(key, a[key]) for key in sorted(a.keys())] print hashlib.sha1( str(a_sorted_list) ).hexdigest()

It's not fool-proof, as a formating of a list converted to a string or formatting of a tuple can change in some future major python version, sort order depends on locale etc. but I think it can be good enough.

Improve this answer

1 Comment

Better would be to use sorted(a.items()), then you can collapse this to a one-liner without loss of readability.
3

A possible option would be using a serialized representation of the list that preserves order. I am not sure whether the default list to string mechanism imposes any kind of order, but it wouldn't surprise me if it were interpreter-dependent. So, I'd basically build something akin to urlencode that sorts the keys beforehand.

Not that I believe that you method would fail, but I'd rather play with predictable things and avoid undocumented and/or unpredictable behavior. It's true that despite "unordered", dictionaries end up having an order that may even be consistent, but the point is that you shouldn't take that for granted.

Improve this answer

6 Comments

I appologize, I wasn't clear. My intention is that Dictionaries with the same keys and values should generate the same id or hash
-1. From my reading of the question the unique identifier should be based on the contents of the dictionary.
@StevenRumbalski Pedro answered before I added my clarification in the question.
@Pedro Ferreira: From the urlencode doc "The order of parameters in the encoded string will match the order of parameter tuples in the sequence." Unfortunately, this order can vary for identical dictionaries.
@StevenRumbalski, I said "something akin to urlencode that sorts the keys beforehand". Not urlencode.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.