[python] Why can't I use a list as a dict key in python?

I'm a bit confused about what can/can't be used as a key for a python dict.

dicked = {}
dicked[None] = 'foo'     # None ok
dicked[(1,3)] = 'baz'    # tuple ok
import sys
dicked[sys] = 'bar'      # wow, even a module is ok !
dicked[(1,[3])] = 'qux'  # oops, not allowed

So a tuple is an immutable type but if I hide a list inside of it, then it can't be a key.. couldn't I just as easily hide a list inside a module?

I had some vague idea that that the key has to be "hashable" but I'm just going to admit my own ignorance about the technical details; I don't know what's really going on here. What would go wrong if you tried to use lists as keys, with the hash as, say, their memory location?

This question is related to python list dictionary tuples hashable

The answer is

There's a good article on the topic in the Python wiki: Why Lists Can't Be Dictionary Keys. As explained there:

What would go wrong if you tried to use lists as keys, with the hash as, say, their memory location?

It can be done without really breaking any of the requirements, but it leads to unexpected behavior. Lists are generally treated as if their value was derived from their content's values, for instance when checking (in-)equality. Many would - understandably - expect that you can use any list [1, 2] to get the same key, where you'd have to keep around exactly the same list object. But lookup by value breaks as soon as a list used as key is modified, and for lookup by identity requires you to keep around exactly the same list - which isn't requires for any other common list operation (at least none I can think of).

Other objects such as modules and object make a much bigger deal out of their object identity anyway (when was the last time you had two distinct module objects called sys?), and are compared by that anyway. Therefore, it's less surprising - or even expected - that they, when used as dict keys, compare by identity in that case as well.

Why can't I use a list as a dict key in python?

>>> d = {repr([1,2,3]): 'value'}
{'[1, 2, 3]': 'value'}

(for anybody who stumbles on this question looking for a way around it)

as explained by others here, indeed you cannot. You can however use its string representation instead if you really want to use your list.

Just found you can change List into tuple, then use it as keys.

d = {tuple([1,2,3]): 'value'}

The issue is that tuples are immutable, and lists are not. Consider the following

d = {}
li = [1,2,3]
d[li] = 5

What should d[li] return? Is it the same list? How about d[[1,2,3]]? It has the same values, but is a different list?

Ultimately, there is no satisfactory answer. For example, if the only key that works is the original key, then if you have no reference to that key, you can never again access the value. With every other allowed key, you can construct a key without a reference to the original.

If both of my suggestions work, then you have very different keys that return the same value, which is more than a little surprising. If only the original contents work, then your key will quickly go bad, since lists are made to be modified.

Here's an answer http://wiki.python.org/moin/DictionaryKeys

What would go wrong if you tried to use lists as keys, with the hash as, say, their memory location?

Looking up different lists with the same contents would produce different results, even though comparing lists with the same contents would indicate them as equivalent.

What about Using a list literal in a dictionary lookup?

Because lists are mutable, dict keys (and set members) need to be hashable, and hashing mutable objects is a bad idea because hash values should be computed on the basis of instance attributes.

In this answer, I will give some concrete examples, hopefully adding value on top of the existing answers. Every insight applies to the elements of the set datastructure as well.

Example 1: hashing a mutable object where the hash value is based on a mutable characteristic of the object.

>>> class stupidlist(list):
...     def __hash__(self):
...         return len(self)
>>> stupid = stupidlist([1, 2, 3])
>>> d = {stupid: 0}
>>> stupid.append(4)
>>> stupid
[1, 2, 3, 4]
>>> d
{[1, 2, 3, 4]: 0}
>>> stupid in d
>>> stupid in d.keys()
>>> stupid in list(d.keys())

After mutating stupid, it cannot be found in the dict any longer because the hash changed. Only a linear scan over the list of the dict's keys finds stupid.

Example 2: ... but why not just a constant hash value?

>>> class stupidlist2(list):
...     def __hash__(self):
...         return id(self)
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>> stupidA == stupidB
>>> stupidA in {stupidB: 0}

That's not a good idea as well because equal objects should hash identically such that you can find them in a dict or set.

Example 3: ... ok, what about constant hashes across all instances?!

