Apakah sebab mengapa kapasiti awal ArrayList di Java ialah 10?

Mengapakah kapasiti awal HashMap 16?

Apabila bercakap tentang kapasiti permulaan ArrayList, kita mesti menyemak kapasiti permulaan HashMap terlebih dahulu. Berikut ialah kod sumber Java 8 sebagai contoh Terdapat dua faktor yang berkaitan dalam HashMap: kapasiti pemulaan dan faktor pemuatan:

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

Dalam HashMap, kapasiti permulaan lalai tatasusunan ialah 16. Apabila data diisi kepada kapasiti lalai 0.75 Apabila, ia akan dikembangkan sebanyak 2 kali. Sudah tentu, pengguna juga boleh memasukkan saiz yang ditentukan semasa permulaan. Tetapi perlu diingatkan bahawa lebih baik menggunakan nilai 2 kepada kuasa ke-n Jika ia tidak ditetapkan kepada kuasa ke-2, HashMap juga akan menukarnya, tetapi ia akan mengambil satu langkah lagi.

Mengenai prinsip pelaksanaan HashMap, saya tidak akan menerangkan secara terperinci di sini sudah terlalu banyak artikel di Internet tentang perkara ini. Satu perkara yang perlu kita ketahui ialah algoritma HashMap untuk mengira koordinat nilai utama, iaitu dengan mencincang nilai kunci dan kemudian memetakannya ke koordinat dalam tatasusunan.

Pada masa ini, pastikan kapasiti HashMap adalah 2 hingga kuasa ke-n Kemudian operasi bit boleh digunakan untuk mengendalikan memori secara terus semasa operasi cincang tanpa menukar kepada perpuluhan, dan kecekapan akan lebih tinggi.

Secara amnya, boleh dianggap bahawa sebab HashMap menggunakan kuasa 2 hingga ke-n dan nilai lalai ialah 16, mempunyai pertimbangan berikut:

• Kurangkan perlanggaran cincang;

• Tingkatkan kecekapan pertanyaan Peta; 🎜>

  Peruntukan yang berlebihan membazirkan sumber;

• Ringkasnya, sebab HashMap menggunakan 16 sebagai nilai lalai adalah untuk mengurangkan perlanggaran cincang dan meningkatkan kecekapan.
• Adakah kapasiti awal ArrayList 10?
  Seterusnya, mari kita sahkan dahulu sama ada kapasiti awal ArrayList ialah 10, dan kemudian bincangkan mengapa ia adalah nilai ini.

Mari kita lihat dahulu kod sumber kapasiti permulaan ArrayList dalam Java 8:

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

Jelas sekali, nilai permulaan kontena lalai ialah 10. Dan daripada JDK1.2 hingga JDK1.6, nilai ini sentiasa 10.

Bermula dari JDK1.7, apabila memulakan ArrayList, nilai lalai dimulakan kepada tatasusunan kosong:

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

Sesetengah rakan di sini mesti mengatakan bahawa nilai lalai bagi ArrayList dalam Java 8 Saiz awal ialah 0, bukan 10. Dan anda juga akan mendapati sesuatu yang pelik tentang komen pada kaedah pembina: bina senarai kosong dengan kapasiti awal 10. Apa kejadahnya? Ia jelas kosong!

Tempah keraguan, mari kita lihat kaedah tambah ArrayList dahulu:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

Kaedah ensureCapacityInternal dipanggil dalam kaedah tambah apabila memasukkan kaedah ini ialah bekas kosong pada mulanya, jadi

Masuk

:

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

Dalam kaedah di atas, kapasiti dikira terlebih dahulu dengan calculateCapacity:

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

akan mendapati bahawa

ditugaskan semula kepada 10 (size=0), Lulus minCapacity=1ini

,

Berikut ialah badan kaedah: minCapacityDEFAULT_CAPACITY=10

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

ensureExplicitCapacity(minCapacity);Kaedah tumbuh dalam kod di atas digunakan untuk mengendalikan pengembangan, dan kapasiti dikembangkan kepada 1.5 kali ganda daripada asal. minCapacity=10

Memahami aliran pemprosesan di atas, kami akan mendapati bahawa pada asasnya kapasiti awal ArrayList masih 10, tetapi ia hanya menggunakan pemuatan malas Ini adalah pengoptimuman yang dilakukan oleh Java 8 untuk menjimatkan memori. Oleh itu, dari awal hingga akhir, kapasiti awal ArrayList ialah 10.

Berikut ialah satu lagi sebutan tentang faedah pemuatan malas Apabila terdapat beribu-ribu ArrayLists dalam program, saiz lalai 10 objek bermakna 10 penunjuk (40 atau 80) diperuntukkan kepada tatasusunan asas apabila dibuat. . Jika anda dengan malas boleh memulakan tatasusunan, anda boleh menjimatkan banyak ruang memori. Perubahan dalam Java 8 adalah untuk tujuan di atas.

Mengapakah kapasiti awal ArrayList 10?

Akhir sekali, mari kita bincangkan mengapa kapasiti awal ArrayList ialah 10. Malah boleh dikatakan tiada sebab, cuma "terasa" sahaja, tidak terlalu besar, tidak terlalu kecil, sesuai untuk mata!

Pertama sekali, apabila membincangkan HashMap, kami mengatakan bahawa sebab mengapa HashMap memilih kuasa 2 hingga ke-n adalah lebih kepada mempertimbangkan prestasi dan perlanggaran algoritma cincang. Masalah ini tidak wujud untuk ArrayList. ArrayList hanyalah tatasusunan mudah berkembang, tanpa mengambil kira pengoptimuman peringkat algoritma. Selagi ia melebihi nilai tertentu, ia boleh berkembang. Oleh itu, secara teorinya, kapasiti ArrayList boleh menjadi sebarang nilai positif.

Dokumentasi ArrayList tidak menjelaskan mengapa 10 dipilih, tetapi kemungkinan besar disebabkan oleh pertimbangan padanan terbaik antara kehilangan prestasi dan kehilangan ruang. 10. Ia tidak terlalu besar atau terlalu kecil Ia tidak akan membazirkan terlalu banyak ruang memori dan tidak akan menjejaskan prestasi terlalu banyak.

Jika anda perlu bertanya mengapa 10 dipilih pada mulanya, anda mungkin perlu bertanya kepada pengarang kod ini "Josh Bloch".

Jika anda melihat dengan teliti, anda juga akan menemui beberapa nombor kapasiti permulaan menarik yang lain:

ArrayList-10
Vector-10
HashSet-16
HashMap-16
HashTable-11

ArrayList mempunyai kapasiti permulaan yang sama seperti Vector, iaitu 10; Kapasiti permulaan HashMap Sama, ia adalah 16; dan HashTable menggunakan 11 sahaja, yang merupakan satu lagi soalan yang sangat menarik.

Atas ialah kandungan terperinci Apakah sebab mengapa kapasiti awal ArrayList di Java ialah 10?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!