Re:Python Hash Tables: understanding dictionaries
by formerly_proven on Sunday August 23, 2020 @03:04PM
(#24254389)
> They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. But once you went down this path, users start relying on this quirks and you cannot get away from that.
They most definitely aren't sorted. It's not a quirk either. Python dicts are essentially a tiny hashtable of pointers into an array of objects. For iteration, that array is traversed directly. That's where the insertion-order preservation comes from. It's cheap. It doesn't involve sorting.
> They are insecure by default. Only with some special cmdline flag they feature a randomized seed.
Hashes are randomized since Python 3.2 or so.
> Which is still insecure because the seed can be easily exposed by reading the memory of the seed.
Obviously.
> They feature special values for ints. 1 hashes to 1, 4 to 4 and do on.
That's a quirk of the hash function (which is a reduction modulo a prime), not the hashtable.
> Everybody using siphash is immediately exposed as having no idea about hash table security.
They most definitely aren't sorted. It's not a quirk either. Python dicts are essentially a tiny hashtable of pointers into an array of objects. For iteration, that array is traversed directly. That's where the insertion-order preservation comes from. It's cheap. It doesn't involve sorting.
> They are insecure by default. Only with some special cmdline flag they feature a randomized seed.
Hashes are randomized since Python 3.2 or so.
> Which is still insecure because the seed can be easily exposed by reading the memory of the seed.
Obviously.
> They feature special values for ints. 1 hashes to 1, 4 to 4 and do on.
That's a quirk of the hash function (which is a reduction modulo a prime), not the hashtable.
> Everybody using siphash is immediately exposed as having no idea about hash table security.
Well...