主题：【原创】说说.NET 3.5中的高性能害死集--HashSet -- Highway

几个月前，看到MSDN杂志上有一篇文章叫做《CLR Inside Out: New Library Classes in “Orcas”》，里面提到了.NET3.5中新增的一个类HashSet，当时就觉得很有意思，一直想探个究竟，但苦于没有时间。这两天Labor day休息，算是找了点时间，把这个问题把玩了一下。这里就跟大家聊聊。

首先先把这个HashSet解释一下。HashSet就是使用Hash技术实现的集合（Set）。集合是个很重要数据结构，不论是从逻辑上讲还是从实际编程上来说。使用Hash技术来实现集合操作也是最为普遍和常见的。这个Hash呢，国内好像翻译作“哈虚”，叫人看着就头晕。什么哈虚表，哈虚集的，望之比堆栈，链表什么的还要俨然。要是让我翻译，叫做“害死”肯能更亲和一些，发音也更接近，大家说是不是？

那么这个Set到底是干什么的呢？我们这里举个例子简单介绍一下。

比如说你来西西河灌水，第一件事就是要注册一个网名。这个网名首先不能和别人的重合。铁手可能用的是database query来检查重复性的问题，如果用程序语言来办的话，Set就是一个很好的数据结构。已有的网友放在一个Set里面，以后每有用户注册的话，就问一下这个Set （contains() 函数），看看有没有问题。没有重复并且认证通过以后这个新的ID就加入到网友集合中去（add()函数）。

如果有一天西西河和别的网站合并了（比如说把柚子网收购了），那么第一件事情就是清点网友。西西河3万，柚子网2万，结果呢，3万5。为什么不是5万呢？因为很多人两面注册，统计的时候不用算两次。这呢，就是取两个集合的合集（Superset）。合并后，铁手要选拔新的版主。可能最合适人选是两面都脸熟的网友。这时候呢，就要先看看两个网站的交集，看看哪些家伙是两边混的(Intersect)。

往简单里说，集合主要就是这么写操作。

说来你们可能不相信，就这么一个最常见最普遍的东西微软的.NET里居然没有。从1.0开始到现在将近7年了，这个缺就一直空着。直到.NET 3.5这个窟窿才算是有人给堵上。有些搞笑是不是？

更搞笑的是微软在填这个黑窟窿的时候，居然还堂而皇之的，美其名曰“高性能害死集（HashSet）”。大有王婆卖瓜的架势。

就我个人看来，Java的Collection比微软的.NET要好不止一点半点。感觉一个是有框架，有结构，深思熟虑后的东西；而另外一个有些拼拼凑凑，仓促上阵的杂牌军。有些朋友问我一些编程的建议，我总是把Java的Collections Framework放在显要位置。上Google一查，第一个蹦出来的就是老剑客Josh Bloch（巨牛级人物）的Java Collections Framework入门教程。外链出处。这个短篇高屋建瓴，深入浅出，绝对是大家手笔。把它学好了，绝对是收益非浅。Java发展到5.0以后，搞出了一个Concurrent package，给Collections Framework引入了不少新鲜血液。对于成天价在线程里讨营生的程序员来说，这些都是都是宝，都是好东东，

Java Collections Framework唯一的缺点就是对于新手来说，选择太多，有些眼晕，比如说吧，最简单的一个Map功能，到底是该使用那个具体实现呢（implementation）？抛开那些生僻的不说，最常见的就有好几个，比如说Hashtable, HashMap, WeakHashMap, TreeMap, ConcurrentHashMap, ConcurrentSkipListMap。如何更好的归纳整理一下，让新手和老枪都各得其所这可能是Java需要解决的一个小问题。

微软这边到没这个问题。不是老式的Hashtable，就是Generic的Dictionary<T, U>。没得挑反倒省心。自打2.0起，大家都捧Generics场，所以Dictionary几乎成了不二人选。事实上，Dictionary<T, U>倒也称职，一般的事情都能解决。如果需要排序的话，请SortedDictionary<T, U>出场也就够了。

Dictionary<T, U>不光可以解决Java里面所谓Map Interface里面定义的那些功能，稍加改动，Set功能也就实现了。事实上，Java的HashSet就是在HashMap上蒙了一层皮，你们要是看一些JDK里面的Source code，一眼就明白了。使用同样的手法，我们可以用三两分钟就创建出.NET的HashSet来。

