Apakah mekanisme pengembangan hashmap?

Mekanisme pengembangan peta cincang adalah untuk mengira semula kapasiti dan menggantikan tatasusunan asal dengan tatasusunan baharu. Kira semula semua data tatasusunan asal dan masukkan tatasusunan baharu, dan kemudian tuding ke tatasusunan baharu jika tatasusunan telah mencapai nilai maksimum sebelum pengembangan kapasiti, tetapkan ambang terus kepada integer maksimum dan kembalikannya.

Persekitaran pengendalian tutorial ini: sistem windows7, java8, komputer Dell G3.

Apakah itu ubah saiz?

Ubah saiz: Ia adalah untuk mengira semula kapasiti dan terus menambah elemen pada objek HashMap Apabila tatasusunan di dalam objek HashMap tidak dapat memuatkan lebih banyak elemen, objek itu perlu dibesarkan tatasusunan supaya lebih banyak elemen boleh ditampung. Sudah tentu, tatasusunan dalam Java tidak boleh dikembangkan secara automatik Kaedahnya ialah menggunakan tatasusunan baru untuk menggantikan tatasusunan yang sedia ada dengan kapasiti yang kecil Sama seperti kita menggunakan baldi kecil untuk menampung air, jika kita mahu memegang lebih banyak air, kita ada untuk menukar kepada baldi yang lebih besar.

Bilakah kapasiti akan diperluaskan?

Apabila menambah elemen pada bekas, bilangan elemen dalam bekas semasa akan ditentukan jika ia lebih besar daripada atau sama dengan ambang, iaitu bilangan elemen dalam bekas semasa lebih besar daripada panjang tatasusunan semasa Apabila didarab dengan nilai faktor pemuatan, ia akan berkembang secara automatik.

Prinsip pengembangan peta hash

Peluasan HashMap adalah untuk mengira semula kapasiti dan terus menambah elemen pada hashMap Apabila hashMap tidak dapat memuatkan elemen baharu, Objek perlu mengembangkan kapasiti tatasusunan untuk menampung lebih banyak elemen.

Ciri pengembangan kapasiti HashMap, lebih besar faktor pemuatan, lebih tinggi penggunaan ruang, lebih banyak elemen perlu diisi sebelum pengembangan, lebih cepat operasi put, tetapi senarai terpaut mudah dilalui Panjang, kebarangkalian perlanggaran cincang adalah tinggi, dan mendapatkan operasi adalah perlahan. Lebih kecil faktor pemuatan, lebih cepat mendapatkan operasi, lebih pendek senarai terpaut, dan lebih rendah kebarangkalian perlanggaran cincang. Walau bagaimanapun, penggunaan ruang adalah rendah. Terlalu banyak elemen put akan membawa kepada pengembangan yang kerap dan menjejaskan prestasi.

Prinsip pengembangan kapasiti HashMap: Kaedah Hashmap adalah untuk menggantikan tatasusunan asal dengan tatasusunan baharu, kira semula semua data dalam tatasusunan asal, masukkan tatasusunan baharu, dan kemudian tuding ke tatasusunan baharu; Jika tatasusunan telah mencapai maksimum sebelum pengembangan, ambang ditetapkan terus kepada integer maksimum dan dikembalikan.

Proses pengembangan

Berikut menggunakan kod sumber + gambar + penerangan teks untuk memperkenalkan proses pengembangan HashMap.

