Re: Store hashes of objects in BTrees instead of objects?

--000000000000a31ba805c69cc058
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Also, range searches, which are an important feature become useless.

On Wed, Jul 7, 2021 at 12:07 PM Jason Madden <[email protected]>
wrote:

>
>
> > On Jul 6, 2021, at 19:43, =C3=89loi Rivard <[email protected]> wrote:
> >
> > I was wondering if there are drawbacks to systematically using hashes o=
f
> strings as LOBTree keys, instead of those whole strings as OOBTree keys.
>
> I can think of two potential drawbacks.
>
> First, hashes of strings in CPython are not stable (by default in Python
> 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)`.
>
> $ 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
> downsides.)
>
> Second, there's the issue of hash collisions. It's possible for two
> completely unequal strings to still have equal hash() values. In that cas=
e,
> because you've thrown away the original string key, you can't say for sur=
e
> that you're really getting back the data you want. In other words,
> 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
> algorithm that `str.__hash__()` uses is explicitly designed to spread has=
h
> values out. But it's not impossible: there are many more possible strings
> 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
> there are more than 2**64 possible strings of length 14 [27**14]; in fact=
,
> that'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
> hashes. If we allow upper and lower case letters, we're guaranteed of
> duplicates after 12 characters.
>
> ~Jason
>
> --
> 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
> email to [email protected].
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/zodb/6F0BAE57-F01E-4D87-938E-DB01602086=
BC%40nextthought.com
> .
>

--=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/CAPDm-FguMA7JmpS_DbSy9UXc_KCUSx5NydEpFHkW1_ZbO5oFBg%40mail.gmail.com.

--000000000000a31ba805c69cc058
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Also, range searches, which are an important feature =
become useless.<br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" cl=
ass=3D"gmail_attr">On Wed, Jul 7, 2021 at 12:07 PM Jason Madden &lt;<a href=
=3D"mailto:[email protected]">[email protected]</a>&g=
t; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
&gt; On Jul 6, 2021, at 19:43, =C3=89loi Rivard &lt;<a href=3D"mailto:azmeu=
[email protected]" target=3D"_blank">[email protected]</a>&gt; wrote:<br>
&gt; <br>
&gt; I was wondering if there are drawbacks to systematically using hashes =
of strings as LOBTree keys, instead of those whole strings as OOBTree keys.=
 <br>
<br>
I can think of two potential drawbacks.<br>
<br>
First, hashes of strings in CPython are not stable (by default in Python 3,=
 opt-in in Python 2.7). They change from one process to the next. So this c=
an&#39;t be used for persistence, it would be limited to transient data in =
a single process. It&#39;s like trying to use `id(an_object)`.<br>
<br>
$ python3.9 -c &#39;print(hash(&quot;hi&quot;))&#39;<br>
-7167107578322364224<br>
$ python3.9 -c &#39;print(hash(&quot;hi&quot;))&#39;<br>
7111998896984987603<br>
$ python3.9 -c &#39;print(hash(&quot;hi&quot;))&#39;<br>
5216739811521604812<br>
<br>
(Yes, you can opt-out of this in Python 3, but doing so has its own downsid=
es.)<br>
<br>
Second, there&#39;s the issue of hash collisions. It&#39;s possible for two=
 completely unequal strings to still have equal hash() values. In that case=
, because you&#39;ve thrown away the original string key, you can&#39;t say=
 for sure that you&#39;re really getting back the data you want. In other w=
ords, something like this is theoretically possible:<br>
<br>
=C2=A0 =C2=A0tree =3D LOBTree()<br>
=C2=A0 =C2=A0tree[hash(&quot;hi&quot;)] =3D 42<br>
=C2=A0 =C2=A0assert len(tree) =3D=3D 1<br>
=C2=A0 =C2=A0assert tree[hash(&quot;bye&quot;)] =3D=3D 42<br>
<br>
Granted, in modern versions of Python 3 this is often ignored because the a=
lgorithm that `str.__hash__()` uses is explicitly designed to spread hash v=
alues out. But it&#39;s not impossible: there are many more possible string=
s than there are distinct 64-bit numbers. Limiting ourselves to the 26 lowe=
r-case characters of the English alphabet, plus a space, we find that there=
 are more than 2**64 possible strings of length 14 [27**14]; in fact, that&=
#39;s bigger than 2**66, meaning that there are something around 2**64 stri=
ngs in that group that, by definition, would have to have duplicate hashes.=
 If we allow upper and lower case letters, we&#39;re guaranteed of duplicat=
es after 12 characters.<br>
<br>
~Jason<br>
<br>
-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;zodb&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:zodb%[email protected]" target=3D"_b=
lank">[email protected]</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/zodb/6F0BAE57-F01E-4D87-938E-DB01602086BC%40nextthought.com" rel=
=3D"noreferrer" target=3D"_blank">https://groups.google.com/d/msgid/zodb/6F=
0BAE57-F01E-4D87-938E-DB01602086BC%40nextthought.com</a>.<br>
</blockquote></div></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;zodb&quot; 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/CAPDm-FguMA7JmpS_DbSy9UXc_KCUSx5NydEpFHkW1_ZbO5oFBg%40mail.=
gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com=
/d/msgid/zodb/CAPDm-FguMA7JmpS_DbSy9UXc_KCUSx5NydEpFHkW1_ZbO5oFBg%40mail.gm=
ail.com</a>.<br />

--000000000000a31ba805c69cc058--