Why Python TypeError: unhashable type: 'list'

Question

Can someone please tell me why I'm getting a TypeError: unhashable type: 'list' error on the print statement below? For some reason it doesn't like the list of data I'm inputting to the function.

from random import randint
from functools import lru_cache


data = []

[data.append(randint(1,1000000)) for i in range(1,1000000)]

data = sorted(data)

low = 0
high = len(data) + 1


target = randint(1,100000)

print(low, high, target)

@lru_cache(maxsize = 1000)
def binary_search(data, target, low, high):
    if low > high:
        return False
    
    else:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search(data, target, low, mid+1)
        else:
            return binary_search(data, target, mid+1, high)

print(binary_search(data, target, low, high))

Doesn't seem like that error could come from either print statement. Can you please post the entire error and stack trace you are getting? — CryptoFool
– CryptoFool, Commented Dec 2, 2020 at 18:54
Typically that error is raised when you are trying to access a dictionary using a list as a key, you can use a tuple to solve it — Andrea
– Andrea, Commented Dec 2, 2020 at 18:57

Bakuriu · Accepted Answer · 2020-12-02 18:57:21Z

lru_cache requires the arguments to be hashable:

In [1]: from functools import lru_cache                                                                                                                                                                                                                                                  

In [2]: @lru_cache(maxsize=1000) 
   ...: def f(arg): 
   ...:     print(arg) 
   ...:                                                                                                                                                                                                                                                                                  

In [3]: f([1,2,3])                                                                                                                                                                                                                                                                       
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-816cce84b257> in <module>
----> 1 f([1,2,3])

TypeError: unhashable type: 'list'

This is because the implementation uses some hash table to lookup the arguments efficiently. lists are mutable and therefore cannot be hashed.

If you want to use lru_cache the arguments must be, for example, tuples instead of lists.

In your case:

print(binary_search(tuple(data), target, low, high))

should work.

Collectives™ on Stack Overflow

Why Python TypeError: unhashable type: 'list'

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related