Apa pentingnya faktor beban di HashMap?

HashMapmemiliki dua sifat penting: sizedan load factor. Saya membaca dokumentasi Java dan dikatakan 0.75fsebagai faktor pemuatan awal. Tetapi saya tidak dapat menemukan penggunaannya yang sebenarnya.

Adakah yang bisa menggambarkan skenario berbeda di mana kita perlu mengatur load factor dan berapa nilai sampel ideal untuk kasus yang berbeda?

The dokumentasi menjelaskan dengan cukup baik:

Sebuah instance dari HashMap memiliki dua parameter yang mempengaruhi kinerjanya: kapasitas awal dan faktor beban. Kapasitas adalah jumlah ember di tabel hash, dan kapasitas awal hanyalah kapasitas pada saat tabel hash dibuat. Load factor adalah ukuran seberapa penuh tabel hash diizinkan dapatkan sebelum kapasitasnya meningkat secara otomatis. Ketika jumlah entri dalam tabel hash melebihi produk dari faktor beban dan kapasitas saat ini, tabel hash diulang (yaitu, struktur data internal dibangun kembali) sehingga tabel hash memiliki sekitar dua kali jumlah ember.

Sebagai aturan umum, faktor muatan default (0,75) menawarkan pertukaran yang baik antara biaya waktu dan ruang. Nilai yang lebih tinggi mengurangi overhead ruang tetapi meningkatkan biaya pencarian (tercermin dalam sebagian besar operasi kelas HashMap, termasuk mendapatkan dan meletakkan). Jumlah entri yang diharapkan dalam peta dan faktor muatannya harus diperhitungkan saat menetapkan kapasitas awalnya, sehingga meminimalkan jumlah operasi pengulangan. Jika kapasitas awal lebih besar dari jumlah entri maksimum dibagi dengan faktor muatan, tidak ada operasi pengulangan yang akan terjadi.

Seperti dengan semua optimasi kinerja, itu ide yang baik untuk menghindari mengoptimalkan hal-hal sebelum waktunya (yaitu tanpa data keras di mana kemacetan berada).

Kapasitas awal default dari HashMaptake adalah 16 dan load factor 0.75f ​​(yaitu 75% dari ukuran peta saat ini). Faktor beban mewakili pada tingkat apa HashMapkapasitas harus digandakan.

Misalnya produk kapasitas dan load factor sebagai 16 * 0.75 = 12. Ini menyatakan bahwa setelah menyimpan pasangan kunci - nilai 12 ke dalam HashMap, kapasitasnya menjadi 32.

Sebenarnya, dari perhitungan saya, load factor "sempurna" lebih dekat ke log 2 (~ 0,7). Meskipun faktor beban apa pun yang kurang dari ini akan menghasilkan kinerja yang lebih baik. Saya pikir 0,75 mungkin ditarik keluar dari topi.

Bukti:

Rantai dapat dihindari dan prediksi cabang dieksploitasi dengan memprediksi apakah ember kosong atau tidak. Sebuah ember mungkin kosong jika probabilitas kosong melebihi .5.

Mari s mewakili ukuran dan jumlah kunci yang ditambahkan. Menggunakan teorema binomial, probabilitas ember menjadi kosong adalah:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

Jadi, ember mungkin kosong jika jumlahnya kurang dari

log(2)/log(s/(s - 1)) keys

Ketika s mencapai tak terhingga dan jika jumlah kunci yang ditambahkan sedemikian sehingga P (0) = .5, maka n / s mendekati log (2) dengan cepat:

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...

Apa itu load factor?

Jumlah kapasitas yang akan habis untuk HashMap untuk meningkatkan kapasitasnya?

Mengapa memuat faktor?

Load factor secara default 0,75 dari kapasitas awal (16) oleh karena itu 25% dari bucket akan bebas sebelum ada peningkatan kapasitas & ini membuat banyak bucket baru dengan kode hash baru yang menunjukkan bahwa ada setelah peningkatan dalam jumlah ember.

