Bagaimana Kamus Built In Python Diimplementasikan?

294

Adakah yang tahu bagaimana tipe kamus built-in untuk python diimplementasikan? Pemahaman saya adalah bahwa ini semacam tabel hash, tapi saya belum dapat menemukan jawaban definitif.

python data-structures dictionary ricree
sumber
4
Berikut ini adalah pembicaraan mendalam tentang kamus Python dari 2.7 hingga 3.6. Tautan
Sören

Jawaban:

494

Berikut ini semua tentang dikte Python yang dapat saya kumpulkan (mungkin lebih dari yang ingin diketahui siapa pun; tetapi jawabannya komprehensif).

  • Kamus python diimplementasikan sebagai tabel hash .
  • Tabel hash harus memungkinkan untuk tabrakan hash yaitu bahkan jika dua kunci yang berbeda memiliki nilai hash yang sama, implementasi tabel harus memiliki strategi untuk memasukkan dan mengambil pasangan kunci dan nilai secara jelas.
  • Python dictmenggunakan pengalamatan terbuka untuk menyelesaikan tabrakan hash (dijelaskan di bawah) (lihat dictobject.c: 296-297 ).
  • Tabel hash Python hanyalah blok memori yang berdekatan (semacam array, sehingga Anda dapat melakukan O(1)pencarian berdasarkan indeks).
  • Setiap slot dalam tabel dapat menyimpan satu dan hanya satu entri.Ini penting.
  • Setiap entri dalam tabel sebenarnya kombinasi dari tiga nilai: <hash, key, value> . Ini diimplementasikan sebagai struct C (lihat dictobject.h: 51-56 ).

  • Gambar di bawah ini adalah representasi logis dari tabel hash Python. Pada gambar di bawah ini, 0, 1, ..., i, ...di sebelah kiri adalah indeks slot di tabel hash (mereka hanya untuk tujuan ilustrasi dan tidak disimpan bersama dengan tabel!).

    # Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
i|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
n|      ...        |
-+-----------------+

  • Ketika dikt diinisialisasi baru itu dimulai dengan 8 slot . (lihat dictobject.h: 49 )

  • Saat menambahkan entri ke tabel, kita mulai dengan beberapa slot i,, yang didasarkan pada hash tombol. CPython awalnya menggunakan i = hash(key) & mask(di mana mask = PyDictMINSIZE - 1, tapi itu tidak terlalu penting). Perhatikan saja bahwa slot awal i,, yang diperiksa tergantung pada hash kunci.
  • Jika slot itu kosong, entri ditambahkan ke slot (dengan entri, maksud saya, <hash|key|value> ). Tapi bagaimana jika slot itu ditempati !? Kemungkinan besar karena entri lain memiliki hash yang sama (tabrakan hash!)
  • Jika slot ditempati, CPython (dan bahkan PyPy) membandingkan hash DAN kunci (dengan membandingkan maksud saya ==bukan isperbandingan) dari entri dalam slot terhadap hash dan kunci dari entri saat ini untuk dimasukkan ( dictobject.c : 337.344-345 ) masing-masing. Jika keduanya cocok, maka dianggap entri sudah ada, menyerah dan pindah ke entri berikutnya yang akan dimasukkan. Jika hash atau kunci tidak cocok, itu mulai memeriksa .
  • Probing berarti mencari slot demi slot untuk menemukan slot kosong. Secara teknis kita bisa pergi satu per satu, i+1, i+2, ...dan menggunakan yang tersedia pertama (itu linear probing). Tetapi karena alasan yang dijelaskan dengan indah di komentar (lihat dictobject.c: 33-126 ), CPython menggunakan probing acak . Dalam penyelidikan acak, slot berikutnya diambil dalam urutan acak semu. Entri ditambahkan ke slot kosong pertama. Untuk diskusi ini, algoritma aktual yang digunakan untuk memilih slot berikutnya tidak terlalu penting (lihat dictobject.c: 33-126 untuk algoritme untuk menyelidik). Yang penting adalah bahwa slot diselidiki sampai slot kosong pertama ditemukan.
  • Hal yang sama terjadi pada pencarian, hanya dimulai dengan slot i awal (di mana saya tergantung pada hash kunci). Jika hash dan kunci keduanya tidak cocok dengan entri di slot, itu mulai memeriksa, sampai menemukan slot dengan kecocokan. Jika semua slot habis, itu melaporkan gagal.
  • BTW, dictukurannya akan diubah jika dua pertiga penuh. Ini menghindari memperlambat pencarian. (lihat dictobject.h: 64-65 )

CATATAN: Saya melakukan penelitian tentang implementasi Python Dict sebagai jawaban atas pertanyaan saya sendiri tentang bagaimana beberapa entri dalam suatu dict dapat memiliki nilai hash yang sama. Saya memposting versi tanggapan yang sedikit diedit di sini karena semua penelitian juga sangat relevan untuk pertanyaan ini.

