登录 立即注册
安币:

安卓巴士 - 安卓开发 - Android开发 - 安卓 - 移动互联网门户

查看: 271|回复: 0

Java中集合的扩容策略及实现

[复制链接]

3

主题

4

帖子

28

安币

初级码农

Rank: 1

发表于 2018-1-11 18:35:02 | 显示全部楼层 |阅读模式
如果对本篇文章感兴趣,请前往,原文地址:http://www.apkbus.com/blog-817034-76860.html

从这一篇开始,会陆续通过笔记来整理和记录之前看过的各种Java集合相关的知识点,主要包括List和Map。今天这一篇主要整理一下**集合扩容**相关的知识,涉及到的集合框架有:HashMap,ArrayMap,SparseArray,ArrayList,Vector。下面先从ArrayList开始。- **ArrayList**        ArrayList是以数组实现的一个集合类,在ArrayList的源码中可以看到,所有元素都是被储存在elementData这个全局的数组变量中,而所谓的扩容也是针对这个数组对象进行操作。具体来说,当一个添加元素的动作,即add或addAll被执行时,都会先调用ensureCapacityInternal(...)方法进行容量预检,如果当前elementData数组的容量不足以完成本次添加操作便会进行自动扩容。该方法代码如下:                ```                //这是一个私有方法,ArrayList提供了另一个public的扩容方法ensureCapacity以满足外界手动扩容的需求                //其实质也是调用了本方法,在此不做累述                //minCapacity是指本次添加操作后所需要的数组容量,即elementData.length   newSize                private void ensureCapacityInternal(int minCapacity) {                                //这个if判断如果成立,则代表当前ArrayList为空,而本次添加操作是第一次添加。                                //此时需要将ArrayList的容量扩充至DEFAULT_CAPACITY=10和本次添加操作所要求的minCapacity二者中的较大者。                        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);                        }                        ensureExplicitCapacity(minCapacity);            }            private void ensureExplicitCapacity(int minCapacity) {                //操作计数器 1                modCount  ;                // overflow-conscious code                // 确保需要进行扩容,即当前数组的容量小于本次添加操作所要求的新的总容量                if (minCapacity - elementData.length > 0)                    grow(minCapacity);            }        ```        在ensureCapacityInternal方法中,一开始会对本次添加操作是否为第一次添加进行判断。从源码:***private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};*** 中可以得知,DEFAULTCAPACITY_EMPTY_ELEMENTDATA变量指代的是一个空的对象数组,这也是通过无参构造函数new出来的ArrayList对象的初始状态,也即 elementData = {};这种情况下的第一次扩容,如果所要求的新容量小于10,则会直接扩容至10。                下面继续看到grow方法,这个方法是ArrayList扩容操作的实现                ```                private void grow(int minCapacity) {                // overflow-conscious code                //记录当前elementData数组的容量                int oldCapacity = elementData.length;                //新的容量暂定为当前容量的1.5倍                int newCapacity = oldCapacity   (oldCapacity >> 1);                //如果1.5倍容量仍不满足minCapacity所要求的,则直接将容量定为minCapacity                if (newCapacity - minCapacity < 0)                    newCapacity = minCapacity;                  //如果新的容量超过了Integer.MAX_VALUE - 8,则做最大化处理                if (newCapacity - MAX_ARRAY_SIZE > 0)                    newCapacity = hugeCapacity(minCapacity);                // minCapacity is usually close to size, so this is a win:                //将当前数组copy到新的数组中                elementData = Arrays.copyOf(elementData, newCapacity);            }            private static int hugeCapacity(int minCapacity) {                if (minCapacity < 0) // overflow                    throw new OutOfMemoryError();                return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;            }        ```         最后的扩容操作,Arrays.copyOf方法会新创建一个大小为newCapacity的数组,然后通过System.arraycopy方法将之前elementData数组中的元素复制到新数组中(起点的index为0),并将新数组返回给变量elementData完成扩容。- **Vector**        Vector和ArrayList其实身出同门,都是AbstractList的子类并且都实现了List接口,所提供的功能也基本相同,最大的不同在于Vector所有的公有API都是加锁的,也即Vector是线程安全的。但这也正是它不受欢迎的原因之一,太重了。。。言归正传,我们来关心一下Vector的扩容操作。其实基本跟ArrayList相同,方法如下:                ```                private void ensureCapacityHelper(int minCapacity) {                // overflow-conscious code                //当前容量不够,扩之                if (minCapacity - elementData.length > 0)                    grow(minCapacity);            }        ```        可以看到,基本只是方法名不一样而已,再来看看Vector的grow函数,这里还真有些不同:                ```                private void grow(int minCapacity) {                // overflow-conscious code                int oldCapacity = elementData.length;                                //不同之处在这里,MARK                int newCapacity = oldCapacity   ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);                                if (newCapacity - minCapacity < 0)                    newCapacity = minCapacity;               if (newCapacity - MAX_ARRAY_SIZE > 0)                    newCapacity = hugeCapacity(minCapacity);                elementData = Arrays.copyOf(elementData, newCapacity);            }        ```        上面代码块中MARK出的那一句便是不同之处,可以看出Vector的扩容是先判断有没有大于0的capacityIncrement,该变量是通过:                ```                public Vector(int initialCapacity, int capacityIncrement) {                super();                if (initialCapacity < 0)                    throw new IllegalArgumentException("Illegal Capacity: " initialCapacity);                this.elementData = new Object[initialCapacity];                this.capacityIncrement = capacityIncrement;            }        ```        这个带参构造函数传入的,如果不调用这个构造函数,则capacityIncrement为0。**在capacityIncrement不为0的情况下,则每次扩容都暂定扩大capacityIncrement个,反之扩容oldCapacity个,即当前容量的一倍。**后续的扩容操作和ArrayList一致,也是通过Arrays.copyOf方法来完成,这里不再重复分析。        - **HashMap**        下面来看另一个熟人--HashMap。不同于上面两个List的实现类,HashMap是一个采用哈希表实现的键值对集合,继承自AbstractMap,实现了Map接口并使用拉链法解决Hash冲突,其内部储存的元素并不是在连续内存地址的,并且是无序的。此处我们只关心其扩容操作的逻辑和实现,先说一下,由于要重新创建数组,rehash,重新分配元素位置等,HashMap扩容的开销要比List大很多。下面介绍几个和扩容相关的成员变量:                ```                //哈希表中的数组,JDK 1.8之前存放各个链表的表头。1.8中由于引入了红黑树,则也有可能存的是树的根                transient Node[] table;                        //默认初始容量:16,必须是2的整数次方。这样规定是因为在通过key来确定元素在table中的index时                //所用的算法为:index = (n - 1) & hash,其中n即为table容量。保证n是2的整数次方就能保证n-1的低位均为1,                //这样便能保留hash(key)得到的hash值的所有低位,从而保证得到的index在n范围内分布均匀,因为hash算法的结果就是均匀的                static final int DEFAULT_INITIAL_CAPACITY = 1 = MAXIMUM_CAPACITY) {                    //当前已经是最大容量,不允许再扩容,返回当前哈希表                threshold = Integer.MAX_VALUE;                return oldTab;            }            else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)                //先将oldCap翻倍,如果得到的值小于最大容量,并且oldCap不小于默认初始值,则将扩容阈值也翻倍,结束                newThr = oldThr  0)                 // initial capacity was placed in threshold                // 若构造函数中有传入initialCapacity,则会暂存在oldThr=threshold变量中。                // 然后在第一次put操作导致的resize方法中被赋给newCap,这样做的目的应该是避免污染oldCap从而影响上面那个if的判断                // 从这里也可以看出HashMap对于所需内存的申请是被延迟到第一次put操作时进行的,而非在构造函数中。            newCap = oldThr;        else {                               // zero initial threshold signifies using defaults                // Map没有被初始化,用默认值初始化            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        if (newThr == 0) {                //若经过计算后,新阈值为0,则赋值为新容量和扩容因子的乘积(需考虑边界条件)            float ft = (float)newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                      (int)ft : Integer.MAX_VALUE);        }        threshold = newThr;                /******-----分割线,至此新的容量和扩容因子已确定------*************/                @SuppressWarnings({"rawtypes","unchecked"})        //创建一个大小为newCap的Node数组,并赋值给table变量            Node[] newTab = (Node[])new Node[newCap];        table = newTab;        if (oldTab != null) {                //遍历扩容前的数组            for (int j = 0; j < oldCap;   j) {                Node e;                if ((e = oldTab[j]) != null) {                        //将原数组中第j个元素赋给e,并将原数组第j位置置空                    oldTab[j] = null;                    if (e.next == null)                            //该元素没有后续节点,即该位置未发生过hash冲突。则直接将该元素的hash值与新数组的长度取模得到新位置并放入                        newTab[e.hash & (newCap - 1)] = e;                    else if (e instanceof TreeNode)                            //JDK1.8中,如果该元素是一个树节点,说明该位置存放的是一颗红黑树,则需要对该树进行分解操作                            //具体实现后面会讨论,这里split的结果就是分为两棵树(这里必要时要进行非树化操作)并分别放在新数组的高段和低段                        ((TreeNode)e).split(this, newTab, j, oldCap);                    else { // preserve order                            //剩下这种情况就是该位置存放的是一个链表,需要说明的是在JDK1.7和1.8中这里有着不同的实现,下面分别讨论                                                        /******--- JDK 1.7版本 starts ---*******/                            //遍历链表                            while(null != e) {                                    //将原链表中e的下一个元素暂存到next变量中                                        HashMapEntry next = e.next;                                        //算出在新数组的index=i,indexFor其实就是e.hash & (newCapacity - 1)                                        int i = indexFor(e.hash, newCapacity);                                        //改变e.next的指向,将新数组该位置上原先的内容(一个链表,元素或是null)挂在e的身后,使e成为这个链表的表头                                        e.next = newTable;                                        //将这个e位表头的新链表放回到index为i的位置中                                        newTable = e;                                        //将之前暂存的原链表中的下一个元素赋给e,继续遍历原链表                                        e = next;                                    }                            /******--- JDK 1.7版本 ends ---*******/                                                        /******--- JDK 1.8版本 starts ---*******/                            //在1.8的实现中,新数组被分成了高低两个段,而原链表也会被分成两个子链表,分别放入新数组的高段和低段中                            //loHead和loTail用于生成将被放入新数组低段的子链表                        Node loHead = null, loTail = null;                        //hiHead和hiTail则用于生成将被放入新数组高段的子链表                        Node hiHead = null, hiTail = null;                        //跟1.7中一样,next用于暂存原链表中e的下一个元素                        Node next;                        //开始遍历原链表                        do {                            next = e.next;                            //用if中的方法确定e是该去新数组的高段还是低段                            if ((e.hash & oldCap) == 0) {                                    //将e加到将被放入低段的子链表的尾部                                if (loTail == null)                                    loHead = e;                                else                                    loTail.next = e;                                loTail = e;                            }                            else {                                    //将e加到将被放入高段的子链表的尾部                                if (hiTail == null)                                    hiHead = e;                                else                                    hiTail.next = e;                                hiTail = e;                            }                        } while ((e = next) != null);                                               if (loTail != null) {                                //将loHead指向的子链表放入新数组中index=j的位置                            loTail.next = null;                            newTab[j] = loHead;                        }                        if (hiTail != null) {                                ////将hiHead指向的子链表放入新数组中index=j oldCap的位置                            hiTail.next = null;                            newTab[j   oldCap] = hiHead;                        }                        /******--- JDK 1.8版本 ends ---*******/                    }                }            }        }        return newTab;    }        ```        可以看到JDK1.8对resize方法进行了彻底的改造,引入红黑树结合之前的链表势必会提高在发生hash冲突时的操作效率(红黑树能保证在最坏情况下插入,删除,查找的时间复杂度都为O(logN))。                此外最大的改动便是在扩容的时候对链表或树的处理,在1.7时代,链表中的每一个元素都会被重新计算在新数组中的index,具体方法仍旧是e.hash对新数组长度做取模操作;而在1.8时代,这个链表或树会被分为两部分,我们暂且称其为A和B,若元素的hash值按位与扩容前数组的长度得到的结果为0(其实就是判断hash的某一位是1还是0,由于hash值均匀分布的特性,这个分裂基本可以认为是均匀的),则将其接入A,反之接入B。最后保持A的位置不变,即在新数组中仍位于原先的index=j处,而B则去到j oldCap处。                **其实对于这个改动带来的好处我理解的不是特别透彻,因为整个过程并没有减少计算的次数。目前看到的好处是可以避免扩容重定向过程中发生哈希冲突(因为是扩容一倍,所以一个萝卜一个坑,不会有冲突),并且不会将链表中的元素倒置(考虑极端情况,就一条链表,1.7的方法每次都会将元素插到表头)。这里还是得求教大家,欢迎讨论~**                回到resize方法,上面还留了一个尾巴,就是当桶中是树形结构时的split方法,下面就来看源码:                ```                 /**         * Splits nodes in a tree bin into lower and upper tree bins,         * or untreeifies if now too small. Called only from resize;         * see above discussion about split bits and indices.         *         * @param map the map         * @param tab the table for recording bin heads         * @param index the index of the table being split         * @param bit the bit of hash to split on         */        final void split(HashMap map, Node[] tab, int index, int bit) {                TreeNode节点继承自LinkedHashMapEntry,在链表节点的基础上扩充了树节点的功能,譬如left,right,parent            TreeNode b = this;            // Relink into lo and hi lists, preserving order            // 将树分为两部分这里的做法和链表结构时是相似的            TreeNode loHead = null, loTail = null;            TreeNode hiHead = null, hiTail = null;            int lc = 0, hc = 0;            //遍历整棵树,这里说明一下,由于这棵树是由链表treeify生成的,其next指针依旧存在并指向之前链表中的后继节点,            //因此遍历时依然可以按照遍历链表的方式来进行            for (TreeNode e = b, next; e != null; e = next) {                    //暂存next                next = (TreeNode)e.next;                //将e从链表中切断                e.next = null;                //与对链表的处理相同,若e.hash按位与bit=oldCap结果为0,则接到低段组的尾部                if ((e.hash & bit) == 0) {                    if ((e.prev = loTail) == null)                        loHead = e;                    else                        loTail.next = e;                    loTail = e;                      lc;                }                //否则接到高段组的尾部                else {                    if ((e.prev = hiTail) == null)                        hiHead = e;                    else                        hiTail.next = e;                    hiTail = e;                      hc;                }            }                        //若低段不为空            if (loHead != null) {                    //如果低段子树的元素个数小于非树化阈值,则将该树进行非树化,还原为链表                if (lc 1))                    : (osize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);        ```        翻译一下就是先判断mSize值是否大于等于8,如果是则n=mSize*1.5,如果否,则判断是否大于等于4,是则n=8个,否则n=4个。                ```                private void allocArrays(final int size) {                if (mHashes == EMPTY_IMMUTABLE_INTS) {                    throw new UnsupportedOperationException("ArrayMap is immutable");                }                if (size == (BASE_SIZE*2)) {                        //线程安全,并且上的是类锁                    synchronized (ArrayMap.class) {                            //若要求的size是8,且大号缓存数组不为空,则从大号缓存数组中取缓存                        if (mTwiceBaseCache != null) {                                //将当前大号缓存数组赋给array,其容量为16,符合mArray的要求                            final Object[] array = mTwiceBaseCache;                            mArray = array;                            //index=0的位置存放的是指向下一个大号缓存数组的指针,取出赋给mTwiceBaseCache变量,即第一层缓存被mArray取走了                            mTwiceBaseCache = (Object[])array[0];                            //第一层缓存的index=1的位置存放的是长度为8的数组,赋给mHashes                            mHashes = (int[])array[1];                            //将已经取出的第一层缓存数组的前两位都清空,这样一来便得到了长度分别为16和8的空的mArray和mHashes数组,好精巧的设计!                            array[0] = array[1] = null;                            //大号缓存被取走了一层,链表长度减一                            mTwiceBaseCacheSize--;                            if (DEBUG) Log.d(TAG, "Retrieving 2x cache "   mHashes                                      " now have "   mTwiceBaseCacheSize   " entries");                            return;                        }                    }                } else if (size == BASE_SIZE) {                        //这边size=4,与上同理,只是操作的缓存对象变成了小号缓存数组                    synchronized (ArrayMap.class) {                        if (mBaseCache != null) {                            final Object[] array = mBaseCache;                            mArray = array;                            mBaseCache = (Object[])array[0];                            mHashes = (int[])array[1];                            array[0] = array[1] = null;                            mBaseCacheSize--;                            if (DEBUG) Log.d(TAG, "Retrieving 1x cache "   mHashes                                      " now have "   mBaseCacheSize   " entries");                            return;                        }                    }                }                        //如果要求的size不是4或8,则不满足使用缓存的条件,直接按照要求的size新创建两个数组                mHashes = new int[size];                mArray = new Object[size
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

站长推荐

通过邮件订阅最新安卓weekly信息
上一条 /4 下一条

下载安卓巴士客户端

全国最大的安卓开发者社区

广告投放| 下载客户端|申请友链|手机版|站点统计|安卓巴士 ( 粤ICP备15117877号 )

快速回复 返回顶部 返回列表