譬如说

    class HashSet<T>
    {
        private static readonly Object DUMMY = new Object();

        private Dictionary<T, Object> map;

        public HashSet()
        {
            this.map = new Dictionary<T, object>();
        }

        public void Add(T obj)
        {
            if(!this.map.ContainsKey(obj))
            {
                this.map.Add(obj, DUMMY);
            }
        }

        public void Remove(T obj)
        {
            map.Remove(obj);
        }

        public bool Contains(T obj)
        {
            return this.map.ContainsKey(obj);
        }

        //此处略去308字...
}

就我所知，现在的.NET程序员们都是用这样的办法“对付着” 过的。可能微软觉得大家日子还能过，所以也就不急的想办法了。

Better later than never。不管怎么说，微软算是把这个Collections API的黑窟窿给堵上了。那我们现在就看看这个“高性能”是吹牛还是名归实致。

我写了段非常简单的程序，原理是随机产生一些东西（整数，String），然后将这些东西放到Set里面去，检验最常用的add操作。然后再产生另外一组东西，一个个的检查一下，看看Set里面是不是已经包含了（检验contains操作），最后再循环一次，把Set里面的东西一个个删除（检验remove操作。）

这里是测试结果。同样的程序我在Java 6.0, Java 7.0(测试版) ，以及.NET 3.5 Beta 2版本下进行测试。结果呢，.NET 3.5的HashSet还真是比Java快一些。其中整数测试大概快17%-29%，String测试快5%左右（有一组例外，Java要快）。

从这个角度讲，微软宣称的“高性能”倒也不完全是瞎吹。表现也还过得去。但为什么整数测试优势明显，而String测试差距就很小了呢？

选择整数和String我是有针对性的。在Java中，所有的Collection操作都是针对Object的，整数，浮点数这些Primitive类型是不可以的。即使从语法上你可以放一个整数到Set里面，但实际上Java是将这个整数先变成了Integer Object，然后才放到Set里面的。这里有个包装的开销（boxing）。

.NET的Generics是针对任何类型的。整数，浮点数这些Value type可以直接放到Set中去，不需要所谓的Boxing。就这一点而言，.NET是有绝对优势的。所以最后测试胜出，可能也就在于把Java boxing的开销省了。

大家不妨这样来理解，Hash一类的操作都是基于一个Object的Hash code来进行的。Java里面 int x = 5，double y = 3.8，这x, y哪里来的Hash code。变成Integer，Double对象以后呢，这些属性才有，所以哈虚才玩得转。相反，在.NET里面, int x= 5，这个x是一个Value Type，它的确是有Hash Code的（就是他本身），也提供GetHashCode()这么个函数让你把x的Hash Code拿出来。

String操作呢，两面都是Object，大家半斤八两。不过呢，.NET的Generics不需要类型转化（casting），虽然现在计算当中casting并不费时，但没有这个操作可能还是有一点点的优势的。可能由于这点节省，.NET最终比Java快了5%左右。

就测试的这些结果分析一下，我们可以大概得出这样一个结论，那就是.NET和Java在“哈虚”一端功力相若。虽然没有直接拼比HashMap和Dictionary，但我觉得两者也应该非常接近。由于.NET在Generics上的基础优势，所以在针对Primitive类型/value type操作上，由于节省了boxing/un-boxing的开销，所以性能上有一定的优势；在Object / Reference类型操作上，.NET也还是保持着一点点的优势，不过节省casting带来的优势远没有那么明显罢了。所以在我的测试中.NET赢了两阵，功劳可能还算不到Hash头上。

出于好奇，我把这个新的HashSet和我前面提到的用Dictionary包装生成的“自制”Set比试了一把，结果打了个难分难解，自制的土货甚至还有一点点的优势。这个就有些怪异了。敢情微软费了那么大的劲儿，全力推出的这么个HashSet和我几分钟就炮制的东西差不多呀？

有没有可能微软这个HashSet就是基于已有的那个Dictionary的啊？我觉得可能性不大。并且我反编译了这个两个类的程序，看着差异还是蛮大的，不象Java的HashMap和HashSet那么昭然若揭。

当然微软这个新的HashSet功能比较多，有一些挺方便的函数，比如IsSuperSetOf, IsSubsetOf, IntersectWith等等。但是我觉得这些功能并不复杂，用Dictionary也就是几句程序行的事情。不知道微软花了这么长的时间怎么就整出这个个东西来，有些匪夷所思。不过呢，我的测试只是闹着玩的，很多功能都没有测试，所以我不便于轻下结论。有兴趣的朋友可以沿着这条思路走下去，把这个问题搞搞清楚。

好了，就先灌到这里吧。