Ponieważ listy są zmienne, dictklucze (i setskładowe) muszą być hashowalne, a haszowanie zmiennych obiektów jest złym pomysłem, ponieważ wartości skrótu powinny być obliczane na podstawie atrybutów instancji.
W tej odpowiedzi podam kilka konkretnych przykładów, miejmy nadzieję, że dodam wartość do istniejących odpowiedzi. Każdy wgląd dotyczy elementówset infrastruktury danych.
Przykład 1 : haszowanie zmiennego obiektu, gdzie wartość skrótu jest oparta na zmiennej charakterystyce obiektu.
>>> 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
False
>>> stupid in d.keys()
False
>>> stupid in list(d.keys())
True
Po mutacji stupidnie można go już znaleźć w dyktandzie, ponieważ zmienił się skrót. Tylko liniowe skanowanie listy kluczy dyktatu znajdujestupid .
Przykład 2 : ... ale dlaczego nie stałaby się wartością skrótu?
>>> class stupidlist2(list):
... def __hash__(self):
... return id(self)
...
>>> stupidA = stupidlist2([1, 2, 3])
>>> stupidB = stupidlist2([1, 2, 3])
>>>
>>> stupidA == stupidB
True
>>> stupidA in {stupidB: 0}
False
To również nie jest dobry pomysł, ponieważ równe obiekty powinny mieć identyczne hashowanie, aby można je było znaleźć w dictlubset .
Przykład 3 : ... ok, a co ze stałymi hashami we wszystkich instancjach ?!
>>> 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}
True
>>> stupidC in {stupidE: 0}
False
>>> d = {stupidC: 0}
>>> stupidC.append(5)
>>> stupidC in d
True
Wydaje się, że wszystko działa zgodnie z oczekiwaniami, ale zastanów się, co się dzieje: kiedy wszystkie instancje twojej klasy generują tę samą wartość skrótu, wystąpi kolizja hashowania, ilekroć będzie więcej niż dwa wystąpienia kluczy w a dictlub w a set.
Znalezienie właściwej instancji z my_dict[key]lub key in my_dict(lub item in my_set) wymaga wykonania tylu sprawdzeń równości, ile jest instancji stupidlist3w kluczach dykta (w najgorszym przypadku). W tym momencie cel słownika - wyszukiwanie O (1) - jest całkowicie pokonany. Jest to pokazane w następujących czasach (zrobionych za pomocą IPythona).
Niektóre czasy na przykład 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)
Jak widać, test członkostwa w naszym stupidlists_setjest nawet wolniejszy niż liniowe skanowanie całości lists_list, podczas gdy masz oczekiwany super szybki czas wyszukiwania (współczynnik 500) w zestawie bez mnóstwa kolizji hash.
TL; DR: możesz używać tuple(yourlist)jako dictkluczy, ponieważ krotki są niezmienne i haszowalne.