PyCon 2010: The Mighty Dictionary
Why Stack Overflow recommends it
Stack Overflow users link it whenever an answer needs to explain how Python dicts and sets work internally, especially why key order appears arbitrary or changes.
Recommended by 11 people across 11 different months, 2010 to 2021.
What it is
A 2010 PyCon talk by Brandon Craig Rhodes that walks through how CPython implements the dict as a hash table, covering hashing, buckets, collision resolution, resizing and why iteration order is arbitrary. The upload on this channel is a re-post of the conference recording.
What people said
Strong rec Alex · 2016-07 · Stack Overflow · on “Why can't I change a set I'm iterating over?”
First you need to understand a bit about how dicts work [LINK] . Sets work the same way (in terms of storing keys) under the covers. I don't think I could ever explain this better than Brandon Rhodes at PyCon [this video] (the talk answers this question at some point and is a phenomenal reference for the data structures underlying dicts and sets ). Basically for dicts / sets the order of iteration can change as items are added or removed. The same is not true of lists .
Recommends miku · 2010-09 · Stack Overflow · on “Python Array with String Indices”
What you want is called an associative array [LINK] . In python these are called dictionaries [LINK] . Dictionaries are sometimes found in other languages as “associative memories” or “associative arrays”. Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys, which can be any immutable type ; strings and numbers can always be keys. myDict = {} myDict["john"] = "johns value" myDict["jeff"] = "jeffs value" Alternative way to create the above dict: myDict = {"john": "johns value", "jeff": "jeffs value"} Accessing values: print(myDict["jeff"]) # => "jeffs value" Getting the keys (in Python v2): print(myDict.keys()) # => ["john", "jeff"] In Python 3, you'll
Recommends mgilson · 2012-08 · Stack Overflow · on “How does Python determines the order of elements in sets?”
You should watch this video [this video] (although it is CPython 1 specific and about dictionaries -- but I assume it applies to sets as well). Basically, python hashes the elements and takes the last N bits (where N is determined by the size of the set) and uses those bits as array indices to place the object in memory. The objects are then yielded in the order they exist in memory. Of course, the picture gets a little more complicated when you need to resolve collisions between hashes, but that's the gist of it. Also note that the order that they are printed out is determined by the order that you put them in (due to collisions). So, if you reorder the list you pass to set_2 , you might get a d
Recommends Lukas Graf · 2014-08 · Stack Overflow · on “What determines object order when creating a Python dict?”
See Brandon Rhodes' talk The Mighty Dictionary [this video] for all the gory details on dictionary construction and resizing (if you're interested in the answer to the exact question from your title).
Recommends Lukas Graf · 2014-10 · Stack Overflow · on “How to let imported python modules use a builtin hash() function which behaves the same between 32 and 64 bit?”
Also: Just monkey-patching the `hash()` function is unlikely to completely solve your problem. If the order of some operations changes in your code (but functionally it stays the same), the order in which dictionary insert collisions happen might change, and so will the key order. Even though the code produces an equivalent dictionary. (See The Mighty Dictionary [this video] if you haven't yet).
Recommends jonrsharpe · 2015-06 · Stack Overflow · on “Python dictionary size vs object size efficiency”
Note that sys.getsizeof [LINK] gives you the size of the object itself , but that's not the whole story. An object has various attributes that also contribute to the overall memory footprint. For example, an instance of a class has a __dict__ , which holds the values of its attributes: >>> o = O() >>> o.__dict__ {} >>> sys.getsizeof(o.__dict__) 140 Note three interesting things: This is also a dictionary - this data structure is used a lot under the hood in Python, and is extremely well-optimised as a result; There is nothing in o.__dict__ , because var1 and var2 are class attributes , stored on O , not instance attributes ; and Even though there's nothing in o.__dict__ , it's still the same
Recommends jonrsharpe · 2015-07 · Stack Overflow · on “Python dictionary iterator performance”
What exactly are you asking? If you're interested in how dictionaries are implemented, check out *"the mighty dictionary"* [this video] .
Recommends franciscod · 2015-07 · Stack Overflow · on “How to force Python dictionary to shrink?”
The way to do this "rehashing" so it uses less memory is to create a new dictionary and copy the content over. The Python dictionary implementation is explained really well in this video: [this video] There is an atendee asking this same question ( [this video] ), and the answer given by the speaker is: Resizes are only calculated upon insertion; as a dictionary shrinks it just gains a lot of dummy entries and as you refill it will just start reusing those to store keys. [...] you have to copy the keys and values out to a new dictionary
Recommends franciscod · 2015-07 · Stack Overflow · on “Writing dict of lists to csv, specifing column order”
The Python dict keys are sorted by its hash. If you want further info on this you can check this awesome video from PyCon 2010: [this video] You can sort the keys into a list, and then access the values with that list: sorted_keys = sorted(d.keys()) # use this instead of d.keys() sorted_values = (d[k] for k in sorted_keys) # use this instead of d.values()
Recommends BioGeek · 2015-10 · Stack Overflow · on “In hash collision, how does CPython know which value is stored at index HASHVALUE and which value is stored at RESOLUTIONINDEX”
This is answered in detail at around minute 8:50 in the talk The mighty dictionary [this video] , given by Brandon Craig Rhodes at PyCon 2010.