首页 > 程序开发 > 综合编程 > 其他综合 >

白话算法(6.4) 能让 Dictionary 比 Hashtable 慢 600 倍?&

2011-04-19

泛型 Dictionary 和 Hashtable 都是散列表的一种实现。只不过 Hashtable 使用的是双重散列法(开放寻址法的一种),而 Dictionary 使用的是除法散列法+链接法处理碰撞。知道了这一点,就可以写一个让 Dictionary 出丑的测试: view sour

泛型 Dictionary 和 Hashtable 都是散列表的一种实现。只不过 Hashtable 使用的是双重散列法(开放寻址法的一种),而 Dictionary 使用的是除法散列法+链接法处理碰撞。知道了这一点,就可以写一个让 Dictionary 出丑的测试:

view sourceprint?01 int SIZE = 10103;

02 IDictionary<int, int> dict = new Dictionary<int, int>(SIZE);

03 Hashtable h = new Hashtable(SIZE);

04

05 for (int i = 0; i < 10000; i++)

06 {

07 dict.Add(i*SIZE, i);

08 h.Add(i*SIZE, i);

09 }

10

11 Stopwatch t = new Stopwatch();

12

13 t.Reset();

14 t.Start();

15 // 为了让测试效果明显,重复10万次查询

16 for (int i = 0; i < 100000; i++)

17 {

18 dict.ContainsKey(SIZE);

19 }

20 t.Stop();

21 Console.WriteLine("Dictionary:" + t.Elapsed.TotalMilliseconds.ToString() + "毫秒");

22

23 t.Reset();

24 t.Start();

25 // 为了让测试效果明显,重复10万次查询

26 for (int i = 0; i < 100000; i++)

27 {

28 h.ContainsKey(SIZE);

29 }

30 t.Stop();

31 Console.WriteLine("Hashtable:" + t.Elapsed.TotalMilliseconds.ToString() + "毫秒");

测试结果:

\

怎么样,效果很惊人吧?当然,计算倍数并没有什么实际意义,只不过听起来很恐怖,比较容易吸引眼球罢了。而且,这个测试对 Dictionary 是不公平的,毕竟是我故意制造了一个让 Dictionary 产生1万次碰撞的输入。一般情况下,Dictionary 和 Hashtable 的效率是不相上下的,在 Key 是原生类型的情况下 Dictionary 还略快一些。不过,这个测试也说明开放寻址法自有其优点,毕竟我们难以制造一个能让 Hashtable 出这么大的丑的测试。
  上面那个测试让人心中不爽,但是在实际使用时一般不会有太大问题。当容量比较小时,使用除法散列法确实容易产生碰撞,但是就算达到极端的 O(n) 查找又如何——把百八十个项全部遍历一遍也用不了多少时间。当容量较大时,例如容量是 10103 时,要每隔 10103 个数字才发生一次碰撞,如果可以假设实际添加到字典中的项都是比较靠近的,就不会发生大量碰撞。
  在阅读 Dictionary 源代码之前,我们先来做个独立思考,如何把上一篇使用双重散列法实现的 HashSet4 改造成泛型字典?

HashSet4 到泛型字典

  泛型字典在功能上与 Hashtable 的不同之处主要有2点:1)它的 Key 和 Value 都是泛型的;2)遍历 Key 得到的序列与添加时的顺序一致。
  先看第一点:泛型。如果把 HashSet4 的 Key 的类型由 Object 改成泛型参数 TKey,就无法把 null 和 _bucket 赋值给 Key 了,这两个特殊的值分别表示槽是空槽和标记为删除的槽,所以要为 Bucket 增加一个状态属性,并修改 MarkDeleted() 和 IsEmputyOrDeleted() 函数:

view sourceprint?01 public class HashSet4<TKey>

02 {

03 [DebuggerDisplay("Key = {Key} k = {k} IsCollided = {IsCollided}")]

04 private struct Bucket

05 {

06 public TKey Key;

07 private int _k; // Store hash code; sign bit means there was a collision.

08 public BucketState State;

09 public int k

10 {

11 get { return _k & 0x7FFFFFFF; } // 返回去掉最高的碰撞位之后的 _k

12 set

13 {

14 _k &= unchecked((int)0x80000000); // 将 _k 除了最高的碰撞位之外的其它位全部设为0

15 _k |= value; // 保持 _k 的最高的碰撞位不变,将 value 的值放到 _k 的后面几位中去

16 }

17 }

18 // 是否发生过碰撞

19 public bool IsCollided

20 {

21 get { return (_k & unchecked((int)0x80000000)) != 0; } // _k 的最高位如果为1表示发生过碰撞

22 }

23 // 将槽标记为发生过碰撞

24 public void MarkCollided()

25 {

26 _k |= unchecked((int)0x80000000); // 将 _k 的最高位设为1

27 }

28

29 public void MarkDeleted()

30 {

31 State = BucketState.Deleted;

32 k = 0;

33 }

34

35 public bool IsEmputyOrDeleted()

36 {

37 return State == BucketState.Empty || State == BucketState.Deleted;

38 }

39 }

40 private enum BucketState

41 {

42 Empty = 0,

43 Full = 1,

44 Deleted = 2

45 }

46 // ...

47 }

Rehash()、Add()、Contains()、Remove() 也要做相应的修改:

show sourceview sourceprint?001 public class HashSet4<TKey>

002 {

003 // 将老数组中的项在大小为 newSize 的新数组中重新排列

004 private void Rehash(int newSize)

005 {

006 _occupancy = 0; // 将标记为碰撞的槽的数量重新设为0

007 Bucket[] newBuckets = new Bucket[newSize]; // 新数组

008 // 将老数组中的项添加到新数组中

009 for (int oldIndex = 0; oldIndex < _b

相关文章
最新文章
热点推荐