Apakah kamus Python contoh tabel hash?

187

Salah satu struktur data dasar dalam Python adalah kamus, yang memungkinkan seseorang untuk merekam "kunci" untuk mencari "nilai" dari jenis apa pun. Apakah ini diimplementasikan secara internal sebagai tabel hash? Jika tidak, apa itu?

python hash dictionary hashmap hashtable Tommy Herbert
sumber
2
Jika Anda tertarik pada detail teknis, satu artikel di Beautiful Code membahas tentang internal dictimplementasi Python .
Torsten Marek
Itu adalah salah satu bab favorit saya di Kode Indah.
Ditjen Penerbitan
4
Berikut ini adalah ceramah oleh Brandon Craig Rhodes yang membahas cara kerja kamus python, youtube.com/watch?v=C4Kc8xzcA68 .
chandola
Saya mencari diagram yang mewakili dict untuk sementara waktu sekarang, yang mendeklarasikan implementasi dalam memori dan CPython. Terima kasih telah merujuk buku ini!
Chen A.

Jawaban:

240

Ya, ini adalah pemetaan hash atau tabel hash. Anda dapat membaca deskripsi implementasi dict python, seperti yang ditulis oleh Tim Peters, di sini .

Itu sebabnya Anda tidak dapat menggunakan sesuatu yang 'tidak bisa diacak' sebagai kunci dict, seperti daftar:

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

Anda dapat membaca lebih lanjut tentang tabel hash atau memeriksa bagaimana hash diimplementasikan dalam python dan mengapa itu diterapkan seperti itu .

nosklo
sumber
1
Tautan Tim Peters akan rusak, apakah ada tautan yang bersih di luar sana?
Matt Alcock
1
@MattAlcock: Saya sudah memperbarui tautannya. Terkadang (biasanya karena seseorang ingin alamat emailnya dihapus di suatu tempat) arsip daftar python dibangun kembali dan id email berubah, sehingga memutus tautan ini. Admin pydotorg umumnya berusaha menghindarinya akhir-akhir ini.
Martijn Pieters
Tetapi menggunakan .keys()dapat mengambil daftar kunci. Tabel hash asli tidak akan menyimpan kunci, hanya hash untuk menghemat ruang.
noɥʇʎԀʎzɐɹƆ
Penjelasan lebih lengkap tentang implementasi python dict di sini: laurentluce.com/posts/python-dictionary-implementation
Daniel Goldfarb
32

Harus ada lebih banyak ke kamus Python daripada pencarian tabel pada hash (). Dengan eksperimen kasar saya menemukan tabrakan hash ini :

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

Namun itu tidak merusak kamus:

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

Cek kewarasan:

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

Mungkin ada tingkat pencarian lain di luar hash () yang menghindari tabrakan antara kunci kamus. Atau mungkin dict () menggunakan hash yang berbeda.

(Omong-omong, ini dalam Python 2.7.10. Kisah yang sama dalam Python 3.4.3 dan 3.5.0 dengan tabrakan di hash(1.1) == hash(214748749.8).)

Bob Stein
sumber
14
Jadi tabrakan tidak bisa dihindari. Set S dapat berisi jumlah item yang jauh lebih besar, dan Anda ingin hash ke nomor yang dapat disimpan oleh komputer. Setiap implementasi tabel hash yang dapat digunakan menyelesaikan tabrakan, dengan dua metode yang paling sering adalah a) pengalamatan terbuka dan b) rantai. Hanya karena itu tidak menggunakan hash yang sempurna tidak berarti itu bukan tabel hash.
TurnipEntropy
1
Tabrakan akan terjadi secara umum, karena ada kemungkinan nilai hashable tak terbatas dan kode hash terbatas. Bahkan tabel hash harus menangani tabrakan.
Yanfeng Liu
3
@YanfengLiu Saya percaya itu adalah poin yang persis sama yang dibuat TurnipEntropy.
Bob Stein
1
Dalam Python 3.7, sepertinya ada 2E20 minus 1 nilai hash yang mungkin, pada kenyataannya. Dari -1E20 minus 1 hingga (+) 1E20 minus 1. Coba hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')Ini memberikan desimal 19 digit - -4037225020714749784jika Anda cukup culun untuk peduli. Lanjutkan dengan kata-kata Anda sendiri, anak-anak, dan hash masih berupa angka 19 digit. Saya berasumsi ada batas pada panjang string yang bisa hash dengan Python, tapi aman untuk mengatakan lebih banyak string yang mungkin daripada nilai yang mungkin. Dan hash(False)= 0 omong-omong.
Will Croxford
22

Iya. Secara internal ini diimplementasikan sebagai hashing terbuka berdasarkan polinomial primitif atas Z / 2 ( sumber ).

Ben Hoffstein
sumber
7

Untuk memperluas penjelasan nosklo:

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
Jeremy Cantrell
sumber