/** 
 * HashMap 添加节点 
 * 
 * @param hash        当前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后，数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢？  
        bucketIndex = indexFor(hash, table.length);//扩容之后，数组长度变了，在数组的下标跟数组长度有关，得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 这地方就是链表出现的地方，有2种情况 
 * 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦 
 * 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  
}

Dalam kaedah addEntry di atas, jika saiz (bilangan elemen dalam bekas semasa) lebih besar daripada atau sama dengan ambang (panjang tatasusunan didarab dengan faktor beban), dan koordinat baldiIndex tatasusunan asas tidak sama dengan null, maka Akan dikembangkan (ubah saiz) . Jika tidak, pengembangan tidak akan berlaku.

Perkara berikut akan menumpukan pada proses pengembangan:

        void resize(int newCapacity) {   //传入新的容量
            Entry[] oldTable = table;    //引用扩容前的Entry数组
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
                threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                return;
            }
     
            Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
            transfer(newTable);	此行有遗漏，勘误见下面引用	//！！将数据转移到新的Entry数组里
            table = newTable;                           //HashMap的table属性引用新的Entry数组
            threshold = (int) (newCapacity * loadFactor);此行有遗漏，勘误见下面引用//修改阈值
        }

Diperbetulkan oleh blogger wennie328: transfer(newTable); ==> pemindahan(newTable, initHashSeedAsNeeded(newCapacity));
ambang = (int) (newCapacity * loadFactor); ==> threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

Sebelum pengembangan, mula-mula dapatkan alamat rujukan tatasusunan sebelum pengembangan dan simpannya dalam pembolehubah Jadual lama, dan kemudian tentukan sama ada panjang tatasusunan sebelum pengembangan adalah Nilai maksimum yang disimpan dalam jenis int telah dicapai Jika ya, pengembangan akan diserahkan kerana kapasiti tatasusunan telah mencapai maksimum dan tidak boleh dikembangkan lagi.

Gambar di bawah menunjukkan keadaan selepas program melaksanakan Entry[] newTable = new Entry[newCapacity]; kapasiti yang lebih besar Tatasusunan digunakan untuk menggantikan tatasusunan sedia ada dengan kapasiti kecil Kaedah pemindahan() menyalin elemen tatasusunan Kemasukan asal kepada tatasusunan Kemasukan baharu.

Rujukan NewTable[i] diberikan kepada e.next, iaitu

menggunakan kaedah sisipan kepala senarai terpaut tunggal

dan elemen baharu pada kedudukan yang sama akan sentiasa diletakkan dalam senarai terpaut Kedudukan kepala dengan cara ini, elemen yang diletakkan pada indeks terlebih dahulu akhirnya akan diletakkan di penghujung rantaian Kemasukan (jika konflik cincang berlaku). Elemen dalam rantaian Kemasukan yang sama dalam tatasusunan lama boleh diletakkan pada kedudukan berbeza dalam tatasusunan baharu selepas mengira semula kedudukan indeks.

        void transfer(Entry[] newTable) {
            Entry[] src = table;                   //src引用了旧的Entry数组
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
                Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
                if (e != null) {
                    src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
                        e.next = newTable[i]; //标记[1]
                        newTable[i] = e;      //将元素放在数组上
                        e = next;             //访问下一个Entry链上的元素
                    } while (e != null);
                }
            }
        }

        static int indexFor(int h, int length) {
            return h & (length - 1);
        }

Proses pemindahan akan ditunjukkan di bawah dalam bentuk gambar (fon merah dalam gambar di bawah menunjukkan perbezaan dari gambar di atas. Gambar berikut adalah seperti ini, dan penerangan dalam fon merah tidak akan berulang)

Gambar di bawah menunjukkan keadaan selepas atur cara melaksanakan kod src[j] = null (ini ialah keadaan semasa gelung pertama):  

Mula-mula, tetapkan alamat rujukan tatasusunan jadual[] kepada tatasusunan src[].

Kemudian, Entri e = src[j]; Memandangkan senarai terpaut di src[j] telah diberikan kepada e untuk penyimpanan, anda boleh dengan berani menetapkan src[j]=null dan kemudian menunggu pengumpulan sampah.

Gambar di bawah menunjukkan keadaan selepas program melaksanakan Entri kod seterusnya (ini ialah keadaan semasa gelung pertama):

Di sini mula-mula sandarkan nilai e.sebelah pembolehubah seterusnya Kod seterusnya akan menukar penunjuk e.next, jadi nilai e.next disandarkan di sini.

Gambar berikut menunjukkan keadaan selepas atur cara melaksanakan kod e.next = newTable[i] (ini ialah keadaan semasa gelung pertama):

Oleh kerana nilai newTable[3] adalah nol, e.next adalah null, seperti yang ditunjukkan dalam rajah di atas.

Gambar di bawah menunjukkan keadaan selepas atur cara melaksanakan newTable[i] = e kod (ini ialah keadaan semasa gelung pertama):

Gambar di bawah menunjukkan keadaan selepas atur cara melaksanakan kod e = seterusnya (ini ialah keadaan semasa gelung pertama):

Seperti yang ditunjukkan di atas, Entry1 Nod ini berjaya dimasukkan ke dalam NewTable Pada akhir kitaran, kerana e!=null dinilai, proses di atas akan diulang sehingga semua nod dialihkan ke newTable.

Ringkasan

• Peluasan ialah operasi intensif prestasi, jadi apabila pengaturcara menggunakan HashMap, mereka perlu menganggarkan saiz peta dan memberikannya semasa pemulaan Nilai kasar untuk mengelakkan pengembangan peta yang kerap.
• Faktor beban boleh diubah suai dan boleh melebihi 1, tetapi disyorkan untuk tidak mengubah suai dengan mudah melainkan keadaannya sangat istimewa.
• HashMap adalah thread-unsafe. Jangan kendalikan HashMap pada masa yang sama dalam persekitaran serentak.
• JDK1.8 memperkenalkan pokok merah-hitam untuk mengoptimumkan prestasi HashMap dengan sangat baik.

Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Pengajaran Pengaturcaraan! !

Atas ialah kandungan terperinci Apakah mekanisme pengembangan hashmap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!