8

例えば：

>>> 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

両方の dict に対して等しいハッシュを生成するための適切なハッシュ関数は何ですか? 辞書には、int、list、dict、string などの基本的なデータ型があり、その他のオブジェクトはありません。

ハッシュがスペース最適化されていて、ターゲット セットが約 500 万個のオブジェクトである場合、衝突の可能性はかなり低くなります。

json.dumps またはその他のシリアライゼーションが、辞書内のメンバーの構造ではなく平等を尊重するかどうかはわかりません。例えば。dict の str を使用した基本的なハッシュは機能しません:

>>> 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 も機能しません:

>>> 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'
4

4 に答える 4

11

pprint モジュールは dict キーをソートします

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

ハッシュを保持したい場合は、hashlib のハッシュを使用する必要があります。sha1で十分です

于 2013-05-24T13:21:24.953 に答える
1

ハッシュする前にソートしないのはなぜですか？確かに、それを行うには無視できない時間がかかるかもしれませんが、少なくとも「良い」ハッシュ関数、つまり、良好な分散と他のすべての望ましい特性を示すハッシュ関数を使い続けることができます。さらに、スペースを節約することが目的である場合、それはおそらくディクショナリに多くのエントリが予想されるためです。したがって、「適切な」ハッシュ関数を使用するときにセットをソートしないことで節約される時間は、多数の衝突の結果としての「悪い」ハッシュ関数。

于 2013-05-24T13:35:26.957 に答える
0

ソートされた文字列のハッシュを行うこともできます:

>>> 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
于 2013-05-24T14:39:56.740 に答える
0

これがあなたが望むものかどうかわからない：

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
于 2013-05-24T13:13:59.847 に答える