Inkonsistensi dalam Big-O dalam menghapus dari ArrayList vs Tabel Hash?

Hal ini dijelaskan di sini. Kuncinya adalah jumlah nilai per Array Dinamis dijaga pada nilai konstan.

Sunting: Seperti yang ditunjukkan Dukeling, jawaban saya menjelaskan mengapa Tabel Hash dengan rangkaian terpisah memiliki kompleksitas penghapusan O(1). Saya harus menambahkan bahwa, di situs web yang Anda lihat, Tabel Hash dikreditkan dengan kompleksitas penghapusan O(1) karena tabel tersebut menganalisis Tabel Hash dengan rangkaian terpisah dan bukan pemeriksaan linier.

Inti dari tabel hash adalah tabel tersebut mendekati kasus terbaik, dimana kasus terbaik berarti satu entri per keranjang. Jelasnya, Anda tidak kesulitan menerima bahwa untuk menghapus satu-satunya entri dari ember membutuhkan waktu O(1).

Ketika banyak terjadi konflik hash, tentunya Anda perlu melakukan banyak shifting saat menggunakan linear probing.

Namun kompleksitas tabel hash berada di bawah asumsi Cukup Uniform Hashing, artinya diasumsikan bahwa akan ada konflik hash dalam jumlah minimal.

Ketika ini terjadi, kita hanya perlu menghapus beberapa nilai dan menggeser tidak ada nilai atau sejumlah kecil nilai (pada dasarnya konstan).

Ketika Anda berbicara tentang kompleksitas suatu algoritma, Anda sebenarnya perlu membahas implementasi konkritnya.

• Tidak ada kelas Java yang disebut "Hash Table" (tentu saja!) atau "HashTable".

• Ada kelas Java yang disebut HashMap dan Hashtable, dan ini memang memiliki O(1) penghapusan.

Tapi mereka tidak bekerja seperti yang Anda pikirkan (semua?) Tabel hash berfungsi. Secara khusus, HashMap dan Hashtable disusun sebagai array pointer ke "rantai".

Artinya, penghapusan terdiri dari pencarian rantai yang sesuai, dan kemudian menelusuri rantai tersebut untuk menemukan entri yang akan dihapus. Langkah pertama adalah waktu konstan (termasuk waktu menghitung kode hash. Langkah kedua sebanding dengan panjang rantai hash. Namun dengan asumsi fungsi hash baik, rata-rata panjang rantai hash adalah konstanta kecil. Oleh karena itu total waktu untuk penghapusan rata-rata adalah O(1).

^{Alasan mengapa rantai hash rata-rata pendek adalah karena kelas HashMap dan Hashtable secara otomatis mengubah ukuran array hash utama ketika "faktor beban" (rasio ukuran array terhadap jumlah entri) melebihi nilai yang telah ditentukan. Dengan asumsi bahwa fungsi hash mendistribusikan kunci (sebenarnya) secara merata, Anda akan menemukan bahwa rantai tersebut kira-kira memiliki panjang yang sama. Dengan asumsi bahwa ukuran array sebanding dengan jumlah total entri, faktor muatan aktual akan menjadi rata-rata panjang rantai hash.}

^{Alasan ini gagal jika fungsi hash tidak mendistribusikan kunci secara merata. Hal ini menyebabkan situasi di mana Anda mendapatkan banyak tabrakan hash. Memang benar, perilaku terburuknya adalah ketika semua kunci memiliki nilai hash yang sama, dan semuanya berakhir pada satu rantai hash dengan semua N entri. Dalam hal ini, penghapusan melibatkan pencarian rantai dengan N entri ... dan itu menjadikannya O(N).}

Ternyata alasan yang sama dapat diterapkan pada bentuk tabel hash lainnya, termasuk yang entrinya disimpan dalam larik hash itu sendiri, dan tabrakan ditangani dengan pemindaian ulang. (Sekali lagi, "triknya" adalah memperluas tabel hash ketika faktor beban menjadi terlalu tinggi.)