Hacker News new | past | comments | ask | show | jobs | submit login

> and I can't explain exactly how their ordered dicts work

Traditionally you simply use a doubly linked list approach on the entries (each entry maintains two additional references to the previous and next entry) for that like LinkedHashMap: https://docs.oracle.com/javase//8/docs/api/java/util/LinkedH...

https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/...

Which is also what Python seems to be doing: https://stackoverflow.com/a/34496644

It's fairly intuitive.

Do their new default (now also ordered?) dics do this differently?




Note that OrderedDict is an implementation in Python. CPython's dict has a different implementation. There's more about it at https://docs.python.org/3.6/whatsnew/3.6.html#new-dict-imple... and https://mail.python.org/pipermail/python-dev/2012-December/1... .


This implementation was used from 3.6, right?

It's interesting that the idea mail mentions that nothing changes about the implementation (including order) but the memory layout. Which would imply insertion order was already preserved in older versions (not the case IIRC) or the idea underwent a few more changes that did in fact impact order.

EDIT: I couldn't quite find an answer but https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/ mentions the behavior happens since then because the implementation only tracks indices in the hash table itself and relies on maintaining entries separately in a second array that gets expanded in insertion order.

This would also seem straightforward but it raises a few questions such as how deletion is implemented (efficiently).

EDIT2: Okay, the talk (https://youtu.be/p33CVV29OG8) mentions they just leave holes until the next resize (at around 42:00).

Raymond also mentions there that his original idea didn't preserve ordering but happened due to an additional compacting optimization? Should probably watch the whole thing some time to get the history. Sounds like a fun talk.


Oh! Yeah, that was the talk, but repeated at PyCon. It’s a very clever design that wasn’t at all obvious to me.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: