HashSet与列表性能

Question

HashSet与列表性能很明显，泛型的搜索性能HashSet<T>类高于泛型类。List<T>班级，等级。只需将基于散列的密钥与List<T>班级，等级。然而，计算散列键本身可能需要一些cpu周期，因此对于少量项，线性搜索可以真正替代HashSet<T>.我的问题是：盈亏平衡在哪里？为了简化场景(为了公平起见)，让我们假设List<T>类使用元素的Equals()方法标识项。

Answer 1

很多人都说，一旦你达到了速度的大小，你就会担心HashSet<T>将永远击败List<T>但这取决于你在做什么。

假设你有一个List<T>平均只有5件物品在里面。在大量的循环中，如果每个周期都添加或删除单个项，则最好使用List<T>.

我在我的机器上做了一个测试，而且，它必须非常小才能从我的机器中获得优势。List<T>..对于短字符串列表，优势在5之后消失，对象在20之后消失。

1 item LIST strs time: 617ms1 item HASHSET strs time: 1332ms2 item LIST strs time: 781ms2 item HASHSET strs time: 1354ms3 item LIST strs time
: 950ms3 item HASHSET strs time: 1405ms4 item LIST strs time: 1126ms4 item HASHSET strs time: 1441ms5 item LIST strs time: 1370ms5 item H
ASHSET strs time: 1452ms6 item LIST strs time: 1481ms6 item HASHSET strs time: 1418ms7 item LIST strs time: 1581ms7 item HASHSET strs time: 
1464ms8 item LIST strs time: 1726ms8 item HASHSET strs time: 1398ms9 item LIST strs time: 1901ms9 item HASHSET strs time: 1433ms1 item LIST
 objs time: 614ms1 item HASHSET objs time: 1993ms4 item LIST objs time: 837ms4 item HASHSET objs time: 1914ms7 item LIST objs time: 1070ms7 i
 tem HASHSET objs time: 1900ms10 item LIST objs time: 1267ms10 item HASHSET objs time: 1904ms13 item LIST objs time: 1494ms13 item HASHSET ob
 js time: 1893ms16 item LIST objs time: 1695ms16 item HASHSET objs time: 1879ms19 item LIST objs time: 1902ms19 item HASHSET objs time: 195
 0ms22 item LIST objs time: 2136ms22 item HASHSET objs time: 1893ms25 item LIST objs time: 2357ms25 item HASHSET objs time: 1826ms28 item 
 LIST objs time: 2555ms28 item HASHSET objs time: 1865ms31 item LIST objs time: 2755ms31 item HASHSET objs time: 1963ms34 item LIST objs 
 time: 3025ms34 item HASHSET objs time: 1874ms37 item LIST objs time: 3195ms37 item HASHSET objs time: 1958ms40 item LIST objs time: 3401ms4
 0 item HASHSET objs time: 1855ms43 item LIST objs time: 3618ms43 item HASHSET objs time: 1869ms46 item LIST objs time: 3883ms46 item HASHS
 ET objs time: 2046ms49 item LIST objs time: 4218ms49 item HASHSET objs time: 1873ms

下面是代码：

static void Main(string[] args){
    int times = 10000000;


    for (int listSize = 1; listSize < 10; listSize++)
    {
        List<string> list = new List<string>();
        HashSet<string> hashset = new HashSet<string>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add("string" + i.ToString());
            hashset.Add("string" + i.ToString());
        }

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove("string0");
            list.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");


        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove("string0");
            hashset.Add("string0");
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET strs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }


    for (int listSize = 1; listSize < 50; listSize+=3)
    {
        List<object> list = new List<object>();
        HashSet<object> hashset = new HashSet<object>();

        for (int i = 0; i < listSize; i++)
        {
            list.Add(new object());
            hashset.Add(new object());
        }

        object objToAddRem = list[0];

        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            list.Remove(objToAddRem);
            list.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item LIST objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");



        timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i < times; i++)
        {
            hashset.Remove(objToAddRem);
            hashset.Add(objToAddRem);
        }
        timer.Stop();
        Console.WriteLine(listSize.ToString() + " item HASHSET objs time: " + timer.ElapsedMilliseconds.ToString() + "ms");
        Console.WriteLine();
    }

    Console.ReadLine();}

Answer 2

你看错了。是的，对列表的线性搜索会超过HashSet来获得少量的项。但是，性能差异通常对如此小的集合并不重要。通常你需要担心的是大量的收藏品，而这正是你需要担心的地方。从大O的角度思考..然而，如果您已经度量过HashSet性能的一个真正的瓶颈，那么您可以尝试创建一个混合List/HashSet，但是您将通过进行大量的经验性能测试来做到这一点-而不是对此提出问题。

Answer 3

  从本质上说，比较两种结构是毫无意义的。性能行为不同的人。使用传达意图的结构。即使你说List<T>不会有重复，迭代顺序也不重要，使其与HashSet<T>，使用它仍然是一个糟糕的选择。List<T>因为它的容错能力相对较低。

尽管如此，我会检查其他方面表现，

+------------+--------+-------------+-----------+----------+----------+-----------+

| Collection | Random | Containment | Insertion | Addition |  Removal | Memory    |

|            | access |             |           |          |          |           |

+------------+--------+-------------+-----------+----------+----------+-----------+

| List<T>    | O(1)   | O(n)        | O(n)      | O(1)*    | O(n)     | Lesser    |

| HashSet<T> | O(n)   | O(1)        | n/a       | O(1)     | O(1)     | Greater** |

+------------+--------+-------------+-----------+----------+----------+-----------+

* Even though addition is O(1) in both cases, it will be relatively slower in HashSet<T> since it involves cost of precomputing hash code before storing it.

** The superior scalability of HashSet<T> has a memory cost. Every entry is stored as a new object along with its hash code. This article might give you an idea.