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

Question

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

User · Accepted Answer

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

User · Answer

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

User · Answer

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

User · Answer

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  amp  more info  http   wiki python org moin DictionaryKeys

User · Answer

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    gt  gt  gt  class stupidlist list           def   hash   self               return len self        gt  gt  gt  stupid   stupidlist  1  2  3    gt  gt  gt  d    stupid  0   gt  gt  gt  stupid append 4   gt  gt  gt  stupid  1  2  3  4   gt  gt  gt  d   1  2  3  4   0   gt  gt  gt  stupid in d False  gt  gt  gt  stupid in d keys   False  gt  gt  gt  stupid in list d keys    True   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    gt  gt  gt  class stupidlist2 list           def   hash   self               return id self        gt  gt  gt  stupidA   stupidlist2  1  2  3    gt  gt  gt  stupidB   stupidlist2  1  2  3    gt  gt  gt    gt  gt  gt  stupidA    stupidB True  gt  gt  gt  stupidA in  stupidB  0  False   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     gt  gt  gt  class stupidlist3 list           def   hash   self               return 1       gt  gt  gt  stupidC   stupidlist3  1  2  3    gt  gt  gt  stupidD   stupidlist3  1  2  3    gt  gt  gt  stupidE   stupidlist3  1  2  3  4    gt  gt  gt    gt  gt  gt  stupidC in  stupidD  0  True  gt  gt  gt  stupidC in  stupidE  0  False  gt  gt  gt  d    stupidC  0   gt  gt  gt  stupidC append 5   gt  gt  gt  stupidC in d True   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   gt  gt  gt  lists list     i   for i in range 1000    gt  gt  gt  stupidlists set    stupidlist3  i   for i in range 1000    gt  gt  gt  tuples set     i   for i in range 1000    gt  gt  gt  l    999   gt  gt  gt  s   stupidlist3  999    gt  gt  gt  t    999    gt  gt  gt    gt  gt  gt   timeit l in lists list 25 5   s    442 ns per loop  mean    std  dev  of 7 runs  10000 loops each   gt  gt  gt   timeit s in stupidlists set 38 5   s    61 2 ns per loop  mean    std  dev  of 7 runs  10000 loops each   gt  gt  gt   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

User · Answer

Just found you can change List into tuple  then use it as keys   d    tuple  1 2 3     value

User · Answer

The issue is that tuples are immutable  and lists are not  Consider the following  d      li    1 2 3  d li    5 li append 4    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

User · Answer

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

User · Answer

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

User · Answer

Why can t I use a list as a dict key in python    gt  gt  gt  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

User · Answer

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  lt your key here gt     If it works fine it can be used as key for your dictionary or else convert it to something hashable     Inshort     Convert that list to tuple  lt your list gt    Convert that list to str  lt your list gt

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

Examples related to python

Examples related to list

Examples related to dictionary

Examples related to tuples

Examples related to hashable