怎么理解List的扩容机制

发布时间：2021-11-02 11:40:18 阅读：172 作者：iii 栏目：编程语言

开发者测试专用服务器限时活动，0元免费领，库存有限，领完即止！点击查看>>

这篇文章主要讲解了“怎么理解List的扩容机制”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么理解List的扩容机制”吧！

一：背景

1. 讲故事

在前一篇大内存排查中，我们看到了Dictionary正在做扩容操作，当时这个字典的count=251w，你把字典玩的66飞起，其实都是底层为你负重前行，比如其中的扩容机制，当你遇到几百万甚至千万的大集合这个扩容机制还真的需要挖一下，免的入戏太深，难以自拔。

怎么理解List的扩容机制

为了方便讲述，我准备从List说起，因为它最简单哈

二：List扩容机制

1. 如何查看

要想看它的扩容机制，可以用ILSpy去看看List的源码即可，非常简单。

怎么理解List的扩容机制

从源码的 int num = (_items.Length == 0) ? 4 : (_items.Length * 2) 可以非常清楚的看到，4个空间起步，后面都是 *2 的扩容，也就说当你有 2^(n-1) + 1 个元素，实际上你需要占用 2^n个空间。

下面我用C#代码演示一下：

        static void Main(string[] args)        {            var list1 = Enumerable.Range(0, (int)Math.Pow(2, 22)).ToList();            var list2 = new List<int>(list1);            list2.Add(1);            Console.WriteLine($"list1.Capacity={list1.Capacity}");            Console.WriteLine($"list2.Capacity={list2.Capacity}");            Console.ReadLine();        } ------ output -------list1.Capacity=4194304list2.Capacity=8388608

从代码中可以看到，当List中已有 4194304个元素的时候，再往其中塞入一个元素，仅仅是多一个，在底层可是翻倍的空间占用哦，太可气了，要想往深处看可以用windbg看一下各自数组占用大小。

0:000> !DumpObj /d 000001ec037d2e20Name:        System.Collections.Generic.List`1[[System.Int32, mscorlib]]Fields:              MT    Field   Offset                 Type VT     Attr            Value Name00007ffde2ac8538  400189e        8       System.Int32[]  0 instance 000001ec147b9c10 _items00007ffde2ac85a0  400189f       18         System.Int32  1 instance          4194304 _size00007ffde2ac85a0  40018a0       1c         System.Int32  1 instance          4194304 _version00007ffde2ac5dd8  40018a1       10        System.Object  0 instance 0000000000000000 _syncRoot00007ffde2ac8538  40018a2        0       System.Int32[]  0   shared           static _emptyArray                                 >> Domain:Value dynamic statics NYI 000001ec01bc0920:NotInit  <<0:000> !do 000001ec147b9c10Name:        System.Int32[]MethodTable: 00007ffde2ac8538EEClass:     00007ffde2c35918Size:        16777240(0x1000018) bytesArray:       Rank 1, Number of elements 4194304, Type Int32 (Print Array)Fields:None
0:000> !do 000001ec037d2e78Name:        System.Collections.Generic.List`1[[System.Int32, mscorlib]]MethodTable: 00007ffde2ada068EEClass:     00007ffde2c3b008Size:        40(0x28) bytesFile:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dllFields:              MT    Field   Offset                 Type VT     Attr            Value Name00007ffde2ac8538  400189e        8       System.Int32[]  0 instance 000001ec167b9c80 _items00007ffde2ac85a0  400189f       18         System.Int32  1 instance          4194305 _size00007ffde2ac85a0  40018a0       1c         System.Int32  1 instance                1 _version00007ffde2ac5dd8  40018a1       10        System.Object  0 instance 0000000000000000 _syncRoot00007ffde2ac8538  40018a2        0       System.Int32[]  0   shared           static _emptyArray                                 >> Domain:Value dynamic statics NYI 000001ec01bc0920:NotInit  <<0:000> !do 000001ec167b9c80Name:        System.Int32[]MethodTable: 00007ffde2ac8538EEClass:     00007ffde2c35918Size:        33554456(0x2000018) bytesArray:       Rank 1, Number of elements 8388608, Type Int32 (Print Array)Fields:None

