牛人请进,HashTable算法研究

Question

C#实现HashTable类,能达到效率和.NET里面的HashTable一样,可用帖子 http://topic.csdn.net/u/20090823/21/032c6587-ff8a-4d97-858f-73b752b6ca22.html 来测试效率,其中要写的方法类似如下:
long begin = System.DateTime.Now.Ticks;            Hashtable hshTable = new Hashtable();            foreach (string item in input)
            {
                string sKey = item;
                if (!hshTable.Contains(sKey))
                    hshTable.Add(sKey, item);
            }            long end = System.DateTime.Now.Ticks;
            Console.WriteLine("Hashtable test: 总共" + hshTable.Count + "个数据" + "，做完需要" + (end - begin) / 10000 + "毫秒");看哪个牛人能比微软实现的效率还高,哈哈

Answer 1

HashTable
当把某个元素添加到 Hashtable 时，将根据键的哈希代码将该元素放入存储桶中。该键的后续查找将使用键的哈希代码只在一个特定存储桶中搜索，这将大大减少为查找一个元素所需的键比较的次数。
这种算法的速度是很快的，接近于 O(1)。但也牺牲了内存。想不到更快的。从原理上讲

Answer 2

不过你可以在Key上再做文章。搜索的速度取决去key的哈希算法。

Answer 3

不用反编译,
代码我己经贴出来了.
在原贴的第:
63楼/63楼.
(一个回贴放不下...)不该在HashTable函数上做文章,
应该在GetHashCode的自定义函数上想办法.
具体见:
http://topic.csdn.net/u/20090824/12/67d3acfd-a6e5-4ebe-8261-c16fd28a4d0d.html

Answer 4

以前我发过一套自制的数据结构库.
里面有个自制的dictionary.有兴趣你可以去看看.

Answer 5

我在这里不就说了，如果需要的话，在key的哈希算法上做文章

Answer 6

哈希算法是key类提供的,好像和hashtable没有关系呀

Answer 7

寒~ 我知道如何做 因为我做过数据库索引
简单说一下， string在内存中的结构可不是字符串 他是一组结构的2进制编码
如果你用utf-8来保存string 当你查找某一str是否在集合中 str也会被utf-8转2进制
然后2进制算0和1的个数 长度 然后对比已经存在的长度 01个数  最后（？）然后详细对比
微软的hashtable速度来说 已经第3次优化了 超级猛了
我这个速度基本赶上 当然了 我还有商业级算法 这里不能说了 抱歉

Answer 8

摘取msdn对于Dictionary的一段解释
//检索速度取决于为 TKey 指定的类型的哈希算法的质量。

Answer 9

Hashtable类的算法效率是很高的,我4年前做SP的时候,那时候需要过滤一些手机号码的黑名单,黑名单包括手机号码段,手机号码,我用Hashtable写的过滤程序,黑名单大慨有300多万,过滤500多万的号码,包括了从文件载入和过滤后写入文件,只用了近10秒的时间,减去载入和写入IO的时间,过滤只需不到1秒的时候,过滤手机号码是当手机号码在黑名单中过滤掉,如果号码在黑名单的号码段中也被过滤掉,如果当时不用Hashtable计算量是超大的,那时其他的同行是用数据库去过滤的,过滤这种数量的黑名单都要几个小时的时间