"""
In order to preserve O(1) performance for node removal (finding nodes), we
must do better than just looping through the linked-list. Here are options
we've considered:
1. use a second dict to map keys to nodes (a la the pure Python version).
2. keep a simple hash table mirroring the order of dict's, mapping each key
to the corresponding node in the linked-list.
3. use a version of shared keys (split dict) that allows non-unicode keys.
4. have the value stored for each key be a (value, node) pair, and adjust
__getitem__(), get(), etc. accordingly.
The approach with the least performance impact (time and space) is #2,
mirroring the key order of dict's dk_entries with an array of node pointers.
While lookdict() and friends (dk_lookup) don't give us the index into the
array, we make use of pointer arithmetic to get that index. **An alternative
would be to refactor lookdict() to provide the index, explicitly exposing
the implementation detail.** We could even just use a custom lookup function
for OrderedDict that facilitates our need. However, both approaches are
significantly more complicated than just using pointer arithmetic.
The catch with mirroring the hash table ordering is that we have to keep
the ordering in sync through any dict resizes. However, that order only
matters during node lookup. We can simply defer any potential resizing
until we need to do a lookup.
"""