Looking a little deeper at how Python actually uses hash tables: Firstly, the has function isn’t as simple as I suggested above. In Python 3.6, a change was made to achieve the latter. There are two ways to limit this overhead: Pick a clever hash function that maps the keys as densely as possible into as small a space as possible, and limit the size of each element in the array. This empty space isn’t zero cost: this is an array, meaning that it’s all one block of memory and the empty spaces are blank memory just taking up space. One of the downsides of a hash function can be seen in the diagram above: generally there’s a bunch of empty space in it. Nor can we get the keys in insertion order, because nothing about the structure shows us the order they were inserted the image above would look the same whatever order you inserted the three values. We can now easily look up any of the values from its key: hash the key, look up the corresponding position in the array, check that the key matches what we expect and then return the value.īut note that there’s no way to produce the keys in alphabetical order, without looking up all the keys and then sorting them (which is a costly operation). We can store these entries in an 8-element array like this: The great thing about it is that it’s equally fast no matter how many other elements are stored in the hash table (I’m skipping over a few details here, to keep things simple). The hash function is quick, and fetching an item from a specified position in an array is trivial. To insert a value, apply the function to the key and then store the value in an array at that numbered position. Start with a so-called “hash function” that maps strings (or whatever key value you’re using-I’ll keep it simple here) into integers. A hash table is a data structure that gives very fast lookup regardless of the number of items in the container. To recap some of the basics: Dictionaries don’t preserve ordering because they’re implemented using hash tables. I was assuming that making things more user-friendly like this would only come at the cost of making things slower, and there’s no way that Python would make things slower across the board. I don’t know about anyone else, but I was really surprised to see this change. I’m on Ubuntu, so I’m getting Python 3.6 as my default Python 3. This behavior was implementation detail of CPython from 3.6. This actually isn’t anything mysterious: it’s right there in the documentation:Ĭhanged in version 3.7: Dictionary order is guaranteed to be insertion order.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |