Apakah hashmap Java benar-benar O (1)?

159

Saya telah melihat beberapa klaim menarik tentang hashmaps SO re Java dan O(1)waktu pencarian mereka . Adakah yang bisa menjelaskan mengapa demikian? Kecuali jika hashmaps ini sangat berbeda dari algoritma hashing yang saya beli, pasti selalu ada dataset yang berisi collision.

Dalam hal ini, pencarian akan O(n)lebih daripada O(1).

Dapatkah seseorang menjelaskan apakah mereka adalah O (1) dan, jika demikian, bagaimana mereka mencapai hal ini?

paxdiablo
sumber
1
Saya tahu ini mungkin bukan jawaban tetapi saya ingat Wikipedia memiliki artikel yang sangat bagus tentang ini. Jangan lewatkan analisis kinerja bagian
victor hugo
28
Notasi O besar memberi batas atas untuk jenis analisis tertentu yang Anda lakukan. Anda masih harus menentukan apakah Anda tertarik pada kasus terburuk, kasus rata-rata, dll.
Dan Homerick

Jawaban:

127

Fitur khusus dari HashMap adalah bahwa tidak seperti, katakanlah, pohon seimbang, perilakunya adalah probabilistik. Dalam kasus-kasus ini, biasanya sangat membantu untuk membicarakan kompleksitas dalam hal kemungkinan suatu peristiwa terburuk terjadi. Untuk peta hash, itu tentu saja adalah kasus tabrakan sehubungan dengan seberapa penuh peta itu terjadi. Tabrakan cukup mudah diperkirakan.

p collision = n / kapasitas

Jadi peta hash dengan jumlah elemen yang kecil kemungkinan besar akan mengalami setidaknya satu tabrakan. Notasi O besar memungkinkan kita melakukan sesuatu yang lebih menarik. Perhatikan bahwa untuk sembarang, konstanta tetap k.

O (n) = O (k * n)

Kita dapat menggunakan fitur ini untuk meningkatkan kinerja peta hash. Kami malah bisa memikirkan kemungkinan paling banyak 2 tabrakan.

p collision x 2 = (n / kapasitas) 2

Ini jauh lebih rendah. Karena biaya penanganan satu tabrakan tambahan tidak relevan dengan kinerja Big O, kami telah menemukan cara untuk meningkatkan kinerja tanpa benar-benar mengubah algoritma! Kita dapat melakukan ini secara umum

p collision xk = (n / kapasitas) k

Dan sekarang kita dapat mengabaikan sejumlah tabrakan yang sewenang-wenang dan berakhir dengan kemungkinan kecil semakin banyak tabrakan daripada yang kita perhitungkan. Anda bisa mendapatkan probabilitas ke tingkat kecil sewenang-wenang dengan memilih k yang benar, semua tanpa mengubah implementasi algoritma yang sebenarnya.

Kita membicarakan hal ini dengan mengatakan bahwa peta hash memiliki akses O (1) dengan probabilitas tinggi

SingleNegationElimination
sumber
Bahkan dengan HTML, saya masih tidak begitu senang dengan fraksi. Bersihkan mereka jika Anda bisa memikirkan cara yang baik untuk melakukannya.
SingleNegationElimination
4
Sebenarnya, apa yang dikatakan di atas adalah bahwa efek O (log N) dikubur, untuk nilai-nilai non-ekstrim N, oleh overhead tetap.
Hot Licks
Secara teknis, angka yang Anda berikan adalah nilai yang diharapkan dari jumlah tabrakan, yang dapat sama dengan probabilitas tabrakan tunggal.
Simon Kuang
1
Apakah ini mirip dengan analisis diamortisasi?
Lostsoul29
1
@ OleV.V. kinerja HashMap yang baik selalu bergantung pada distribusi fungsi hash Anda yang baik. Anda dapat memperdagangkan kualitas hash yang lebih baik untuk kecepatan hashing dengan menggunakan fungsi hashing kriptografis pada input Anda.
SingleNegationElimination
38

Anda tampaknya mencampur perilaku kasus terburuk dengan rata-rata (diharapkan) runtime. Yang pertama memang O (n) untuk tabel hash secara umum (yaitu tidak menggunakan hashing sempurna) tetapi ini jarang relevan dalam praktek.

Setiap implementasi tabel hash yang dapat diandalkan, ditambah dengan hash setengah layak, memiliki kinerja pengambilan O (1) dengan faktor yang sangat kecil (2, pada kenyataannya) dalam kasus yang diharapkan, dalam margin varians yang sangat sempit.

Konrad Rudolph
sumber
6
Saya selalu berpikir batas atas adalah kasus terburuk tetapi tampaknya saya salah - Anda dapat memiliki batas atas untuk kasus rata-rata. Jadi tampaknya orang yang mengklaim O (1) seharusnya menjelaskan bahwa itu adalah untuk kasus rata-rata. Kasus terburuk adalah kumpulan data di mana ada banyak tabrakan membuatnya O (n). Itu masuk akal sekarang.
paxdiablo
2
Anda mungkin harus membuatnya jelas bahwa ketika Anda menggunakan notasi O besar untuk kasus rata-rata Anda berbicara tentang batas atas pada fungsi runtime yang diharapkan yang merupakan fungsi matematika yang jelas. Kalau tidak, jawaban Anda tidak masuk akal.
ldog
1
gmatt: Saya tidak yakin saya mengerti keberatan Anda: notasi-O besar adalah batas atas pada fungsi menurut definisi . Apa lagi yang bisa saya maksudkan?
Konrad Rudolph
3
baik biasanya dalam literatur komputer Anda melihat notasi O besar yang mewakili upperbound pada fungsi kompleksitas ruang runtime atau dari suatu algoritma. Dalam hal ini upperbound sebenarnya pada harapan yang dengan sendirinya bukan fungsi tetapi operator pada fungsi (Variabel Acak) dan sebenarnya merupakan integral (lebesgue.) Fakta bahwa Anda dapat mengikat hal seperti itu tidak boleh diambil begitu saja dan tidak sepele.
ldog
31

Di Jawa, HashMap bekerja dengan menggunakan hashCode untuk menemukan ember. Setiap ember adalah daftar item yang berada di dalam ember itu. Item dipindai, menggunakan yang sama untuk perbandingan. Saat menambahkan item, HashMap diubah ukurannya setelah persentase beban tertentu tercapai.

Jadi, kadang-kadang harus dibandingkan dengan beberapa item, tetapi umumnya jauh lebih dekat dengan O (1) daripada O (n). Untuk tujuan praktis, hanya itu yang perlu Anda ketahui.

FogleBird
sumber
11
Yah, karena big-O seharusnya menentukan batas, tidak ada bedanya apakah itu lebih dekat ke O (1) atau tidak. Bahkan O (n / 10 ^ 100) masih O (n). Saya mendapatkan poin Anda tentang efisiensi membawa kemudian rasio turun tetapi itu masih menempatkan algoritma pada O (n).
paxdiablo
4
Analisis peta-peta biasanya pada kasus rata-rata, yaitu O (1) (dengan kolusi) Pada kasus terburuk, Anda dapat memiliki O (n), tetapi biasanya tidak demikian. mengenai perbedaan - O (1) berarti Anda mendapatkan waktu akses yang sama terlepas dari jumlah item pada bagan, dan itu biasanya terjadi (selama ada proporsi yang baik antara ukuran tabel dan 'n ')
Liran Orevi
4
Perlu juga dicatat, bahwa itu masih persis O (1), bahkan jika pemindaian bucket membutuhkan waktu karena ada beberapa elemen di dalamnya. Selama bucket memiliki ukuran maksimum tetap, ini hanyalah faktor konstan yang tidak relevan dengan klasifikasi O (). Tapi tentu saja bisa ada lebih banyak elemen dengan kunci "mirip" telah ditambahkan, sehingga bucket ini meluap dan Anda tidak dapat menjamin konstanta lagi.
sth
@sth Mengapa ember memiliki ukuran maksimum tetap !?
Navin
31

Ingat bahwa o (1) tidak berarti bahwa setiap pencarian hanya memeriksa satu item - itu berarti bahwa jumlah rata-rata barang yang diperiksa tetap konstan dengan jumlah item dalam wadah. Jadi jika diperlukan rata-rata 4 perbandingan untuk menemukan item dalam wadah dengan 100 item, itu juga harus mengambil rata-rata 4 perbandingan untuk menemukan item dalam wadah dengan 10.000 item, dan untuk jumlah item lainnya (selalu ada sedikit varians, terutama di sekitar titik-titik di mana tabel hash mengulangi, dan ketika ada sejumlah item yang sangat kecil).

Jadi tabrakan tidak mencegah wadah memiliki o (1) operasi, selama jumlah rata-rata kunci per ember tetap dalam batas yang tetap.

Daniel James
sumber
16

Saya tahu ini adalah pertanyaan lama, tetapi sebenarnya ada jawaban baru untuk itu.