Praveen Gollakota
sumber
8
Anda bilang, ketika hash dan kunci cocok, itu (masukkan op) menyerah dan bergerak. Tidak memasukkan timpa entri yang ada dalam kasus ini?
0xc0de
65

Bagaimana Kamus Built In Python Diimplementasikan?

Inilah kursus singkatnya:

  • Mereka adalah tabel hash. (Lihat di bawah untuk detail implementasi Python.)
  • Layout dan algoritma baru, seperti Python 3.6, membuatnya
    • dipesan dengan memasukkan kunci, dan
    • mengambil lebih sedikit ruang,
    • hampir tanpa biaya dalam kinerja.
  • Optimalisasi lain menghemat ruang saat diksi berbagi kunci (dalam kasus khusus).

Aspek yang dipesan tidak resmi pada Python 3.6 (untuk memberikan implementasi lain kesempatan untuk mengikuti), tetapi resmi dalam Python 3.7 .

Kamus Python adalah Tabel Hash

Untuk waktu yang lama, ini bekerja persis seperti ini. Python akan mengalokasikan 8 baris kosong dan menggunakan hash untuk menentukan di mana harus menempel pasangan kunci-nilai. Misalnya, jika hash untuk kunci berakhir pada 001, itu akan menempel di indeks 1 (yaitu 2) (seperti contoh di bawah ini.)

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Setiap baris membutuhkan 24 byte pada arsitektur 64 bit, 12 pada 32 bit. (Perhatikan bahwa tajuk kolom hanyalah label untuk keperluan kami di sini - tidak ada di memori.)

Jika hash berakhir sama dengan hash kunci yang sudah ada sebelumnya, ini adalah tabrakan, dan kemudian akan menempel pasangan nilai kunci di lokasi yang berbeda.

Setelah 5 nilai kunci disimpan, saat menambahkan pasangan nilai kunci lainnya, kemungkinan tabrakan hash terlalu besar, sehingga kamus menjadi dua kali lipat. Dalam proses 64 bit, sebelum mengubah ukuran, kami memiliki 72 byte kosong, dan setelah itu, kami membuang 240 byte karena 10 baris kosong.

Ini membutuhkan banyak ruang, tetapi waktu pencariannya cukup konstan. Algoritma perbandingan kunci adalah untuk menghitung hash, pergi ke lokasi yang diharapkan, membandingkan id kunci - jika mereka objek yang sama, mereka sama. Jika tidak maka bandingkan nilai hash, jika tidak sama, mereka tidak sama. Lain, maka kita akhirnya membandingkan kunci untuk kesetaraan, dan jika mereka sama, kembalikan nilainya. Perbandingan akhir untuk kesetaraan bisa sangat lambat, tetapi pemeriksaan sebelumnya biasanya memotong perbandingan akhir, membuat pencarian sangat cepat.

Tabrakan memperlambat segalanya, dan penyerang secara teoritis dapat menggunakan tabrakan hash untuk melakukan serangan penolakan layanan, jadi kami mengacak inisialisasi fungsi hash sehingga menghitung hash yang berbeda untuk setiap proses Python baru.

Ruang terbuang yang dijelaskan di atas telah mengarahkan kami untuk memodifikasi implementasi kamus, dengan fitur baru yang menarik bahwa kamus sekarang dipesan melalui penyisipan.

Tabel Compact Hash Baru

Sebagai gantinya, kita mulai dengan mengalokasikan array untuk indeks penyisipan.

Karena pasangan nilai kunci pertama kami berada di slot kedua, kami mengindeks seperti ini:

[null, 0, null, null, null, null, null, null]

Dan meja kami baru saja diisi dengan urutan penyisipan:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

Jadi ketika kita melakukan pencarian untuk kunci, kita menggunakan hash untuk memeriksa posisi yang kita harapkan (dalam hal ini, kita langsung ke indeks 1 dari array), kemudian pergi ke indeks itu di tabel-hash (misalnya indeks 0 ), periksa apakah kunci sama (menggunakan algoritma yang sama dijelaskan sebelumnya), dan jika demikian, kembalikan nilainya.

Kami mempertahankan waktu pencarian konstan, dengan kehilangan kecepatan kecil dalam beberapa kasus dan keuntungan dalam kasus lain, dengan sisi positifnya kami menghemat cukup banyak ruang selama implementasi yang sudah ada sebelumnya dan kami mempertahankan urutan penyisipan. Satu-satunya ruang yang terbuang adalah null byte dalam array indeks.

Raymond Hettinger memperkenalkan ini di python-dev pada bulan Desember 2012. Akhirnya masuk ke CPython dengan Python 3.6 . Pemesanan melalui penyisipan dianggap sebagai detail implementasi untuk 3.6 untuk memungkinkan implementasi lain dari Python kesempatan untuk mengejar ketinggalan.

