News for hackers. Stuff that matters.
Re:Python Hash Tables: understanding dictionaries by rurban on Sunday August 23, 2020 @02:27PM (#24254067)
Well, if you know hash tables you will still need some education on the special quirks of python hash tables. They are in no way related to CS hash tables. And you should not base your own hash table on the python architecture.

They are sorted. Normal hash tables are unsorted, sorting needs lot of time and space. Nobody but python would do that. (ignoring PHP here). But once you went down this path, users start relying on this quirks and you cannot get away from that.

They feature special values for ints. 1 hashes to 1, 4 to 4 and so on. This looks like Lua arrays, which are either arrays or hashtables under the hood, and allows efficient switches from dense to sparse arrays. But mostly it costs time in the most critical fast path. And it doesn't help in security at all.

They are insecure by default. Only with some special cmdline flag they feature a randomized seed. Which is still insecure because the seed can be easily exposed by reading the memory of the seed.

They are extremely slow.

They are using siphash. Everybody using siphash is immediately exposed as having no idea about hash table security.

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.

Well...

Re:Python Hash Tables: understanding dictionaries by dragonwriter on Sunday August 23, 2020 @03:11PM (#24254457)
> They are sorted.

No, they are insertion-ordered.

> Nobody but python would do that.

Ruby Hashes are insertion-ordered; JavaScript objects have numeric properties ordered numerically (so, in a sense, are sorted), but other propertied in insertion order.