>>> class stupidlist3(list):
...     def __hash__(self):
...         return 1
>>> stupidC = stupidlist3([1, 2, 3])
>>> stupidD = stupidlist3([1, 2, 3])
>>> stupidE = stupidlist3([1, 2, 3, 4])
>>> stupidC in {stupidD: 0}
>>> stupidC in {stupidE: 0}
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d

Things seem to work as expected, but think about what's happening: when all instances of your class produce the same hash value, you will have a hash collision whenever there are more than two instances as keys in a dict or present in a set.

Finding the right instance with my_dict[key] or key in my_dict (or item in my_set) needs to perform as many equality checks as there are instances of stupidlist3 in the dict's keys (in the worst case). At this point, the purpose of the dictionary - O(1) lookup - is completely defeated. This is demonstrated in the following timings (done with IPython).

Some Timings for Example 3

>>> lists_list = [[i]  for i in range(1000)]
>>> stupidlists_set = {stupidlist3([i]) for i in range(1000)}
>>> tuples_set = {(i,) for i in range(1000)}
>>> l = [999]
>>> s = stupidlist3([999])
>>> t = (999,)
>>> %timeit l in lists_list
25.5 µs ± 442 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit s in stupidlists_set
38.5 µs ± 61.2 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit t in tuples_set
77.6 ns ± 1.5 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

As you can see, the membership test in our stupidlists_set is even slower than a linear scan over the whole lists_list, while you have the expected super fast lookup time (factor 500) in a set without loads of hash collisions.

TL; DR: you can use tuple(yourlist) as dict keys, because tuples are immutable and hashable.

Your awnser can be found here:

Why Lists Can't Be Dictionary Keys

Newcomers to Python often wonder why, while the language includes both a tuple and a list type, tuples are usable as a dictionary keys, while lists are not. This was a deliberate design decision, and can best be explained by first understanding how Python dictionaries work.

Source & more info: http://wiki.python.org/moin/DictionaryKeys

The simple answer to your question is that the class list does not implement the method hash which is required for any object which wishes to be used as a key in a dictionary. However the reason why hash is not implemented the same way it is in say the tuple class (based on the content of the container) is because a list is mutable so editing the list would require the hash to be recalculated which may mean the list in now located in the wrong bucket within the underling hash table. Note that since you cannot modify a tuple (immutable) it doesn't run into this problem.

As a side note, the actual implementation of the dictobjects lookup is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. If you have that book available to you it might be a worthwhile read, in addition if you're really, really interested you may like to take a peek at the developer comments on the actual implementation of dictobject here. It goes into great detail as to exactly how it works. There is also a python lecture on the implementation of dictionaries which you may be interested in. They go through the definition of a key and what a hash is in the first few minutes.

According to the Python 2.7.2 documentation:

