Mengapa saya tidak bisa menggunakan list sebagai kunci dict di python?

Saya agak bingung tentang apa yang bisa / tidak bisa digunakan sebagai kunci untuk 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

Jadi tuple adalah tipe yang tidak dapat diubah tetapi jika saya menyembunyikan daftar di dalamnya, maka itu tidak bisa menjadi kunci .. tidak bisakah saya dengan mudah menyembunyikan daftar di dalam modul?

Saya memiliki ide yang tidak jelas bahwa kuncinya harus "dapat di-hash" tetapi saya hanya akan mengakui ketidaktahuan saya sendiri tentang detail teknis; Saya tidak tahu apa yang sebenarnya terjadi di sini. Apa yang salah jika Anda mencoba menggunakan daftar sebagai kunci, dengan hash sebagai, katakanlah, lokasi memorinya?

Ada artikel bagus tentang topik di wiki Python: Mengapa Daftar Tidak Bisa Menjadi Kunci Kamus . Seperti yang dijelaskan di sana:

Apa yang salah jika Anda mencoba menggunakan daftar sebagai kunci, dengan hash sebagai, katakanlah, lokasi memorinya?

Itu dapat dilakukan tanpa benar-benar melanggar persyaratan apa pun, tetapi itu mengarah pada perilaku yang tidak terduga. Daftar umumnya diperlakukan seolah-olah nilainya berasal dari nilai isinya, misalnya saat memeriksa persamaan (dalam-). Banyak yang akan - dapat dimengerti - berharap bahwa Anda dapat menggunakan daftar apa pun [1, 2]untuk mendapatkan kunci yang sama, di mana Anda harus menyimpan objek daftar yang persis sama. Tetapi pencarian menurut pemutusan nilai segera setelah daftar yang digunakan sebagai kunci diubah, dan untuk pencarian berdasarkan identitas mengharuskan Anda untuk menyimpan daftar yang persis sama - yang tidak memerlukan operasi daftar umum lainnya (setidaknya tidak ada yang dapat saya pikirkan ).

Objek lain seperti modul dan objectmembuat kesepakatan yang jauh lebih besar dari identitas objek mereka (kapan terakhir kali Anda memiliki dua objek modul yang berbeda dipanggil sys?), Dan tetap dibandingkan dengan itu. Oleh karena itu, kurang mengherankan - atau bahkan diharapkan - bahwa mereka, ketika digunakan sebagai kunci dict, dibandingkan dengan identitas dalam kasus itu juga.

Mengapa saya tidak bisa menggunakan list sebagai kunci dict di python?

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

(untuk siapa saja yang tersandung pada pertanyaan ini mencari jalan keluarnya)

seperti yang dijelaskan oleh orang lain di sini, memang Anda tidak bisa. Namun Anda dapat menggunakan representasi stringnya jika Anda benar-benar ingin menggunakan daftar Anda.

Baru ditemukan Anda dapat mengubah Daftar menjadi tupel, lalu menggunakannya sebagai kunci.

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

Masalahnya adalah bahwa tupel tidak dapat diubah, dan daftar tidak. Simak berikut ini

d = {}
li = [1,2,3]
d[li] = 5
li.append(4)

Apa yang harus d[li]dikembalikan? Apakah ini daftar yang sama? Bagaimana dengan d[[1,2,3]]? Ini memiliki nilai yang sama, tetapi apakah daftarnya berbeda?

Pada akhirnya, tidak ada jawaban yang memuaskan. Misalnya, jika satu-satunya kunci yang berfungsi adalah kunci asli, maka jika Anda tidak memiliki referensi ke kunci tersebut, Anda tidak dapat lagi mengakses nilainya. Dengan setiap kunci lain yang diizinkan, Anda dapat membuat kunci tanpa referensi ke aslinya.

Jika kedua saran saya berfungsi, maka Anda memiliki kunci yang sangat berbeda yang mengembalikan nilai yang sama, yang lebih dari sedikit mengejutkan. Jika hanya konten asli yang berfungsi, maka kunci Anda akan segera rusak, karena daftar dibuat untuk dimodifikasi.

Inilah jawabannya http://wiki.python.org/moin/DictionaryKeys

Apa yang salah jika Anda mencoba menggunakan daftar sebagai kunci, dengan hash sebagai, katakanlah, lokasi memorinya?

Mencari daftar yang berbeda dengan konten yang sama akan menghasilkan hasil yang berbeda, meskipun membandingkan daftar dengan konten yang sama akan menunjukkan bahwa mereka setara.

Bagaimana dengan Menggunakan literal daftar dalam pencarian kamus?

Karena daftar dapat berubah, dictkunci (dan setanggota) harus dapat dicirikan, dan mencirikan objek yang dapat berubah adalah ide yang buruk karena nilai hash harus dihitung berdasarkan atribut instance.

Pada jawaban ini, saya akan memberikan beberapa contoh konkret, semoga menambah nilai di atas jawaban yang ada. Setiap wawasan berlaku untuk elemen struktur data setjuga.

Contoh 1 : hashing objek yang bisa berubah di mana nilai hash didasarkan pada karakteristik objek yang bisa berubah.

>>> 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

Setelah bermutasi stupid, itu tidak dapat ditemukan lagi di dict karena hash berubah. Hanya pemindaian linier atas daftar kunci dict yang ditemukan stupid.

Contoh 2 : ... tetapi mengapa tidak hanya nilai hash konstan?

>>> 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

Itu juga bukan ide yang bagus karena objek yang sama harus memiliki hash yang identik sehingga Anda dapat menemukannya di a dictatau set.

Contoh 3 : ... ok, bagaimana dengan hash konstan di semua instance ?!

>>> 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