Tombol Bersama

Optimalisasi lain untuk menghemat ruang adalah implementasi yang berbagi kunci. Jadi, alih-alih memiliki kamus berlebihan yang mengambil semua ruang itu, kami memiliki kamus yang menggunakan kembali kunci bersama dan hash kunci. Anda bisa memikirkannya seperti ini:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Untuk mesin 64 bit, ini bisa menghemat hingga 16 byte per kunci per kamus tambahan.

Tombol Bersama untuk Objek & Alternatif Kustom

Dikte bersama ini dimaksudkan untuk digunakan untuk objek khusus __dict__. Untuk mendapatkan perilaku ini, saya percaya Anda harus menyelesaikan mengisi __dict__sebelum Anda instantiate objek berikutnya ( lihat PEP 412 ). Ini berarti Anda harus menetapkan semua atribut Anda di __init__atau__new__ , jika tidak, Anda mungkin tidak mendapatkan penghematan ruang.

Namun, jika Anda tahu semua atribut Anda pada saat Anda __init__dieksekusi, Anda juga bisa menyediakan __slots__untuk objek Anda, dan menjamin bahwa __dict__itu tidak dibuat sama sekali (jika tidak tersedia pada orang tua), atau bahkan memperbolehkan __dict__tetapi menjamin bahwa atribut Anda yang diramalkan adalah disimpan dalam slot. Untuk lebih lanjut __slots__, lihat jawaban saya di sini .

Lihat juga:

Aaron Hall
sumber
1
Anda mengatakan "kami", dan "untuk memungkinkan implementasi Python lainnya kesempatan untuk mengejar ketinggalan" - apakah ini berarti Anda "mengetahui hal-hal" dan bahwa itu mungkin menjadi fitur permanen? Apakah ada kerugian pada dikte yang dipesan oleh spec?
toonarmycaptain
Kelemahan dari yang dipesan adalah bahwa jika dikte diharapkan dipesan, mereka tidak dapat dengan mudah beralih ke implementasi yang lebih baik / lebih cepat yang tidak dipesan. Tampaknya tidak mungkin yang akan terjadi. Saya "tahu banyak hal" karena saya menonton banyak pembicaraan dan membaca banyak hal yang ditulis oleh anggota inti dan orang lain dengan reputasi dunia nyata yang lebih baik daripada saya, jadi bahkan jika saya tidak memiliki sumber yang segera tersedia untuk dikutip, saya biasanya tahu apa yang saya bicarakan. Tapi saya pikir Anda bisa mendapatkan poin itu dari salah satu pembicaraan Raymond Hettinger.
Aaron Hall
1
Anda menjelaskan dengan agak samar bagaimana cara kerja penyisipan ("Jika hash berakhir sama dengan hash kunci yang sudah ada sebelumnya, ... maka itu akan menempel pasangan nilai kunci di lokasi yang berbeda" - ada?), Tetapi Anda tidak menjelaskan bagaimana pencarian dan tes keanggotaan bekerja. Tidak terlalu jelas bagaimana lokasi ditentukan oleh hash baik, tetapi saya kira bahwa ukuran selalu kekuatan 2, dan Anda mengambil beberapa bit terakhir dari hash ...
Alexey
@Alexey Tautan terakhir yang saya berikan memberi Anda implementasi dict yang dianotasi dengan baik - di mana Anda dapat menemukan fungsi yang melakukan ini, saat ini pada baris 969, bernama find_empty_slot: github.com/python/cpython/blob/master/Objects/dictobject.c # L969 - dan mulai jalur 134 ada beberapa prosa yang menjelaskannya.
Aaron Hall
46

Kamus Python menggunakan pengalamatan terbuka ( referensi di dalam kode Cantik )

NB! Pengalamatan terbuka , alias hashing tertutup harus, seperti dicatat dalam Wikipedia, tidak menjadi bingung dengan hashing terbuka yang berlawanan !

Pengalamatan terbuka berarti bahwa dict menggunakan slot array, dan ketika posisi utama objek diambil dalam dict, tempat objek tersebut dicari pada indeks yang berbeda dalam array yang sama, menggunakan skema "perturbation", di mana nilai hash objek memainkan bagian .

u0b34a0f6ae
sumber
5
"jangan bingung dengan hashing terbuka yang berlawanan! (yang kita lihat dalam jawaban yang diterima)." - Saya tidak yakin jawaban mana yang diterima ketika Anda menulisnya, atau apa jawaban itu pada saat itu - tetapi komentar yang ditulis dalam kurung ini saat ini tidak benar untuk jawaban yang diterima dan sebaiknya dihapus.
Tony Delroy