Sekarang mengapa Anda harus menyimpan banyak ember gratis & apa dampak menjaga ember gratis pada kinerja?

Jika Anda mengatur faktor pemuatan untuk mengatakan 1.0 maka sesuatu yang sangat menarik mungkin terjadi.

Katakanlah Anda menambahkan objek x ke hashmap Anda yang hashCode-nya adalah 888 & di hashmap Anda, ember yang mewakili kode hash adalah gratis, jadi objek x ditambahkan ke ember, tetapi sekarang lagi katakan jika Anda menambahkan objek lain y yang hashCode adalah juga 888 maka objek Anda y akan ditambahkan pasti TETAPI di akhir ember ( karena ember tidak lain adalah implementasi terkait, tetapi menyimpan kunci, nilai & selanjutnya ) sekarang ini memiliki dampak kinerja! Karena objek Anda tidak lagi ada di kepala ember jika Anda melakukan pencarian, waktu yang diperlukan tidak akan menjadi O (1)kali ini tergantung pada berapa banyak item yang ada di ember yang sama. Ini disebut tabrakan hash & ini bahkan terjadi ketika faktor loading Anda kurang dari 1.

Korelasi antara kinerja, tabrakan hash & loading factor?

Faktor muatan yang lebih rendah = lebih banyak bucket gratis = lebih sedikit peluang tabrakan = kinerja tinggi = kebutuhan ruang yang tinggi.

Koreksi saya jika saya salah di suatu tempat.

Dari dokumentasi :

Load factor adalah ukuran seberapa penuh tabel hash diizinkan dapatkan sebelum kapasitasnya meningkat secara otomatis

Ini benar-benar tergantung pada persyaratan khusus Anda, tidak ada "aturan praktis" untuk menentukan faktor muatan awal.

Untuk HashMap DEFAULT_INITIAL_CAPACITY = 16 dan DEFAULT_LOAD_FACTOR = 0.75f artinya jumlah MAX SEMUA Entri di HashMap = 16 * 0.75 = 12 . Ketika elemen ketiga belas akan ditambahkan kapasitas (ukuran array) dari HashMap akan digandakan! Ilustrasi sempurna menjawab pertanyaan ini: gambar diambil dari sini:

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

Jika ember terlalu penuh, maka kita harus memeriksa

daftar tertaut yang sangat panjang.

Dan itu agak mengalahkan intinya.

Jadi, inilah contoh di mana saya memiliki empat ember.

Saya memiliki gajah dan musang di HashSet saya sejauh ini.

Ini situasi yang cukup bagus, bukan?

Setiap elemen memiliki nol atau satu elemen.

Sekarang kita menempatkan dua elemen lagi ke dalam HashSet kita.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

Ini juga tidak terlalu buruk.

Setiap ember hanya memiliki satu elemen. Jadi jika saya ingin tahu, apakah ini mengandung panda?

Saya dapat dengan cepat melihat bucket nomor 1 dan ternyata tidak

disana dan

Saya tahu itu tidak ada dalam koleksi kami.

Jika saya ingin tahu apakah itu berisi kucing, saya melihat ember

nomor 3,

Saya menemukan kucing, saya sangat cepat tahu apakah itu ada di kita

koleksi.

Bagaimana jika saya menambahkan koala, itu tidak terlalu buruk.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

Mungkin sekarang alih-alih di ember nomor 1 hanya melihat

satu elemen,

Saya perlu melihat dua.

Tapi setidaknya saya tidak harus melihat gajah, luak dan

kucing.

Jika saya lagi mencari panda, itu hanya bisa di ember

nomor 1 dan

Saya tidak perlu melihat apa pun selain berang-berang dan

koala.

Tapi sekarang saya memasukkan buaya ke dalam ember nomor 1 dan Anda bisa

lihat mungkin kemana ini pergi.

Bahwa jika bucket nomor 1 terus semakin besar dan semakin besar

lebih besar, maka saya pada dasarnya harus memeriksa semua

