Saya mencoba memahami hashfungsi Python di bawah tenda. Saya membuat kelas khusus di mana semua contoh mengembalikan nilai hash yang sama.
class C:
def __hash__(self):
return 42
Saya hanya berasumsi bahwa hanya satu instance dari kelas di atas yang dapat berada dalam a dictkapan saja, tetapi sebenarnya a dictdapat memiliki banyak elemen dengan hash yang sama.
c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements
Saya bereksperimen sedikit lebih banyak dan menemukan bahwa jika saya mengganti __eq__metode sedemikian rupa sehingga semua contoh kelas sebanding, maka dictsatu - satunya memungkinkan satu contoh.
class D:
def __hash__(self):
return 42
def __eq__(self, other):
return True
p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element
Jadi saya ingin tahu bagaimana a dictbisa memiliki banyak elemen dengan hash yang sama.
Jawaban:
Untuk penjelasan rinci tentang cara kerja hashing Python, lihat jawaban saya untuk Mengapa pengembalian awal lebih lambat dari yang lain?
Pada dasarnya ini menggunakan hash untuk memilih slot di tabel. Jika ada nilai di slot dan hash cocok, itu membandingkan item untuk melihat apakah mereka sama.
Jika hash tidak cocok atau item tidak sama, maka ia mencoba slot lain. Ada rumus untuk memilih ini (yang saya jelaskan dalam jawaban referensi), dan secara bertahap menarik bagian yang tidak terpakai dari nilai hash; tetapi setelah menggunakan semuanya, ini pada akhirnya akan bekerja melalui semua slot di tabel hash. Itu menjamin pada akhirnya kami menemukan item yang cocok atau slot kosong. Ketika pencarian menemukan slot kosong, itu memasukkan nilai atau menyerah (tergantung apakah kita menambahkan atau mendapatkan nilai).
Hal penting yang perlu diperhatikan adalah tidak ada daftar atau keranjang: hanya ada tabel hash dengan jumlah slot tertentu, dan setiap hash digunakan untuk menghasilkan urutan slot kandidat.
sumber
Berikut adalah segala sesuatu tentang Python dicts yang bisa saya kumpulkan (mungkin lebih dari siapa pun yang ingin tahu; tetapi jawabannya komprehensif). Teriakan kepada Duncan karena menunjukkan bahwa penis Python menggunakan slot dan membawa saya ke lubang kelinci ini.
O(1)pencarian berdasarkan indeks).Gambar di bawah ini adalah representasi logis dari tabel hash python. Pada gambar di bawah ini, 0, 1, ..., i, ... di sebelah kiri adalah indeks dari slot di tabel hash (mereka hanya untuk tujuan ilustrasi dan tidak disimpan bersama dengan tabel jelas!).
# Logical model of Python Hash table -+-----------------+ 0| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+Saat dikt baru diinisialisasi, ia dimulai dengan 8 slot . (lihat dictobject.h: 49 )
iyang didasarkan pada hash kunci. CPython menggunakan inisiali = hash(key) & mask. Di manamask = PyDictMINSIZE - 1, tapi itu tidak terlalu penting). Perhatikan bahwa slot awal, i, yang diperiksa tergantung pada hash kunci.<hash|key|value>). Tapi bagaimana jika slot itu ditempati !? Kemungkinan besar karena entri lain memiliki hash yang sama (benturan hash!)==perbandingan bukanisperbandingan) dari entri di slot terhadap kunci entri saat ini yang akan dimasukkan ( dictobject.c: 337 , 344-345 ). Jika keduanya cocok, maka dianggap entri sudah ada, menyerah dan pindah ke entri berikutnya untuk disisipkan. Jika salah satu hash atau kunci tidak cocok, itu mulai menyelidiki .Ini dia! Implementasi Python dari dict memeriksa persamaan hash dari dua kunci dan persamaan normal (
==) dari kunci saat memasukkan item. Jadi Singkatnya, jika ada dua kunci,adanbdanhash(a)==hash(b), namuna!=b, kemudian keduanya dapat eksis secara harmonis dalam dict Python. Tetapi jikahash(a)==hash(b)dana==b, maka keduanya tidak bisa berada dalam dikt yang sama.Karena kita harus menyelidiki setelah setiap tabrakan hash, satu efek samping dari tabrakan hash yang terlalu banyak adalah pencarian dan penyisipan akan menjadi sangat lambat (seperti yang ditunjukkan Duncan di komentar ).
Saya kira jawaban singkat untuk pertanyaan saya adalah, "Karena begitulah cara penerapannya dalam kode sumber;)"
Meskipun ini bagus untuk diketahui (untuk poin geek?), Saya tidak yakin bagaimana ini bisa digunakan dalam kehidupan nyata. Karena kecuali Anda mencoba untuk secara eksplisit merusak sesuatu, mengapa dua objek yang tidak sama memiliki hash yang sama?
sumber
Sunting : jawaban di bawah ini adalah salah satu cara yang mungkin untuk menangani tabrakan hash, namun itu bukan cara Python melakukannya. Wiki Python yang direferensikan di bawah ini juga salah. Sumber terbaik yang diberikan oleh @Duncan di bawah ini adalah implementasinya sendiri: https://github.com/python/cpython/blob/master/Objects/dictobject.c Saya minta maaf atas kesalahannya .
Ini menyimpan daftar (atau ember) elemen di hash kemudian mengulang melalui daftar itu sampai menemukan kunci sebenarnya dalam daftar itu. Sebuah gambar mengatakan lebih dari seribu kata:
Di sini Anda melihat
John SmithdanSandra Deekeduanya hash152. Ember152berisi keduanya. Saat mencarinyaSandra Dee, pertama kali menemukan daftar di keranjang152, lalu mengulang melalui daftar itu hinggaSandra Deeditemukan dan kembali521-6955.Berikut ini salah, hanya di sini untuk konteks: Di wiki Python, Anda dapat menemukan kode (pseudo?) Bagaimana Python melakukan pencarian.
Sebenarnya ada beberapa solusi yang mungkin untuk masalah ini, lihat artikel wikipedia untuk tinjauan yang bagus: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
sumber
Tabel hash, secara umum harus mengizinkan tabrakan hash! Anda akan menjadi tidak beruntung dan dua hal pada akhirnya akan berhubungan dengan hal yang sama. Di bawahnya, ada sekumpulan objek dalam daftar item yang memiliki kunci hash yang sama. Biasanya, hanya ada satu hal dalam daftar itu, tetapi dalam kasus ini, itu akan terus menumpuknya menjadi satu. Satu-satunya cara untuk mengetahui bahwa mereka berbeda adalah melalui operator yang sama.
Jika ini terjadi, performa Anda akan menurun seiring waktu, itulah sebabnya Anda ingin fungsi hash menjadi "seacak mungkin".
sumber
Di utas saya tidak melihat apa sebenarnya yang dilakukan python dengan instance dari kelas yang ditentukan pengguna ketika kami memasukkannya ke dalam kamus sebagai kunci. Mari kita baca beberapa dokumentasi: ini mendeklarasikan bahwa hanya objek yang dapat di-hash yang dapat digunakan sebagai kunci. Hashable adalah semua kelas bawaan yang tidak dapat diubah dan semua kelas yang ditentukan pengguna.
Jadi jika Anda memiliki __hash__ secara konstan di kelas Anda, tetapi tidak menyediakan metode __cmp__ atau __eq__, maka semua instance Anda tidak sama untuk kamus. Di sisi lain, jika Anda menyediakan metode __cmp__ atau __eq__, tetapi tidak menyediakan __hash__, instance Anda masih tidak sama dalam kamus.
class A(object): def __hash__(self): return 42 class B(object): def __eq__(self, other): return True class C(A, B): pass dict_a = {A(): 1, A(): 2, A(): 3} dict_b = {B(): 1, B(): 2, B(): 3} dict_c = {C(): 1, C(): 2, C(): 3} print(dict_a) print(dict_b) print(dict_c)Keluaran
{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2} {<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3} {<__main__.C object at 0x7f9672f04a10>: 3}sumber