首页 > 代码库 > 链表与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检索实测
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。