首页 > 代码库 > 链表与Hash检索实测

链表与Hash检索实测

测试环境:

  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 = 2000000;
        static long FisrtLv = 500000;
        static long SecondLv = 1000000;
        static long ThirdLv = 1500000;

        static void Main(string[] args)
        {
            //链表测试资源准备
            var ObjectList = new List<TestObject>();
            for (int i = 0; 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 = 0; 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 = 0; i < FisrtLv; i++)
            {
                ObjectList[i].memberBigInt += 1;
            }
            var lastElapsedTime3 = stopWatch3.ElapsedMilliseconds;
            Console.WriteLine("Condition 3: {0} ms.", lastElapsedTime3);
            
            //写入2
            var stopWatch4 = Stopwatch.StartNew();
            for (int i = 0; i < FisrtLv; i++)
            {
                ObjectDictionary[Convert.ToString(i)].memberBigInt += 1;
            }
            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 实际上没有冷数据,这样随着运行时间的推移,效率会越来越低。

链表与Hash检索实测