An object is hashable if it has a hash value which never changes during its lifetime (it needs a hash() method), and can be compared to other objects (it needs an eq() or cmp() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal, and their hash value is their id().

A tuple is immutable in the sense that you cannot add, remove or replace its elements, but the elements themselves may be mutable. List's hash value depends on the hash values of its elements, and so it changes when you change the elements.

Using id's for list hashes would imply that all lists compare differently, which would be surprising and inconvenient.

A Dictionary is a HashMap it stores map of your keys, value converted to a hashed new key and value mapping.

something like (psuedo code):

{key : val}  
hash(key) = val

If you are wondering which are available options that can be used as key for your dictionary. Then

anything which is hashable(can be converted to hash, and hold static value i.e immutable so as to make a hashed key as stated above) is eligible but as list or set objects can be vary on the go so hash(key) should also needs to vary just to be in sync with your list or set.

You can try :

hash(<your key here>)

If it works fine it can be used as key for your dictionary or else convert it to something hashable.

Inshort :

  1. Convert that list to tuple(<your list>).
  2. Convert that list to str(<your list>).

dict keys need to be hashable. Lists are Mutable and they do not provide a valid hash method.

Questions with python tag:

programming a servo thru a barometer Is there a way to view two blocks of code from the same file simultaneously in Sublime Text? python variable NameError Why my regexp for hyphenated words doesn't work? Comparing a variable with a string python not working when redirecting from bash script is it possible to add colors to python output? Get Public URL for File - Google Cloud Storage - App Engine (Python) Real time face detection OpenCV, Python xlrd.biffh.XLRDError: Excel xlsx file; not supported Could not load dynamic library 'cudart64_101.dll' on tensorflow CPU-only installation Upgrade to python 3.8 using conda Unable to allocate array with shape and data type How to fix error "ERROR: Command errored out with exit status 1: python." when trying to install django-heroku using pip How to prevent Google Colab from disconnecting? "UserWarning: Matplotlib is currently using agg, which is a non-GUI backend, so cannot show the figure." when plotting figure with pyplot on Pycharm How to fix 'Object arrays cannot be loaded when allow_pickle=False' for imdb.load_data() function? "E: Unable to locate package python-pip" on Ubuntu 18.04 Tensorflow 2.0 - AttributeError: module 'tensorflow' has no attribute 'Session' Jupyter Notebook not saving: '_xsrf' argument missing from post How to Install pip for python 3.7 on Ubuntu 18? Python: 'ModuleNotFoundError' when trying to import module from imported package OpenCV TypeError: Expected cv::UMat for argument 'src' - What is this? Requests (Caused by SSLError("Can't connect to HTTPS URL because the SSL module is not available.") Error in PyCharm requesting website How to setup virtual environment for Python in VS Code? Pylint "unresolved import" error in Visual Studio Code Pandas Merging 101 Numpy, multiply array with scalar What is the meaning of "Failed building wheel for X" in pip install? Selenium: WebDriverException:Chrome failed to start: crashed as google-chrome is no longer running so ChromeDriver is assuming that Chrome has crashed Could not install packages due to an EnvironmentError: [Errno 13] OpenCV !_src.empty() in function 'cvtColor' error ConvergenceWarning: Liblinear failed to converge, increase the number of iterations How to downgrade python from 3.7 to 3.6 I can't install pyaudio on Windows? How to solve "error: Microsoft Visual C++ 14.0 is required."? Iterating over arrays in Python 3 How do I install opencv using pip? How do I install Python packages in Google's Colab? How do I use TensorFlow GPU? How to upgrade Python version to 3.7? How to resolve TypeError: can only concatenate str (not "int") to str How can I install a previous version of Python 3 in macOS using homebrew? Flask at first run: Do not use the development server in a production environment TypeError: only integer scalar arrays can be converted to a scalar index with 1D numpy indices array What is the difference between Jupyter Notebook and JupyterLab? Pytesseract : "TesseractNotFound Error: tesseract is not installed or it's not in your path", how do I fix this? Could not install packages due to a "Environment error :[error 13]: permission denied : 'usr/local/bin/f2py'" How do I resolve a TesseractNotFoundError? Trying to merge 2 dataframes but get ValueError Authentication plugin 'caching_sha2_password' is not supported Python Pandas User Warning: Sorting because non-concatenation axis is not aligned

Questions with list tag:

Convert List to Pandas Dataframe Column Python find elements in one list that are not in the other Sorting a list with stream.sorted() in Java Python Loop: List Index Out of Range How to combine two lists in R How do I multiply each element in a list by a number? Save a list to a .txt file The most efficient way to remove first N elements in a list? TypeError: list indices must be integers or slices, not str Parse JSON String into List<string> Append a tuple to a list - what's the difference between two ways? TypeError: 'list' object is not callable in python how to use List<WebElement> webdriver How to add an element to a list? Convert list or numpy array of single element to float in python Reading specific columns from a text file in python How to add element in Python to the end of list using list.insert? How to get every first element in 2 dimensional list Attribute Error: 'list' object has no attribute 'split' Pandas DataFrame to List of Dictionaries Remove duplicates from a list of objects based on property in Java 8 How can I generate a list of consecutive numbers? Beginner Python: AttributeError: 'list' object has no attribute python filter list of dictionaries based on key value Display List in a View MVC TypeError: 'list' object cannot be interpreted as an integer How to save a list to a file and read it as a list type? How to convert list of numpy arrays into single numpy array? Pandas column of lists, create a row for each list element Find empty or NaN entry in Pandas Dataframe How can I return the difference between two lists? TypeError: unsupported operand type(s) for -: 'list' and 'list' Python pandas insert list into a cell How to multiply all integers inside list Appending to list in Python dictionary How to find length of dictionary values ValueError: max() arg is an empty sequence Return list from async/await method Dump a list in a pickle file and retrieve it back later How to 'update' or 'overwrite' a python list Apply function to each element of a list Extract first item of each sublist Checking for empty or null List<string> Dynamically adding elements to ArrayList in Groovy Finding median of list in Python Java 8 stream reverse order replace special characters in a string python How to remove the last element added into the List? Java 8: merge lists with stream API python - if not in list

Questions with dictionary tag:

JS map return object python JSON object must be str, bytes or bytearray, not 'dict Python update a key in dict if it doesn't exist How to update the value of a key in a dictionary in Python? How to map an array of objects in React C# Dictionary get item by index Are dictionaries ordered in Python 3.6+? Split / Explode a column of dictionaries into separate columns with pandas Writing a dictionary to a text file? enumerate() for dictionary in python Map<String, String>, how to print both the "key string" and "value string" together How to convert Map keys to array? How to iterate (keys, values) in JavaScript? Iterate over values of object 'dict' object has no attribute 'has_key' How to get the difference between two dictionaries in Python? Python: create dictionary using dict() with integer keys? Reading json files in C++ Adding item to Dictionary within loop How to convert a JSON string to a dictionary? Iterate through dictionary values? Error: " 'dict' object has no attribute 'iteritems' " How do you find the first key in a dictionary? Populating a dictionary using for loops (python) Pandas DataFrame to List of Dictionaries Beginner Python: AttributeError: 'list' object has no attribute Slicing a dictionary python filter list of dictionaries based on key value How to convert a pymongo.cursor.Cursor into a dict? C# - Print dictionary Determining if Swift dictionary contains key and obtaining any of its values Java 8 stream map on entry set TypeError: 'type' object is not subscriptable when indexing in to a dictionary print highest value in dict with key Converting dictionary to JSON Convert a Pandas DataFrame to a dictionary How do I print the key-value pairs of a dictionary in python Argument Exception "Item with Same Key has already been added" Array from dictionary keys in swift Appending to list in Python dictionary C++ Loop through Map The given key was not present in the dictionary. Which key? How to find length of dictionary values Python safe method to get value of nested dictionary How can I get key's value from dictionary in Swift? Sort Dictionary by keys How to iterate through a list of dictionaries in Jinja template? How to check if a variable is a dictionary in Python? Comparing two maps How do I get the key at a specific index from a Dictionary in Swift?

Questions with tuples tag:

Append a tuple to a list - what's the difference between two ways? How can I access each element of a pair in a pair list? pop/remove items out of a python tuple Python convert tuple to string django: TypeError: 'tuple' object is not callable Why is there no tuple comprehension in Python? Python add item to the tuple Converting string to tuple without splitting characters Convert tuple to list and back How to form tuple column from two columns in Pandas Pair/tuple data type in Go What and When to use Tuple? Find the maximum value in a list of tuples in Python How to unzip a list of tuples into individual lists? Convert list to tuple in Python How to change values in a tuple? Sort a list of tuples by 2nd item (integer value) What's the difference between lists enclosed by square brackets and parentheses in Python? Sort tuples based on second parameter How to easily initialize a list of Tuples? Select value from list of tuples where condition How to convert comma-delimited string to list in Python? Better naming in Tuple classes than "Item1", "Item2" Unpacking a list / tuple of pairs into two lists / tuples python: create list of tuples from lists Why can't I use a list as a dict key in python? Explicitly select items from a list or tuple List of tuples to dictionary Reference an Element in a List of Tuples How does tuple comparison work in Python? how to add value to a tuple? Python: Tuples/dictionaries as keys, select, sort Accessing a value in a tuple that is in a list JavaScript variable assignments from tuples python tuple to dict How to extract the n-th elements from a list of tuples? Getting one value from a tuple How to sort a list/tuple of lists/tuples by the element at a given index? What are "named tuples" in Python? How to search a list of tuples in Python Using Pairs or 2-tuples in Java How to merge lists into a list of tuples? Inserting an item in a Tuple What is the pythonic way to unpack tuples? Find an element in a list of tuples Expanding tuples into arguments List vs tuple, when to use each? Python : List of dict, if exists increment a dict value, if not append a new dict Add Variables to Tuple Tuples( or arrays ) as Dictionary keys in C#

Questions with hashable tag:

Why can't I use a list as a dict key in python?