526互联

C#中的List<T>和Dictionary<TKey, TValue>的底层原理

发布时间 2024-01-12 11:08:54作者: Jason_c

List<T>和Dictionary<TKey, TValue>本质上上是顺序表，用数组来存储数据，在添加和删除数据时，如果需要调整数组长度，则需要进行数组拷贝。

也可以理解成就是对数组的一种扩展，从而使开发者更方便的调用添加、删除、插入等操作。

所以，优化的思路是，对于大概知道元素的数量时，在实例化时应使用public List(int capacity){}构造函数，来比较在添加元素时，频繁进行数组拷贝，

那么问题来了，既然知道了元素数量，为什么不直接用数组，呜呜呜...

下面是扒的List<T>的部分源码，可见一斑：

List<T>的数据存储在_items里

        private T[] _items;

        private int _size;

List<T>的Add方法：

        public void Add(T item)
        {
            if (_size == _items.Length)
            {
                EnsureCapacity(_size + 1);
            }

            _items[_size++] = item;
            _version++;
        }

很明显，当数组长度小于数据长度时，则调用EnsureCapacity()方法，我们来看看EnsureCapacity干了个啥

        private void EnsureCapacity(int min)
        {
            if (_items.Length < min)
            {
                int num = (_items.Length == 0) ? 4 : (_items.Length * 2);
                if ((uint)num > 2146435071u)
                {
                    num = 2146435071;
                }

                if (num < min)
                {
                    num = min;
                }

                Capacity = num;
            }
        }

看到这，你可能也有疑问，也没看到有数组拷贝呀，别着急，接着往下看

        public int Capacity
        {
            [__DynamicallyInvokable]
            get
            {
                return _items.Length;
            }
            [__DynamicallyInvokable]
            set
            {
                if (value < _size)
                {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
                }

                if (value == _items.Length)
                {
                    return;
                }

                if (value > 0)
                {
                    T[] array = new T[value];
                    if (_size > 0)
                    {
                        Array.Copy(_items, 0, array, 0, _size);
                    }

                    _items = array;
                }
                else
                {
                    _items = _emptyArray;
                }
            }
        }

看到这明白了吧，在Capacity赋值的时候，创建了一个新的数组，然后将旧数组拷贝到新的数组里。

Dictionary<TKey, TValue>的原理也差不多，数据存储在private Entry[] entries;字段里。

Entry是个结构体，存储着Key,Value

        private struct Entry
        {
            public int hashCode;

            public int next;

            public TKey key;

            public TValue value;
        }

感兴趣的同学可以自己扒下源码看看，了解了底层逻辑，不但能帮忙你写出更高质量的代码，同时也是一件很有意思的事（相同事装b的又一神器，哈哈哈），

而且有兴趣的话，你也可以照猫画虎，写出List<T,T>,Dictionary<TKey,TKey, TValue>，在遇到要存储多个数据，或者根据多个数据查找某个值时，可以考虑它，而不用将多个数据封装到一个类里