Re: Store hashes of objects in BTrees instead of objects?
Éloi Rivard <[email protected]> Thu, 8 Jul 2021 05:43:35 -0700 (PDT)
| Newsgroups | gmane.comp.web.zope.zodb |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_518_1924918719.1625748215827
Content-Type: multipart/alternative;
boundary="----=_Part_519_721922740.1625748215827"
------=_Part_519_721922740.1625748215827
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I was ignoring that the hash salt for those native python types was=20
different on different processes, and generated different hashes. Some=20
types seems to be safe in that regard though:
$ python3.9 -c "import uuid;=20
print(hash(uuid.UUID('0ef31c24-06c8-460c-93c4-30f39c7c8ef1')))"
818830583600693081
$ python3.9 -c "import uuid;=20
print(hash(uuid.UUID('0ef31c24-06c8-460c-93c4-30f39c7c8ef1')))"
81883058360069308
It looks that this can be mitigated by using hashing functions from=20
hashlib, then extract a 64bit integer from the hashes.
$ python3.9 -c "import hashlib;=20
print(int(hashlib.sha256(b'hi').hexdigest(), base=3D16) % 2 ** 64)"
14450742454081714852
$ python3.9 -c "import hashlib;=20
print(int(hashlib.sha256(b'hi').hexdigest(), base=3D16) % 2 ** 64)"
14450742454081714852
I get your point on the string lengths. Now the question is to know if that=
=20
collision probability is acceptable in my context...
Thank you for the hints!
Le mercredi 7 juillet 2021 =C3=A0 18:07:48 UTC+2, Jason Madden a =C3=A9crit=
:
>
>
> > On Jul 6, 2021, at 19:43, =C3=89loi Rivard <[email protected]> wrote:
> >=20
> > I was wondering if there are drawbacks to systematically using hashes o=
f=20
> strings as LOBTree keys, instead of those whole strings as OOBTree keys.=
=20
>
> I can think of two potential drawbacks.
>
> First, hashes of strings in CPython are not stable (by default in Python=
=20
> 3, opt-in in Python 2.7). They change from one process to the next. So th=
is=20
> can't be used for persistence, it would be limited to transient data in a=
=20
> single process. It's like trying to use `id(an_object)`.
>
> $ python3.9 -c 'print(hash("hi"))'
> -7167107578322364224
> $ python3.9 -c 'print(hash("hi"))'
> 7111998896984987603
> $ python3.9 -c 'print(hash("hi"))'
> 5216739811521604812
>
> (Yes, you can opt-out of this in Python 3, but doing so has its own=20
> downsides.)
>
> Second, there's the issue of hash collisions. It's possible for two=20
> completely unequal strings to still have equal hash() values. In that cas=
e,=20
> because you've thrown away the original string key, you can't say for sur=
e=20
> that you're really getting back the data you want. In other words,=20
> something like this is theoretically possible:
>
> tree =3D LOBTree()
> tree[hash("hi")] =3D 42
> assert len(tree) =3D=3D 1
> assert tree[hash("bye")] =3D=3D 42
>
> Granted, in modern versions of Python 3 this is often ignored because the=
=20
> algorithm that `str.__hash__()` uses is explicitly designed to spread has=
h=20
> values out. But it's not impossible: there are many more possible strings=
=20
> than there are distinct 64-bit numbers. Limiting ourselves to the 26=20
> lower-case characters of the English alphabet, plus a space, we find that=
=20
> there are more than 2**64 possible strings of length 14 [27**14]; in fact=
,=20
> that's bigger than 2**66, meaning that there are something around 2**64=
=20
> strings in that group that, by definition, would have to have duplicate=
=20
> hashes. If we allow upper and lower case letters, we're guaranteed of=20
> duplicates after 12 characters.
>
> ~Jason
--=20
You received this message because you are subscribed to the Google Groups "=
zodb" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to [email protected].
To view this discussion on the web visit https://groups.google.com/d/msgid/=
zodb/13e69ceb-9b35-4f87-bc16-0995c1bb6086n%40googlegroups.com.
------=_Part_519_721922740.1625748215827
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div>I was ignoring that the hash salt for those native python types was di=
fferent on different processes, and generated different hashes. Some types =
seems to be safe in that regard though:<br></div><div><br></div><div>$ pyth=
on3.9 -c "import uuid; print(hash(uuid.UUID('0ef31c24-06c8-460c-93c4-30f39c=
7c8ef1')))"</div><div>818830583600693081<br></div><div><div>$ python3.9 -c =
"import uuid; print(hash(uuid.UUID('0ef31c24-06c8-460c-93c4-30f39c7c8ef1'))=
)"</div><div>81883058360069308</div><div><br></div><div>It looks that this =
can be mitigated by using hashing functions from hashlib, then extract a 64=
bit integer from the hashes.</div><div><br></div><div>$ python3.9 -c "impor=
t hashlib; print(int(hashlib.sha256(b'hi').hexdigest(), base=3D16) % 2 ** 6=
4)"<br>14450742454081714852</div><div><br></div><div><div>$ python3.9 -c "i=
mport hashlib; print(int(hashlib.sha256(b'hi').hexdigest(), base=3D16) % 2 =
** 64)"<br>14450742454081714852</div><div><br></div></div><div>I get your p=
oint on the string lengths. Now the question is to know if that collision p=
robability is acceptable in my context...</div><div><br></div><div>Thank yo=
u for the hints!<br></div></div><div class=3D"gmail_quote"><div dir=3D"auto=
" class=3D"gmail_attr">Le mercredi 7 juillet 2021 =C3=A0 18:07:48 UTC+2, Ja=
son Madden a =C3=A9crit=C2=A0:<br/></div><blockquote class=3D"gmail_quote" =
style=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); pa=
dding-left: 1ex;">
<br>
<br>> On Jul 6, 2021, at 19:43, =C3=89loi Rivard <<a href data-email-=
masked rel=3D"nofollow">[email protected]</a>> wrote:
<br>>=20
<br>> I was wondering if there are drawbacks to systematically using has=
hes of strings as LOBTree keys, instead of those whole strings as OOBTree k=
eys.=20
<br>
<br>I can think of two potential drawbacks.
<br>
<br>First, hashes of strings in CPython are not stable (by default in Pytho=
n 3, opt-in in Python 2.7). They change from one process to the next. So th=
is can't be used for persistence, it would be limited to transient data=
in a single process. It's like trying to use `id(an_object)`.
<br>
<br>$ python3.9 -c 'print(hash("hi"))'
<br>-7167107578322364224
<br>$ python3.9 -c 'print(hash("hi"))'
<br>7111998896984987603
<br>$ python3.9 -c 'print(hash("hi"))'
<br>5216739811521604812
<br>
<br>(Yes, you can opt-out of this in Python 3, but doing so has its own dow=
nsides.)
<br>
<br>Second, there's the issue of hash collisions. It's possible for=
two completely unequal strings to still have equal hash() values. In that =
case, because you've thrown away the original string key, you can't=
say for sure that you're really getting back the data you want. In oth=
er words, something like this is theoretically possible:
<br>
<br> tree =3D LOBTree()
<br> tree[hash("hi")] =3D 42
<br> assert len(tree) =3D=3D 1
<br> assert tree[hash("bye")] =3D=3D 42
<br>
<br>Granted, in modern versions of Python 3 this is often ignored because t=
he algorithm that `str.__hash__()` uses is explicitly designed to spread ha=
sh values out. But it's not impossible: there are many more possible st=
rings than there are distinct 64-bit numbers. Limiting ourselves to the 26 =
lower-case characters of the English alphabet, plus a space, we find that t=
here are more than 2**64 possible strings of length 14 [27**14]; in fact, t=
hat's bigger than 2**66, meaning that there are something around 2**64 =
strings in that group that, by definition, would have to have duplicate has=
hes. If we allow upper and lower case letters, we're guaranteed of dupl=
icates after 12 characters.
<br>
<br>~Jason</blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;zodb" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]">zodb+unsubscri=
[email protected]</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/zodb/13e69ceb-9b35-4f87-bc16-0995c1bb6086n%40googlegroups.com?ut=
m_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/zod=
b/13e69ceb-9b35-4f87-bc16-0995c1bb6086n%40googlegroups.com</a>.<br />
------=_Part_519_721922740.1625748215827--
------=_Part_518_1924918719.1625748215827--