elemen-elemen itu untuk ditemukan

sesuatu yang harus ada di bucket nomor 1.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

Jika saya mulai menambahkan string ke ember lain,

benar, masalahnya semakin besar di setiap

ember tunggal.

Bagaimana kita menghentikan ember kita menjadi terlalu penuh?

Solusinya di sini adalah itu

          "the HashSet can automatically

        resize the number of buckets."

Ada HashSet menyadari bahwa ember mendapatkan

terlalu penuh.

Ini kehilangan keuntungan dari ini semua pencarian untuk

elemen.

Dan itu hanya akan membuat lebih banyak ember (umumnya dua kali seperti sebelumnya) dan

lalu tempatkan elemen ke dalam ember yang benar.

Jadi inilah implementasi dasar HashSet kami dengan terpisah

rantai. Sekarang saya akan membuat "HashSet ukuran-sendiri".

HashSet ini akan menyadari bahwa embernya

terlalu penuh dan

perlu lebih banyak ember.

loadFactor adalah bidang lain di kelas HashSet kami.

loadFactor mewakili jumlah rata-rata elemen per

ember,

di atas yang ingin kami ubah ukurannya.

loadFactor adalah keseimbangan antara ruang dan waktu.

Jika ember terlalu penuh maka kami akan mengubah ukuran.

Tentu saja itu butuh waktu, tetapi

itu mungkin menghemat waktu kita di jalan jika ember adalah a

sedikit lebih kosong.

Mari kita lihat sebuah contoh.

Inilah HashSet, kami telah menambahkan empat elemen sejauh ini.

Gajah, anjing, kucing dan ikan.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

Pada titik ini, saya telah memutuskan bahwa loadFactor, the

ambang,

jumlah rata-rata elemen per ember yang saya terima

dengan, adalah 0,75.

Jumlah bucket adalah bucket.panjang, yaitu 6, dan

pada titik ini HashSet kami memiliki empat elemen, jadi

ukuran saat ini adalah 4.

Kami akan mengubah ukuran HashSet kami, yaitu kami akan menambahkan lebih banyak ember,

ketika jumlah rata-rata elemen per ember melebihi

the loadFactor.

Saat itulah ukuran saat ini dibagi dengan bucket. Panjangnya adalah

lebih besar dari loadFactor.

Pada titik ini, jumlah rata-rata elemen per ember

adalah 4 dibagi dengan 6.

4 elemen, 6 ember, itu 0,67.

Itu kurang dari ambang yang saya tetapkan 0,75 jadi kita

baik.

Kami tidak perlu mengubah ukuran.

Tapi sekarang katakanlah kita tambahkan woodchuck.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

Woodchuck akan berakhir di ember nomor 3.

Pada titik ini, ukuran saat ini adalah 5.

Dan sekarang jumlah rata-rata elemen per ember

adalah currentSize dibagi dengan buckets.length.

Itu 5 elemen dibagi 6 ember adalah 0,83.

Dan ini melebihi loadFactor yang 0,75.

Untuk mengatasi masalah ini, untuk membuat

ember mungkin sedikit

lebih kosong sehingga operasi suka menentukan apakah a

ember berisi

sebuah elemen akan menjadi sedikit kurang kompleks, saya ingin mengubah ukuran

HashSet saya.

Mengubah ukuran HashSet membutuhkan dua langkah.

Pertama saya akan menggandakan jumlah ember, saya punya 6 ember,

sekarang saya akan memiliki 12 ember.

Perhatikan di sini bahwa loadFactor yang saya atur ke 0,75 tetap sama.

Tetapi jumlah ember berubah adalah 12,

jumlah elemen tetap sama, adalah 5.

5 dibagi 12 adalah sekitar 0,42, itu jauh di bawah kita

loadFactor,

jadi kami baik-baik saja sekarang.

Tapi kami belum selesai karena beberapa elemen ini ada di

ember yang salah sekarang.

Misalnya, gajah.

Gajah berada di ember nomor 2 karena jumlahnya

