首页
登录 | 注册

ArrayList,HashMap,LinkedList 初始化大小和 扩容机制

前面写这篇文章的时候,看的是JDK1.6,然后就被下面的评论的人喷成了垃圾,是我没有说明清楚。

1.ArrayList

jdk1.6 的源码
/**
     * Constructs an empty list with the specified initial capacity.
     */
    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
    //初始化大小10
    this(10);
    }
/**
     * Increases the capacity of this <tt>ArrayList</tt> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param   minCapacity   the desired minimum capacity
     */
    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        //原始大小的1.5 + 1
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

ArrayList 初始化大小是 10 (如果你知道你的arrayList 会达到多少容量,可以在初始化的时候就指定,能节省扩容的性能开支)
扩容点规则是,新增的时候发现容量不够用了,就去扩容
扩容大小规则是,扩容后的大小= 原始大小+原始大小/2 + 1。(例如:原始大小是 10 ,扩容后的大小就是 10 + 5+1 = 16)

jdk1.7
/**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    ···省略
/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        super();
        //初始化大小0
        this.elementData = EMPTY_ELEMENTDATA;
    }
/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //直接是1.5 倍
        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);
    }

扩容大小规则是,扩容后的大小= 原始大小+原始大小/2 。(例如:原始大小是 10 ,扩容后的大小就是 10 + 5 = 15, 15+15/2 = 22, 22+22/2 = 33)

2.linkedList

linkedList 是一个双向链表,没有初始化大小,也没有扩容的机制,就是一直在前面或者后面新增就好。
对于双向链表的理解
ArrayList,HashMap,LinkedList  初始化大小和 扩容机制

3.HashMap

HashMap 初始化大小是 16 ,扩容因子默认0.75(可以指定初始化大小,和扩容因子)
扩容机制.(当前大小 和 当前容量 的比例超过了 扩容因子,就会扩容,扩容后大小为 一倍。例如:初始大小为 16 ,扩容因子 0.75 ,当容量为12的时候,比例已经是0.75 。触发扩容,扩容后的大小为 32.)



2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号