链表与Hash检索实测

时间：2021-02-25 14:45:28

测试环境：

　　Win7 SP1、8G内存、3.4GHz 4核

测试代码：

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Reflection;

using System.Diagnostics;

namespace FactoryMode

{

    public class TestObject

    {

        public string memberString { get; set; }

        public long memberBigInt { get; set; }

    }

    [Serializable]

    public class Program : MarshalByRefObject

    {

        static long TotalCount = ;

        static long FisrtLv = ;

        static long SecondLv = ;

        static long ThirdLv = ;

        static void Main(string[] args)

        {

            //链表测试资源准备

            var ObjectList = new List<TestObject>();

            for (int i = ; i < TotalCount; i++)

            {

                var newTestObject = new TestObject();

                newTestObject.memberString = i.ToString();

                newTestObject.memberBigInt = i;

                ObjectList.Add(newTestObject);

            }

            //查找1

            var stopWatch1 = Stopwatch.StartNew();

            var result1 = ObjectList.Find(p => p.memberBigInt == SecondLv);

            var lastElapsedTime1 = stopWatch1.ElapsedMilliseconds;

            Console.WriteLine("Condition 1: {0} ms.", lastElapsedTime1);

            Console.WriteLine("result1: {0}.", result1.memberString);

            //字典测试资源准备

            var ObjectDictionary = new Dictionary<string, TestObject>();

            for (int i = ; i < TotalCount; i++)

            {

                var newTestObject = new TestObject();

                newTestObject.memberString = i.ToString();

                newTestObject.memberBigInt = i;

                ObjectDictionary.Add(newTestObject.memberString, newTestObject);

            }

            //查找2

            var stopWatch2 = Stopwatch.StartNew();

            var result2 = ObjectDictionary[Convert.ToString(ThirdLv)];

            var lastElapsedTime2 = stopWatch2.ElapsedMilliseconds;

            Console.WriteLine("Condition 2: {0} ms.", lastElapsedTime2);

            Console.WriteLine("result2: {0}.", result2.memberString);

            Console.Read();

        }

    }

}

测试结果：

　　链表检索：每50w 12ms；

　　Hash检索：0ms；

测试代码2：

            //写入1

            var stopWatch3 = Stopwatch.StartNew();

            for (int i = ; i < FisrtLv; i++)

            {

                ObjectList[i].memberBigInt += ;

            }

            var lastElapsedTime3 = stopWatch3.ElapsedMilliseconds;

            Console.WriteLine("Condition 3: {0} ms.", lastElapsedTime3);

            //写入2

            var stopWatch4 = Stopwatch.StartNew();

            for (int i = ; i < FisrtLv; i++)

            {

                ObjectDictionary[Convert.ToString(i)].memberBigInt += ;

            }

            var lastElapsedTime4 = stopWatch4.ElapsedMilliseconds;

            Console.WriteLine("Condition 4: {0} ms.", lastElapsedTime4);

测试结果2：

　　链表写入：12ms；

　　Hash写入：143ms；（根据散列函数得到了新的存储位置，数据转移开销）

技术参考：http://blog.sina.com.cn/s/blog_7880b6e30100xi94.html。

注意点：

　　虽然Hash具有O(1)的数据检索效率，但它空间开销却通常很大，是以空间换取时间，所以Hashtable适用于读取操作频繁，写入操作很少的操作类型。

引申思考：

　　在实际的应用中，应避免将所有的常用、不常用的数据都放在同一个数据结构中，无论是使用自定义的内存结构或者是redis，都应该定时将过期数据放入二级缓存，为一级缓存瘦身。

　　在游戏服务器应用中，一个服务器应将数据分为内存数据、冷备数据，登陆时将冷备数据加载至内存（登陆较慢可容忍），单服热数据容量一般不会超过5w级别，数据结构的性能可接受。

　　在之前一个http短连接项目的应用中，每次协议都直接从redis读取数据，处理完毕之后写入redis，但是 redis 实际上没有冷数据，这样随着运行时间的推移，效率会越来越低。

相关文章