面试题：自定义C#泛型集合及性能优化

自定义C#泛型集合类实现

using System;

public class MyGenericCollection<T>
{
    private T[] items;
    private int count;

    public MyGenericCollection()
    {
        items = new T[4];
        count = 0;
    }

    // 添加元素
    public void Add(T item)
    {
        if (count == items.Length)
        {
            Array.Resize(ref items, items.Length * 2);
        }
        items[count] = item;
        count++;
    }

    // 删除元素
    public bool Remove(T item)
    {
        for (int i = 0; i < count; i++)
        {
            if (EqualityComparer<T>.Default.Equals(items[i], item))
            {
                count--;
                for (int j = i; j < count; j++)
                {
                    items[j] = items[j + 1];
                }
                if (count < items.Length / 4 && items.Length > 4)
                {
                    Array.Resize(ref items, items.Length / 2);
                }
                return true;
            }
        }
        return false;
    }

    // 查找元素
    public bool Contains(T item)
    {
        for (int i = 0; i < count; i++)
        {
            if (EqualityComparer<T>.Default.Equals(items[i], item))
            {
                return true;
            }
        }
        return false;
    }

    public int Count
    {
        get { return count; }
    }
}

性能瓶颈分析及优化

内存管理
- 瓶颈：每次添加元素时，如果当前数组已满，会进行数组扩容，即创建一个新的更大的数组并将原数组元素复制过去，这在大规模数据添加时会导致频繁的内存分配和复制操作，消耗性能。
- 优化：可以在初始化集合时根据预估的数据量设置合适的初始容量，减少扩容次数。另外，删除元素时，如果数组元素过少，可以进行适当的缩容操作，如上述代码中在元素过少时将数组大小减半，避免过多的内存浪费。
算法优化
- 瓶颈：删除元素时，采用的是线性查找并移动后续元素的方式，时间复杂度为O(n)，在集合元素较多时，删除操作性能较差。
- 优化：可以使用其他数据结构来辅助，如哈希表。在添加元素时，同时维护一个哈希表记录元素的位置，这样删除元素时通过哈希表能快速定位元素位置，时间复杂度降为O(1)。对于查找操作，同样可以利用哈希表优化，使得查找时间复杂度也变为O(1)。另外，在移动元素时，可以考虑使用更高效的内存复制算法，如Buffer.BlockCopy方法来提高移动效率。
其他优化
- 瓶颈：在Contains方法中，也是线性查找，对于大数据量性能不佳。
- 优化：除了上述使用哈希表优化查找外，若集合中的元素有序，可以使用二分查找法，将查找的时间复杂度从O(n)降为O(log n)。

星途面试题库

面试题：自定义C#泛型集合及性能优化

知识考点

面试题答案

自定义C#泛型集合类实现

性能瓶颈分析及优化