Jak wygenerować unikatowy równy skrót dla równych słowników?

Question

np

>>> a = {'req_params': {'app': '12345', 'format': 'json'}, 'url_params': {'namespace': 'foo', 'id': 'baar'}, 'url_id': 'rest'} 
>>> b = {'req_params': { 'format': 'json','app': '12345' }, 'url_params': { 'id': 'baar' ,'namespace':'foo' }, 'url_id': 'REST'.lower() } 
>>> a == b 
True 

Co jest dobrym funkcja hash mieszań wygenerować równe dla obu dicts? Słowniki będą mieć podstawowe typy danych, takie jak int, list, dict i stringi, żadnych innych obiektów.

Byłoby świetnie, gdyby hash był zoptymalizowany pod względem przestrzeni, docelowy zestaw wynosi około 5 milionów obiektów, a więc prawdopodobieństwo kolizji jest znacznie mniejsze.

Nie jestem pewien, czy json.dumps lub inne serializacje wynagradzają równość zamiast struktury członków w słowniku. np. Podstawowe mieszania za pomocą STR dict nie działa:

>>> a = {'name':'Jon','class':'nine'} 
>>> b = {'class':'NINE'.lower(),'name':'Jon'} 
>>> str(a) 
"{'name': 'Jon', 'class': 'nine'}" 
>>> str(b) 
"{'class': 'nine', 'name': 'Jon'}" 

json.dumps nie działa albo:

>>> import json,hashlib 
>>> a = {'name':'Jon','class':'nine'} 
>>> b = {'class':'NINE'.lower(),'name':'Jon'} 
>>> a == b 
True 
>>> ha = hashlib.sha256(json.dumps(a)).hexdigest() 
>>> hb = hashlib.sha256(json.dumps(b)).hexdigest() 
>>> ha 
'545af862cc4d2dd1926fe0aa1e34ad5c3e8a319461941b33a47a4de9dbd7b5e3' 
>>> hb 
'4c7d8dbbe1f180c7367426d631410a175d47fff329d2494d80a650dde7bed5cb' 

Answer 1

The pprint moduł sortuje klucze dyktafonu

from pprint import pformat 
hash(pformat(a)) == hash(pformat(b)) 

Jeśli chcesz zachować skróty, powinieneś użyć skrótu z hashlib. sha1 jest dużo

Answer 2

Nie jestem pewien, czy to jest to, co chcesz:

import json 
import hashlib 

a = # as above 
b = # as above 
c = {'req_params': {'app': '12345', 'format': 'json'}, 
    'url_params': {'id':'baar', 'namespace': 'foo' }, 'url_id': 'rest'} 
d = {'url_params': {'id':'baar', 'namespace': 'foo' }, 
    'req_params': {'app': '12345', 'format': 'json'}, 'url_id': 'rest'} 

ha = hashlib.sha256(json.dumps(a)).hexdigest() 
hb = hashlib.sha256(json.dumps(b)).hexdigest() 
hc = hashlib.sha256(json.dumps(c)).hexdigest() 
hd = hashlib.sha256(json.dumps(d)).hexdigest() 

assert ha == hb 
assert ha == hc 
assert ha == hd 

Answer 3

Dlaczego nie sortujesz przed haszowaniem? Oczywiście, może to wymagać niezauważalnego czasu, ale przynajmniej możesz nadal używać "dobrej" funkcji skrótu, tj. Takiej, która wykazuje dobre rozproszenie plus wszystkie inne pożądane właściwości. Co więcej, jeśli pomysł ma na celu zaoszczędzenie miejsca, prawdopodobnie dlatego, że oczekujesz wielu wpisów w słowniku, dlatego czas zaoszczędzony przez nie sortowanie zestawu przy użyciu "dobrej" funkcji skrótu będzie na pewno zdominowany przez czas wyszukiwania przy korzystaniu z "Zła" funkcja skrótu w wyniku dużej liczby kolizji.

Answer 4

Można również zrobić skrót posortowanej ciąg:

>>> a = {'name':'Jon','class':'nine'} 
>>> b = {'class':'NINE'.lower(),'name':'Jon'} 
>>> def isdeq(d1,d2): 
... def dhash(d): 
...  return hash(str({k:d[k] for k in sorted(d)})) 
... return dhash(d1)==dhash(d2) 
... 
>>> isdeq(a,b) 
True 
>>> isdeq({'name':'Jon','class':'nine'},{'name':'jon','class':'nine'}) 
False 
>>> isdeq({'name':'Jon','class':'nine'},{'class':'nine','name':'Jon'}) 
True