Hal-hal tampaknya berfungsi seperti yang diharapkan, tetapi pikirkan tentang apa yang terjadi: ketika semua instance kelas Anda menghasilkan nilai hash yang sama, Anda akan mengalami benturan hash setiap kali ada lebih dari dua instance sebagai kunci dalam a dictatau hadir di a set.

Menemukan instance yang tepat dengan my_dict[key]atau key in my_dict(atau item in my_set) perlu melakukan sebanyak mungkin pemeriksaan kesetaraan karena ada instance stupidlist3di kunci dict (dalam kasus terburuk). Pada titik ini, tujuan pencarian kamus - O (1) - benar-benar dikalahkan. Ini ditunjukkan dalam pengaturan waktu berikut (dilakukan dengan IPython).

Beberapa Waktu untuk Contoh 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)

Seperti yang Anda lihat, uji keanggotaan di kami stupidlists_setbahkan lebih lambat daripada pemindaian linier secara keseluruhan lists_list, sementara Anda memiliki waktu pencarian super cepat yang diharapkan (faktor 500) dalam satu set tanpa banyak benturan hash.

TL; DR: Anda dapat menggunakan tuple(yourlist)sebagai dictkunci, karena tupel tidak dapat diubah dan memiliki hash.

Awnser Anda dapat ditemukan di sini:

Mengapa Daftar Tidak Bisa Menjadi Kunci Kamus

Pendatang baru di Python sering bertanya-tanya mengapa, sementara bahasanya menyertakan tupel dan tipe daftar, tupel dapat digunakan sebagai kunci kamus, sedangkan daftar tidak. Ini adalah keputusan desain yang disengaja, dan paling baik dapat dijelaskan dengan terlebih dahulu memahami cara kerja kamus Python.

Sumber & info lebih lanjut: http://wiki.python.org/moin/DictionaryKeys

Jawaban sederhana untuk pertanyaan Anda adalah bahwa daftar kelas tidak mengimplementasikan hash metode yang diperlukan untuk objek apa pun yang ingin digunakan sebagai kunci dalam kamus. Namun alasan mengapa hash tidak diimplementasikan dengan cara yang sama seperti yang dikatakan kelas tuple (berdasarkan konten wadah) adalah karena daftar bisa berubah sehingga mengedit daftar akan membutuhkan hash untuk dihitung ulang yang mungkin berarti daftar di sekarang terletak di keranjang yang salah dalam tabel hash bawahan. Perhatikan bahwa karena Anda tidak dapat memodifikasi tupel (tidak dapat diubah), ini tidak mengalami masalah ini.

Sebagai catatan tambahan, implementasi aktual dari pencarian dictobjects didasarkan pada Algoritma D dari Knuth Vol. 3, Detik. 6.4. Jika Anda memiliki buku itu yang tersedia untuk Anda, mungkin itu adalah bacaan yang berharga, selain itu jika Anda benar-benar tertarik, Anda mungkin ingin mengintip komentar pengembang tentang implementasi sebenarnya dari diktobyek di sini. Ini menjadi sangat rinci tentang cara kerjanya. Ada juga kuliah python tentang implementasi kamus yang mungkin Anda minati. Mereka membahas definisi kunci dan apa itu hash dalam beberapa menit pertama.

Menurut dokumentasi Python 2.7.2:

Sebuah objek dapat di-hash jika memiliki nilai hash yang tidak pernah berubah selama masa pakainya (ia membutuhkan metode hash ()), dan dapat dibandingkan dengan objek lain (ia membutuhkan metode eq () atau cmp ()). Objek hash yang membandingkan sama harus memiliki nilai hash yang sama.

Hashabilitas membuat objek dapat digunakan sebagai kunci kamus dan anggota set, karena struktur data ini menggunakan nilai hash secara internal.

Semua objek bawaan Python yang tidak dapat diubah dapat di-hash, sementara tidak ada wadah yang dapat diubah (seperti daftar atau kamus). Objek yang merupakan instance dari kelas yang ditentukan pengguna secara default dapat di-hash; mereka semua membandingkan tidak sama, dan nilai hash mereka adalah id ().

Tupel tidak dapat diubah dalam arti bahwa Anda tidak dapat menambah, menghapus, atau mengganti elemennya, tetapi elemen itu sendiri dapat berubah. Nilai hash daftar bergantung pada nilai hash elemennya, dan karenanya berubah saat Anda mengubah elemen.

Menggunakan id untuk hash daftar akan menyiratkan bahwa semua daftar dibandingkan secara berbeda, yang akan mengejutkan dan tidak nyaman.

Kamus adalah HashMap yang menyimpan peta kunci Anda, nilai yang dikonversi menjadi kunci baru dan pemetaan nilai hash.

sesuatu seperti (kode psuedo):

{key : val}  
hash(key) = val

Jika Anda bertanya-tanya opsi mana yang tersedia yang dapat digunakan sebagai kunci untuk kamus Anda. Kemudian

apa pun yang dapat di-hash (dapat diubah menjadi hash, dan tahan nilai statis yaitu tidak dapat diubah sehingga membuat kunci hash seperti yang dinyatakan di atas) memenuhi syarat tetapi karena daftar atau set objek dapat bervariasi saat bepergian sehingga hash (kunci) juga harus untuk memvariasikan hanya untuk sinkron dengan daftar atau set Anda.

Anda dapat mencoba :

hash(<your key here>)

Jika berfungsi dengan baik, itu dapat digunakan sebagai kunci untuk kamus Anda atau mengubahnya menjadi sesuatu yang dapat hash.

Pendeknya :

1. Ubah daftar itu menjadi tuple(<your list>).
2. Ubah daftar itu menjadi str(<your list>).

dictkunci harus dapat di-hash. Daftar Dapat Diubah dan tidak menyediakan metode hash yang valid .