HashSet与List泛型之间的性能比较

搜索了一些文章，但谁也没有举出实例来证明HasSet和List之间谁的查询性能更好。自己动手证明一下

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using TimeControler;

namespace HashSetPerformance
{
    class Program
    {
        static void Main(string[] args)
        {
            //设置最大值 以及查询数字
            int maxNum = 9999999;
            int serchNum = 9999993;
            Console.WriteLine("maxNum:"+maxNum);
            Console.WriteLine("searchNum"+serchNum);

            //得到数据集
            HashSet<int> hashSet = GetHashSet(maxNum);
            List<int> list = GetList(maxNum);

            //分别计算所需时间
            TimeControl.Start();
            hashSet.Contains(serchNum);
            TimeControl.Stop();
            Console.WriteLine("HashSet:"+TimeControl.GetMilliseconds());

            TimeControl.Start();
            list.Contains(serchNum);
            TimeControl.Stop();
            Console.WriteLine("List:"+TimeControl.GetMilliseconds());
            Console.ReadLine();
        }

        private static HashSet<int> GetHashSet(int maxNum)
        {
            HashSet<int> hashSet = new HashSet<int>();
            for (int i = 0; i < maxNum; i++)
            {
                hashSet.Add(i);
            }
            return hashSet;
        }

        private static List<int> GetList(int maxNum)
        {
            List<int> list = new List<int>();
            for (int i = 0; i < maxNum; i++)
            {
                list.Add(i);
            }
            return list;
        }
    }
}

CASE 0: serchNum = 2777661 CASE 1: serchNum = 12345 CASE 2: serchNum = 9999993 —————————————————————————————- 上述数据说明，无序链表查询上相对List是比较稳定的，查阅一下List的源码

// Contains returns true if the specified element is in the List.
// It does a linear, O(n) search.  Equality is determined by calling 
// item.Equals(). 
//
public bool Contains(T item) { 
    if ((Object) item == null) {
        for(int i=0; i<_size; i++)
            if ((Object) _items[i] == null)
                return true; 
        return false;
    } 
    else { 
        EqualityComparer<T> c = EqualityComparer<T>.Default;
        for(int i=0; i<_size; i++) { 
            if (c.Equals(_items[i], item)) return true;
        }
        return false;
    } 
}

for(int i=0; i<_size; i++) { 
            if (c.Equals(_items[i], item)) return true;
        }

这段代码说明其内部依旧是按照索引顺序遍历全部元素 —————————————————————————————- 虽然HashSet并不存在键值之间的对应关系，但HashSet依旧遵循Hash算法，且在其内部也会产生HashCode。

/// <summary>
/// Checks if this hashset contains the item 
/// </summary>
/// <param name="item">item to check for containment</param> 
/// <returns>true if item contained; false if not</returns> 
public bool Contains(T item) {
    if (m_buckets != null) { 
        int hashCode = InternalGetHashCode(item);
        // see note at "HashSet" level describing why "- 1" appears in for loop
        for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
            if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) { 
                return true;
            } 
        } 
    }
    // either m_buckets is null or wasn't found 
    return false;
}

能看源码就是爽啊。。。