精华内容
下载资源
问答
  • HashMap初始容量

    2021-01-21 18:44:35
    HashMap默认初始容量:16 (即2<<3) 别问为什么,太大浪费内存,太小频繁扩容,16是一个在性能和资源之间相对折中的选择; 我们可以在new HashMap时显式指定容量大小 HashMap<String, Object> map = new...

    在已知HashMap中将要存放的KV个数的时候,设置一个合理的初始化容量可以有效的提高性能。

    HashMap默认初始容量:16 (即2<<3)

    别问为什么,太大浪费内存,太小频繁扩容,16是一个在性能和资源之间相对折中的选择;


    我们可以在new HashMap时显式指定容量大小

    HashMap<String, Object> map = new HashMap<>(10);
    

    但是!!
    但是!!
    但是!!

    事情没你想得那么简单

    你指定容量大小后,实际初始容量大小并不是你指定的容量大小,因为HashMap的发明者认为实际需要的容量大小往往大于你在new HashMap时预估的大小,所以HashMap底层会对你指定的大小进行处理,处理后的大小才是实际容量大小;

    底层容量处理

    Hash会选择大于该数字的第一个2的幂作为容量

    比如

    new HashMap<>(3),那么实际初始容量大小为4;
    new HashMap<>(5),那么实际初始容量大小为8;
    new HashMap<>(7),那么实际初始容量大小为8;
    new HashMap<>(10),那么实际初始容量大小为16;
    new HashMap<>(13),那么实际初始容量大小为32;

    这里多举一些例,方便大家理解


    最后说下如何设置最佳初始容量
    先记住一个公式expectedSize / 0.75 + 1

    简单说下为什么
    比如初始容量传7,经过jdk处理,初始容量会等于8,那么到8*0.75=6的时候就进行扩容,频繁进行扩容也会消耗性能;但如果我们传7/0.75+1=10,经过jdk处理后初始容量为16,这就大大减少了扩容的次数;


    ok我话讲完!!!

    展开全文
  • 浅析ArrayList集合的初始容量初始容量为0的两种扩容机制(1.8版本) 网络上对于ArrayList集合的空参构造是否为0,存在不同的的看法。对此,分析了源码,有以下见解: 1.空参构造,集合初始容量必定为0,添加一...

    深入理解ArrayList集合的初始容量和初始容量为0的两种扩容机制(1.8版本)

    网络上对于ArrayList集合的空参构造是否为0,存在不同的的看法。对此,分析了源码,有以下见解:
    1.空参构造,集合初始容量必定为0,添加一个元素,扩容为10。
    2.有参构造,参数为0和集合长度为0时,初始容量为0,添加一个元素扩容为1,再添加一个元素扩容为2,再添加一个元素扩容
    为3,再添加一个元素扩容为4,再添加一个元素扩容为6...
    
    • 版本不同
    • ArrayList的三种构造方法
    • ArrayList()的初始容量和扩容
    • ArrayList(int initialCapacity)的初始容量扩容
    • ArrayList(Collection( extends E) c)(尖括号显示不出来,用()代替)
    • ArrayList集合的扩容公式

    版本不同

    JAVA对于ArrayList集合进行了优化,目前所知,优化了空参构造的初始容量和扩容公式,至于是1.7还是1.8版本开始,
    就不清楚了。在1.6版本之时,该集合的空参构造的初始容量,确实是10,源码自己找。
    该文的源码以JDK1.8为主。
    

    ArrayList的三种构造方法

    public ArrayList(int initialCapacity)
    public ArrayList()
    public ArrayList(Collection<? extends E> c)
    

    public ArrayList()的初始容量和扩容

    首先,分析空参构造的初始容量。
    在1.8里面定义了三个Object[]:
    
    1.用于空实例的共享空数组实例。
    private static final Object[] EMPTY_ELEMENTDATA = {}
    
     2.用于默认大小的空实例的共享空数组实例。
       该数组与EMPTY_ELEMENTDATA区别,但都为空,以便知道当添加第一个元素时,该数组应该于何时扩容多少。
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
    

    而这两个数组,有什么关系呢?
    第一个数组运用于有参构造方法的参数为0或者集合长度为0的时候,而第二个数组运用于空参构造的时候。
    这两个数组一定要区别,对于以后的扩容造成影响。

        ArrayList的底层是由(transient Object[] elementData)实现的; 该数组是存储ArrayList元素的数组缓冲区。ArrayList的容量是这个数组缓冲区的长度。
        任何的elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空集合,当添加第一个元素时,将被扩展到DEFAULT_CAPACITY。
    
    • 初始容量
    	要知道空参构造的初始容量,要对空参构造的源码进行分析:
    	public ArrayList() {
            this.elementData =
            DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
        这样看空参构造,初始容量就是0。
    
    • 扩容机制
    那么当添加一个元素的时候,集合的容量会扩容到默认容量为10,也可能为大于10的值,视情况而定。一般默认一次只添加一个元素。
    private int newCapacity(int minCapacity) {
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity <= 0) {
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                    return Math.max(DEFAULT_CAPACITY, minCapacity);
                    //这里就定义了当
                    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组添加元素的情况,若是第一次添加:1.只添加一个元素,
                    //那么容量就扩容为DEFAULT_CAPACITY=10;2.要是添加的元素大于该默认容量,则以该元素个数为
                    //扩容后的容量。
                if (minCapacity < 0) // overflow
                    throw new OutOfMemoryError();
                return minCapacity;
            }
            return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity
                : hugeCapacity(minCapacity);
        }
    

    public ArrayList(int initialCapacity)的初始容量和扩容

    • 初始容量

    这里就讨论当参数为0的时候,该集合的初始容量也为0。

     public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
                //当该参数为0,底层数组为EMPTY_ELEMENTDATA,那么该数组的长度为0,集合初始容量则为0。
            } else {
                throw new IllegalArgumentException("Illegal    Capacity: "+initialCapacity);
            }
        }
    
    • 扩容机制
      加进一个元素,扩容为1。
      源码分析:
    //add源码  
    public boolean add(E e) {
            modCount++;
            add(e, elementData, size);//调用add(E e, Object[] elementData, int s)方法
            return true;
        } 
    //添加一个元素,调用此方法  
    private void add(E e, Object[] elementData, int s) {
            if (s == elementData.length)
                elementData = grow();// 数组长度为0,继续调用grow()方法
            elementData[s] = e;
            size = s + 1;
        }
    private Object[] grow() {
            return grow(size + 1);//grow()调用grow(1)
        }
    private Object[] grow(int minCapacity) {
            return elementData = Arrays.copyOf(elementData,
                                               newCapacity(minCapacity));
                                               //扩容方法newCapacity(minCapacity)
        }
        //扩容
    private int newCapacity(int minCapacity) {
            int oldCapacity = elementData.length;//oldCapacity=0
            int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity=0
            if (newCapacity - minCapacity <= 0) {
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                    return Math.max(DEFAULT_CAPACITY, minCapacity);
                    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA空参构造的数组;
                    //抱歉这是为了空参构造设计的,参数为0和集合长度为0对应的数组是EMPTY_ELEMENTDATA。
                if (minCapacity < 0) 
                    throw new OutOfMemoryError();
                return minCapacity;//上述条件都不符合,那么就返回1.
            }
            return (newCapacity - MAX_ARRAY_SIZE <= 0)
                ? newCapacity//当newCapacity - minCapacity > 0,且小于最大的数组长度,就返回原数组的1.5倍
                : hugeCapacity(minCapacity);
        }
    

    所以当添加一个元素进去时,该集合扩容为1。

    public ArrayList(Collection(? extends E) c)

    该构造方法与 ArrayList(int initialCapacity)方法有一样的地方:当参数集合长度为0时,该集合的初始容量也为0。

            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // defend against c.toArray (incorrectly) not returning Object[] 
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
         //当该集合为空时,同 ArrayList(int initialCapacity)方法的参数为0情况,集合的初始容量为0。
    

    扩容情况参照ArrayList(0)的情况,同样。

    ArrayList集合的扩容公式

    1.6版本的扩容公式: 数组原长度*3/2+1.
    1.6之后的扩容公式: oldCapacity + (oldCapacity >> 1)
    因为位运算快。

    之所以写此博文,是因为,看见一个拿着1.8版本的源码,睁眼说瞎话,说空参构造的初始容量为10,这简直就是害人。不平之下
    , 按照自己对于源码的见解,进行分析,望能帮助到需要之人。
    若有不足之处,望批评指正。
    
    展开全文
  • 为什么设置初始容量 初始容量多大合适 第一个问题:为什么设置初始容量 这个答案其实通过阅读源码也可以得到。简单来说就是避免扩容带来的效率问题。扩容机制具体详见源码。 在初始化 HashMap 的时候,应该尽量指定...

    Java集合HashMap初始容量与容量大小

    这是两个问题

    • 为什么设置初始容量
    • 初始容量多大合适

    第一个问题:为什么设置初始容量
    这个答案其实通过阅读源码也可以得到。简单来说就是避免扩容带来的效率问题。扩容机制具体详见源码。
    在初始化 HashMap 的时候,应该尽量指定其大小。尤其是当你已知 map 中存放的元素个数时。(《阿里巴巴 Java 开发规约》)

    第二个问题:初始容量多大合适
    那么,既然建议我们集合初始化的时候,要指定初始值大小,那么我们创建
    HashMap 的时候,到底指定多少合适呢?

    有些人会自然想到,我准备塞多少个元素我就设置成多少呗。比如我准备塞 7 个元素,那就 new HashMap(7)。但是,这么做不仅不对,而且以上方式创建出来的 Map 的容量也不是 7。因 为, 当 我 们 使 用 HashMap(int initialCapacity) 来 初 始 化 容 量 的 时 候,HashMap 并不会使用我们传进来的 initialCapacity 直接作为初识容量。JDK 会默认帮我们计算一个相对合理的值当做初始容量。所谓合理值,其实是找到第一个比用户传入的值大的 2 的幂。也就是说,当我们 new HashMap(7) 创建 HashMap 的时候,JDK 会通过计算,帮我们创建一个容量为 8 的 Map;当我们 new HashMap(9) 创建 HashMap 的时候,JDK 会通过计算,帮我们创建一个容量为 16 的 Map。但是,这个值看似合理,实际上并不尽然。因为 HashMap 在根据用户传入的capacity 计算得到的默认容量,并没有考虑到 loadFactor 这个因素,只是简单机械的计算出第一个大约这个数字的 2 的幂。

    loadFactor 是负载因子,当 HashMap 中的元素个数(size)超过 threshold
    = loadFactor * capacity 时,就会进行扩容。也就是说,如果我们设置的默认值是 7,经过 JDK 处理之后,HashMap 的容量会被设置成 8,但是,这个 HashMap 在元素个数达到 8*0.75 = 6 的时候就会进行一次扩容,这明显是我们不希望见到的。

    那么,到底设置成什么值比较合理呢?
    这里我们可以参考 JDK8 中 putAll 方法中的实现的,这个实现在 guava(21.0版本)也被采用。这个值的计算方法就是:

    return (int) ((float) expectedSize / 0.75F + 1.0F);

    比如我们计划向 HashMap 中放入 7 个元素的时候,我们通过 expectedSize /0.75F + 1.0F 计算,7/0.75 + 1 = 10 ,10 经过 JDK 处理之后,会被设置成 16,这就大大的减少了扩容的几率。
    当 HashMap 内 部 维 护 的 哈 希 表 的 容 量 达 到 75% 时(默 认 情 况 下), 会 触发 rehash, 而 rehash 的 过 程 是 比 较 耗 费 时 间 的。 所 以 初 始 化 容 量 要 设 置 成expectedSize/0.75 + 1 的话,可以有效的减少冲突也可以减小误差。所以,我们可以认为,当我们明确知道 HashMap 中元素的个数的时候,把默认容量设置成 expectedSize / 0.75F + 1.0F 是一个在性能上相对好的选择,但是,同时也会牺牲些内存。

    这个算法在 guava 中有实现,开发的时候,可以直接通过 Maps 类创建一个HashMap:
    Map<String, String> map = Maps.newHashMapWithExpectedSize(7);

    其代码实现如下:36  > Java 开发手册建议创建 HashMap 时设置初始化容量,但是多少合适呢?
    public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
    return new HashMap(capacity(expectedSize));
    }
    static int capacity(int expectedSize) {
    if (expectedSize < 3) {
    CollectPreconditions.checkNonnegative(expectedSize, “expectedSize”);
    return expectedSize + 1;
    } else {
    return expectedSize < 1073741824 ? (int)((float)expectedSize/0.75F+1.0F) : 2147483647;
    }
    }

    但是, 以上的操作是一种用内存换性能的做法,真正使用的时候,要考虑到内存的影响。但是,大多数情况下,我们还是认为内存是一种比较富裕的资源。但是话又说回来了,有些时候,我们到底要不要设置 HashMap 的初识值,这个值又设置成多少,真的有那么大影响吗?其实也不见得!可是,大的性能优化,不就是一个一个的优化细节堆叠出来的吗?再 不 济, 以 后 你 写 代 码 的 时 候, 使 用 Maps.newHashMapWithExpectedSize(7); 的写法,也可以让同事和老板眼前一亮。或者哪一天你碰到一个面试官问你一些细节的时候,你也能有个印象,或者某一天你也可以拿这个出去面试问其他人 ~ !啊哈哈哈

    展开全文
  • 这里如果有 list.add("jldsk"); 那么初始容量为10,如果没有添加这条语句,那么初始化容量为0;
    • 这里如果有 list.add("jldsk"); 那么初始容量为10,如果没有添加这条语句,那么初始化容量为0;
    展开全文
  • ArrayList的初始容量的问题

    千次阅读 2015-06-07 08:57:45
    ArrayList的初始容量的问题
  • HashMap初始容量设置问题 我们都知道HashMap的默认容量为16,但是: HashMap<Object, Object> objectObjectHashMap = new HashMap<>(13); //13为自定义的hashmap容量 为什么我们可以这样设置HashMap的...
  • ArrayList的初始容量以及扩容

    千次阅读 2018-12-21 09:11:51
    先看没有指定容量的ArrayList构造函数和相关代码: public ArrayList() { ... // 默认初始容量,这只是一个标记,在执行add方法的时候检测到这个标记会把初始值设为10 } public boolean add(E e) { ensureCapacit...
  • HashMap初始容量指定规则

    万次阅读 2020-06-25 16:20:59
    public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException { Map<String, Object> map = new HashMap<>(8); for (int i = 0;...
  • Java中的ArrayList的初始容量和容量分配List接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。ArrayList继承于List接口,除继承过来的方法外,还提供一些方法来操作内部用来存储...
  • HashMap的初始容量设置

    千次阅读 2019-06-13 14:23:00
    Java中HashMap的初始容量设置问题 阿里规约建议集合初始化时,指定初始化大小。 像HashMap,默认大小是16,也就是支持存储最多20个键值对。 如果不超过20个键值对,可以不设置,如果超出,按如下公式计算后设置: ...
  • 关于HashMap(JDK 1.8) 初始容量设置

    千次阅读 2019-05-09 21:58:58
    可以设置初始容量,可以不设置初始容量。如果map已有数据,然后执行putAll操作,那么在初始化map时指定初始容量。知道最终要put的数据总量,初始容量设置为 (int) ((float) expectedSize / 0.75F + 1.0F)。不知道...
  • ArrayList 的初始容量多少?

    千次阅读 2019-04-24 16:50:38
    List<Integer> list = new ArrayList<... list 的初始容量到底是多少 在 JDK 8 中 查看 ArrayList 源码 /** * Constructs an empty list with an initial capacity of ten. */ public ArrayList(...
  • HashMap有两个参数影响其性能:初始容量和加载因子。容量是哈希表中桶的数量,初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。当哈希表中的条目数超出了加载因子...
  • 向一个ArrayList集合里面存放一千万个int类型数据,当ArrayList初始容量为默认值时;需要3800多毫秒,初始容量为一万时,需要2300多毫秒,而当初始容量为十万时;需要3700多毫秒,时间增加了。(不同机器的时间可能...
  • List、 Set 和 Map 的初始容量和加载因子 答: List ArrayList 的初始容量是10,加载因子为0.5;扩容增量:原容量的 0.5倍+1;一次扩容后长度为16。 Vector 初始容量为10,加载因子1。扩容增量:原容量的1倍,一次...
  • StringBuffer类初始容量及扩容

    千次阅读 2018-03-30 16:02:51
    StringBuffer类可以创建可修改的...1.StringBuffer()的初始容量可以容纳16个字符,当该对象的实体存放的字符的长度大于16时,实体容量就自动增加。StringBuffer对象可以通过length()方法获取实体中存放的字符序列长...
  • jdk1.8中 ArrayList 底层数组的初始容量

    千次阅读 2018-03-19 20:40:48
    网上绝大多数的说法都是,当新建一个无参数的ArrayList时,数组的初始容量为10,然后每次容量不够时扩充为原先的1.5倍。我认为这种说法不够准确。关于new ArrayList() 的初始容量,在jdk1.6中的确是为10,然而在1.8...
  • 为什么HashMap的初始容量是16

    千次阅读 2019-02-18 16:40:43
    为什么HashMap的初始容量是16? https://blog.csdn.net/qq_35583089/article/details/80048285 一 ,到底什么是hash呢? 作者:知乎用户 链接:https://www.zhihu.com/question/26762707/answer/40119521 来源:...
  • 关于ArrayList的初始容量以及扩容的效率问题
  • 接着上一篇博客,上一篇博客说明了HashMap的初始容量都是2的n次幂的形式存在的,而扩容也是2倍的原来的容量进行扩容,也就是扩容后的容量也是2的n次幂的形式存在的,下面就来说明一下为什么是2的n次幂的形式!...
  • 一直记得ArrayList的初始容量大小是10,今天再次看ArrayList的源码(版本:Jdk 7u80)时发现在构造函数的注释上写着初始化容量是10,但是构造函数中却没有指定初始容量,仅仅初始化了一个空的数组。应该是不知道在...
  • ArrayList是Java中比较常用的一个类,它是基于数组实现,非线程安全,可快速随机访问List中的元素。 ArrayList具有动态扩容的机制,每次在添加元素时,...JDK1.8中,ArrayList的初始容量为0,第一次添加元素时,...
  • 一、Java中的ArrayList的初始容量和扩容 ArrayList是经常会被用到的,一般情况下,使用的时候会像这样进行声明: List arrayList = new ArrayList(); 如果像上面这样使用默认的构造方法,初始容量被设置为10。当Arra...
  • 这里要讨论这些常用的默认初始容量和扩容的原因是: 当底层实现涉及到扩容时,容器或重新分配一段更大的连续内存(如果是离散分配则不需要重新分配,离散分配都是插入新元素时动态分配内存),要将容器原来的数据...
  • Java容器类默认初始容量研究

    千次阅读 2016-04-28 17:50:20
    昨天参加了个公司的Java Performance的培训,其间提到了一些容器类的构造函数有默认的参数,用来控制容器的初始容量,建议是尽可能准确地预测容量需求,根据需求创建指定大小的容器,而不是使用默认的容量,这样可以...
  • 初始容量 倒是好理解,顾名思义,初始容量只是哈希表在创建时的容量,那么** 加载因子** 到底是表示什么意思呢? 如果按术语来讲: 加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。如果当哈希表中的...
  • Java和guava关于hashmap在初始化的时候最好给个初始容量,避免扩容引起性能问题的探究。 标签: hashmap初始化设定大小的误区 2016-09-01 16:52 207人阅读 评论(0) 收藏 举报  分类: java ...
  • 欲取鸣琴弹,恨无知音赏。—孟浩然《夏日南亭怀辛大》 ... 初始容量 负载因子 扩容增量 ArrayList 10 1 1倍 Vector 10 1 1.5倍 HashSet 16 0.75 1 倍 HashMap 16 0.75 1 倍 ...
  • 浅谈StringBuffer类初始容量及扩容

    万次阅读 2016-06-24 20:54:32
    StringBuffer类可以创建可修改的字符串...1.StringBuffer()的初始容量可以容纳16个字符,当该对象的实体存放的字符的长度大于16时,实体容量就自动增加。StringBuffer对象可以通过length()方法获取实体中存放的字符序

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 313,215
精华内容 125,286
关键字:

初始容量