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

> 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 of =
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 3,=
 opt-in in Python 2.7). They change from one process to the next. So this c=
an't be used for persistence, it would be limited to transient data in a si=
ngle 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 downsid=
es.)

Second, there's the issue of hash collisions. It's possible for two complet=
ely unequal strings to still have equal hash() values. In that case, becaus=
e you've thrown away the original string key, you can't say for sure that y=
ou'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 a=
lgorithm that `str.__hash__()` uses is explicitly designed to spread hash v=
alues out. But it's not impossible: there are many more possible strings th=
an there are distinct 64-bit numbers. Limiting ourselves to the 26 lower-ca=
se 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 bi=
gger than 2**66, meaning that there are something around 2**64 strings in t=
hat group that, by definition, would have to have duplicate hashes. If we a=
llow upper and lower case letters, we're guaranteed of 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/6F0BAE57-F01E-4D87-938E-DB01602086BC%40nextthought.com.