karakter dalam gajah

adalah 8.

Kami memiliki 6 ember, 8 minus 6 adalah 2.

Itu sebabnya berakhir di nomor 2.

Tapi sekarang kita punya 12 ember, 8 mod 12 adalah 8, jadi

gajah tidak termasuk dalam ember nomor 2 lagi.

Gajah termasuk dalam ember nomor 8.

Bagaimana dengan woodchuck?

Woodchuck-lah yang memulai seluruh masalah ini.

Woodchuck berakhir di ember nomor 3.

Karena 9 mod 6 adalah 3.

Tapi sekarang kita lakukan 9 mod 12.

9 mod 12 adalah 9, woodchuck pergi ke bucket nomor 9.

Dan Anda melihat keuntungan dari semua ini.

Sekarang bucket nomor 3 hanya memiliki dua elemen sedangkan sebelumnya sudah 3.

Jadi, inilah kode kita,

di mana kami memiliki HashSet kami dengan rantai terpisah itu

tidak melakukan pengubahan ukuran.

Sekarang, inilah implementasi baru tempat kami menggunakan pengubahan ukuran.

Sebagian besar kode ini sama,

kita masih akan menentukan apakah itu mengandung

nilai sudah.

Jika tidak, maka kami akan mencari tahu mana embernya

harus masuk ke dan

lalu tambahkan ke ember itu, tambahkan ke LinkedList itu.

Tapi sekarang kita menambahkan bidang currentSize.

currentSize adalah bidang yang melacak nomor tersebut

elemen di HashSet kami.

Kita akan menambahnya dan kemudian kita akan melihat

pada beban rata-rata,

jumlah rata-rata elemen per ember.

Kami akan melakukan pembagian itu di sini.

Kita harus melakukan sedikit casting di sini untuk memastikan

bahwa kita mendapatkan dobel.

Dan kemudian, kami akan membandingkan beban rata-rata dengan bidang

yang saya tetapkan sebagai

0,75 ketika saya membuat HashSet ini, misalnya, yang

the loadFactor.

Jika beban rata-rata lebih besar dari pada loadFactor,

itu berarti ada terlalu banyak elemen per ember

rata-rata, dan saya harus memasukkan kembali.

Jadi inilah implementasi metode kami untuk memasukkan kembali

semua elemen.

Pertama, saya akan membuat variabel lokal yang disebut oldBuckets.

Yang mengacu pada ember saat mereka berdiri

sebelum saya mulai mengubah ukuran segalanya.

Catatan Saya belum membuat array baru dari daftar tertaut dulu.

Saya hanya mengganti nama ember sebagai oldBuckets.

Sekarang ingat ember adalah bidang di kelas kami, saya akan pergi

untuk sekarang membuat array baru

daftar tertaut tetapi ini akan memiliki elemen dua kali lebih banyak

seperti yang terjadi pertama kali.

Sekarang saya harus benar-benar melakukan pemasangan kembali,

Saya akan beralih melalui semua ember lama.

Setiap elemen di oldBuckets adalah LinkedList string

itu adalah ember.

Saya akan pergi melalui ember itu dan mendapatkan setiap elemen di dalamnya

ember.

Dan sekarang aku akan memasukkannya kembali ke dalam Keranjang baru.

Saya akan mendapatkan kode hash-nya.

Saya akan mencari tahu indeks mana itu.

Dan sekarang saya mendapatkan ember baru, LinkedList baru

string dan

Saya akan menambahkannya ke ember baru itu.

Jadi untuk rekap, HashSets seperti yang kita lihat adalah array dari Linked

Daftar, atau ember.

HashSet yang dapat mengubah ukuran dapat direalisasikan menggunakan beberapa rasio atau

Saya akan memilih ukuran tabel n * 1.5 atau n + (n >> 1), ini akan memberikan load factor .66666 ~ tanpa pembagian, yang lambat pada sebagian besar sistem, terutama pada sistem portabel di mana tidak ada pembagian dalam perangkat keras.