可以清楚的看到,一个int[] 占用 16777240 byte /1024/1024 =16M，一个 int[] 占用 33554456 byte/1024/1024 =32M,可这是翻倍的空间哈。

2. 真的以为是仅仅翻了一倍吗？

为什么我要这么说呢？仔细看看Capacity的Set实现，如下代码：

public int Capacity{	get{ return _items.Length; }	set	{		if (value > 0)		{			T[] array = new T[value];			if (_size > 0)			{				Array.Copy(_items, 0, array, 0, _size);			}			_items = array;		}	}}

大家仔细研读，这个流程是先定义好新size的数组array，然后将老的数组(_items) copy到新数组array中，然后将array的引用给了老的数组,不难看出真正的Size应该是 array(32M) + _items（16M） =48M 才是真正的大小，只要GC没有回收老的_items(16M)，那就一直保持48M的大小，你说呢？

要怎么验证呢? 大家可以用windbg去看看托管堆中 int[] 不就可以啦。

var list1 = Enumerable.Range(0, (int)Math.Pow(2, 22)).ToList();list1.Add(1);0:000> !DumpHeap -mt 00007ffde2ac8538  -min 102400         Address               MT     Size0000024c103e9ba0 00007ffde2ac8538  4194328     
0000024c107e9bd8 00007ffde2ac8538  8388632     
0000024c10fe9c10 00007ffde2ac8538 16777240     
0000024c11fe9c48 00007ffde2ac8538 33554456     
Statistics:              MT    Count    TotalSize Class Name00007ffde2ac8538        4     62914656 System.Int32[]Total 4 objects

从信息中看(16777240 + 33554456)byte = 48M，按照刚才的理论这个16777240的int[]应该是没有引用根的等待被GC回收，所以用!gcroot 把两个 int[] 都打印出来。

0:000> !gcroot 0000024c10fe9c10Found 0 unique roots (run '!GCRoot -all' to see all roots).0:000> !gcroot 0000024c11fe9c48Thread 63dc:    0000007b4abfee60 00007ffd85950938 ConsoleApp6.Program.Main(System.String[]) [C:\dream\Csharp\ConsoleApp1\ConsoleApp6\Program.cs @ 28]        rbp-38: 0000007b4abfee88            ->  0000024c00002da0 System.Collections.Generic.List`1[[System.Int32, mscorlib]]            ->  0000024c11fe9c48 System.Int32[]Found 1 unique roots (run '!GCRoot -all' to see all roots).

可以看到：0000024c10fe9c10 确实是没有引用根，也就验证了其实真正的是48M，而不是32M，翻了2倍哦。。。有点小恐怖。

二：如何压缩

1. 系统提供的压缩机制

回过头来看 Capacity 属性中的扩容机制，你只需要将Capacity设置与Count平齐，_items数组多余的虚占空间就给清掉了。

        static void Main(string[] args)        {            var list1 = Enumerable.Range(0, (int)Math.Pow(2, 22)).ToList();            list1.Add(1);            list1.Capacity = list1.Count;            Console.ReadLine();        }

怎么理解List的扩容机制

从图中可以看到，数组中的 8388608-4194305 =4194303 个int直接给灭掉了，优化了空间。

2. 自定义List

其实问题的根源出在了扩容机制，举个例子，如果当length大于400w的时候，默认情况下是翻倍成800w，有时候根据你的业务不需要翻到800w，其实500w就足够了，这样300w的虚占就可以免掉，所以必要的时候自己实现一个list，然后灵活控制它的扩容机制。

感谢各位的阅读，以上就是“怎么理解List的扩容机制”的内容了，经过本文的学习后，相信大家对怎么理解List的扩容机制这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>

向AI问一下细节

怎么理解List的扩容机制

猜你喜欢

最新资讯

相关推荐

开发者交流群：

相关标签