Anda benar bahwa peta hash tidak benar-benar O(1), secara tegas, karena karena jumlah elemen menjadi besar secara sewenang-wenang, akhirnya Anda tidak akan dapat mencari dalam waktu yang konstan (dan notasi-O didefinisikan dalam bentuk angka yang dapat menjadi besar secara sewenang-wenang).

Tetapi itu tidak berarti bahwa kompleksitas waktu nyata adalah O(n)- karena tidak ada aturan yang mengatakan bahwa bucket harus diimplementasikan sebagai daftar linear.

Faktanya, Java 8 mengimplementasikan bucket TreeMapssetelah mereka melampaui ambang batas, yang membuat waktu aktual O(log n).

ajb
sumber
4

Jika jumlah ember (sebut saja b) dipertahankan konstan (kasing biasa), maka pencarian sebenarnya O (n).
Saat n bertambah besar, jumlah elemen di setiap bucket rata-rata n / b. Jika resolusi tabrakan dilakukan dengan salah satu cara yang biasa (daftar tertaut misalnya), maka pencarian adalah O (n / b) = O (n).

Notasi O adalah tentang apa yang terjadi ketika n menjadi lebih besar dan lebih besar. Ini bisa menyesatkan ketika diterapkan pada algoritma tertentu, dan tabel hash adalah contohnya. Kami memilih jumlah ember berdasarkan pada berapa banyak elemen yang kami harapkan untuk ditangani. Ketika n adalah tentang ukuran yang sama dengan b, maka pencarian kira-kira konstan-waktu, tetapi kita tidak dapat menyebutnya O (1) karena O didefinisikan dalam batasan sebagai n → ∞.

IJ Kennedy
sumber
4

O(1+n/k)di mana kjumlah ember.

Jika implementasi set k = n/alphamaka itu adalah O(1+alpha) = O(1)karena alphaadalah sebuah konstanta.

Satyanarayana Kakollu
sumber
1
Apa yang ditandakan oleh alfa konstan ?
Prahalad Deshpande
2

Kami telah menetapkan bahwa deskripsi standar pencarian tabel hash menjadi O (1) mengacu pada waktu rata-rata yang diharapkan, bukan kinerja kasus terburuk yang ketat. Untuk tabel hash yang menyelesaikan tabrakan dengan chaining (seperti hashmap Java) ini secara teknis O (1 + α) dengan fungsi hash yang baik , di mana α adalah faktor beban tabel. Masih konstan selama jumlah objek yang Anda simpan tidak lebih dari faktor konstan yang lebih besar dari ukuran tabel.

Juga telah dijelaskan bahwa secara ketat dimungkinkan untuk membuat input yang membutuhkan pencarian O ( n ) untuk setiap fungsi hash deterministik. Tetapi juga menarik untuk mempertimbangkan waktu perkiraan terburuk , yang berbeda dari waktu pencarian rata-rata. Menggunakan rantai ini adalah O (1 + panjang rantai terpanjang), misalnya Θ (log n / log n ) ketika α = 1.

Jika Anda tertarik dengan cara-cara teoritis untuk mencapai waktu pencarian yang diharapkan, maka Anda dapat membaca tentang hashing sempurna dinamis yang menyelesaikan tabrakan secara rekursif dengan tabel hash lain!

jtb
sumber
2

Ini adalah O (1) hanya jika fungsi hashing Anda sangat bagus. Implementasi tabel hash Java tidak melindungi terhadap fungsi hash yang buruk.

Apakah Anda perlu menumbuhkan tabel saat Anda menambahkan item atau tidak tidak relevan dengan pertanyaan karena ini adalah tentang waktu pencarian.

Antti Huima
sumber
2

Elemen di dalam HashMap disimpan sebagai array dari daftar tertaut (node), setiap daftar tertaut dalam array mewakili sebuah ember untuk nilai hash unik dari satu atau lebih kunci.
Saat menambahkan entri di HashMap, kode hash kunci digunakan untuk menentukan lokasi ember dalam array, sesuatu seperti:

location = (arraylength - 1) & keyhashcode

Di sini & mewakili operator DAN bitwise.

Sebagai contoh: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Selama mendapatkan operasi itu menggunakan cara yang sama untuk menentukan lokasi ember untuk kunci. Di bawah kasus terbaik setiap kunci memiliki kode hash unik dan menghasilkan ember unik untuk setiap kunci, dalam hal ini metode get menghabiskan waktu hanya untuk menentukan lokasi bucket dan mengambil nilai yang konstan O (1).

Dalam kasus terburuk, semua kunci memiliki kode hash yang sama dan disimpan dalam ember yang sama, ini menghasilkan melintasi seluruh daftar yang mengarah ke O (n).

Dalam kasus java 8, bucket Linked List diganti dengan TreeMap jika ukurannya tumbuh lebih dari 8, ini mengurangi efisiensi pencarian case terburuk ke O (log n).

Ramprabhu
sumber
1

Ini pada dasarnya berlaku untuk sebagian besar implementasi tabel hash di sebagian besar bahasa pemrograman, karena algoritma itu sendiri tidak benar-benar berubah.

Jika tidak ada tabrakan hadir dalam tabel, Anda hanya perlu melakukan pencarian tunggal, oleh karena itu waktu berjalan adalah O (1). Jika ada tabrakan, Anda harus melakukan lebih dari satu pencarian, yang menurunkan kinerja menuju O (n).

Tobias Svensson
sumber
1
Itu mengasumsikan waktu berjalan dibatasi oleh waktu pencarian. Dalam prakteknya Anda akan menemukan banyak situasi di mana fungsi hash menyediakan batas (String)
Stephan Eggermont
1

Itu tergantung pada algoritma yang Anda pilih untuk menghindari tabrakan. Jika implementasi Anda menggunakan rantai terpisah, maka skenario terburuk terjadi di mana setiap elemen data hash dengan nilai yang sama (misalnya, pilihan fungsi hash yang buruk). Dalam hal ini, pencarian data tidak berbeda dari pencarian linear pada daftar tertaut yaitu O (n). Namun, probabilitas kejadian itu dapat diabaikan dan pencarian kasus terbaik dan rata-rata tetap konstan yaitu O (1).

Nizar Grira
sumber
1

Di samping akademis, dari perspektif praktis, HashMaps harus diterima memiliki dampak kinerja yang tidak penting (kecuali jika profiler Anda memberi tahu Anda sebaliknya.)

Ryan Emerle
sumber
4
Tidak dalam aplikasi praktis. Segera setelah Anda menggunakan string sebagai kunci, Anda akan melihat bahwa tidak semua fungsi hash ideal, dan beberapa sangat lambat.
Stephan Eggermont
1

Hanya dalam kasus teoretis, ketika kode hash selalu berbeda dan bucket untuk setiap kode hash juga berbeda, O (1) akan ada. Kalau tidak, itu adalah urutan konstan yaitu pada peningkatan hashmap, urutan pencariannya tetap konstan.

sn.anurag
sumber
0

Tentu saja kinerja hashmap akan bergantung pada kualitas fungsi hashCode () untuk objek yang diberikan. Namun, jika fungsi diimplementasikan sedemikian rupa sehingga kemungkinan tabrakan sangat rendah, itu akan memiliki kinerja yang sangat baik (ini tidak sepenuhnya O (1) di setiap kasus tetapi dalam kebanyakan kasus).

Sebagai contoh implementasi default di Oracle JRE adalah dengan menggunakan nomor acak (yang disimpan dalam instance objek sehingga tidak berubah - tetapi juga menonaktifkan penguncian bias, tapi itu diskusi lain) sehingga kemungkinan tabrakan adalah sangat rendah.

Grey Panther
sumber
"Dalam banyak kasus". Lebih khusus lagi, total waktu akan cenderung ke arah K kali N (di mana K adalah konstan) sebagaimana N cenderung ke arah tak terhingga.
ChrisW
7
Ini salah. Indeks dalam tabel hash akan ditentukan melalui hashCode % tableSizeyang berarti pasti akan ada tabrakan. Anda tidak dapat sepenuhnya menggunakan 32-bit. Itu semacam titik tabel hash ... Anda mengurangi ruang pengindeksan yang besar menjadi yang kecil.
FogleBird
1
"Anda dijamin tidak akan ada tabrakan" Tidak, bukan karena ukuran peta lebih kecil dari ukuran hash: misalnya jika ukuran peta dua, maka dijamin tabrakan (tidak masalah apa hash) jika / ketika saya mencoba memasukkan tiga elemen.
ChrisW
Tetapi bagaimana Anda mengkonversi dari kunci ke alamat memori di O (1)? Maksud saya seperti x = array ["key"]. Kuncinya bukan alamat memori sehingga masih harus berupa pencarian O (n).
paxdiablo
1
"Saya percaya bahwa jika Anda tidak mengimplementasikan kode hash, itu akan menggunakan alamat memori objek". Bisa menggunakan itu, tetapi kode hash standar untuk standar Java Oracle sebenarnya nomor acak 25-bit yang disimpan dalam header objek, jadi 64/32-bit tidak ada konsekuensinya.
Boann