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

白话算法(6) 散列表(Hash Table) 从理论到实用(下)

2011-04-19

 【澈丹,我想要个钻戒。】【小北,等等吧,等我再修行两年,你把我烧了,舍利子比钻戒值钱。】                                ——自扯自蛋   无论开发一个程序还是谈一场恋爱,都差不多要经历这

 【澈丹,我想要个钻戒。】【小北,等等吧,等我再修行两年,你把我烧了,舍利子比钻戒值钱。】
                                ——自扯自蛋

  无论开发一个程序还是谈一场恋爱,都差不多要经历这么4个阶段:
  1)从零开始。没有束缚的轻松感。似乎拥有无限的可能性,也有相当多的不确定,兴奋、紧张和恐惧。
  2)从无到有。无从下手的感觉。一步一坎,进展缓慢。走弯路,犯错,投入很多产出很少。目标和现实之间产生强大的张力。疑惑、挫败、焦急和不甘心。
  3)渐入佳境。快速成长。创新,充实,满足。但是在解决问题的同时往往会不可避免地引入更多的问题和遗憾。
  4)接近成功。已经没有那么多的新鲜感和成就感,几乎是惯性般地努力前行。感觉成功在望,但又好像永远也不能100%搞定。有时,一心想要完成的欲望甚至超越了原本的目标。

  经过前面2篇,我们也来到了第4阶段。让我们深吸一口气,把遗留下来的这几个问题全部搞定吧。
  1)能不能支持所有的对象而不仅限于整数?
  2)如何支持所有整数而不只是正整数?
  3)被删除了的槽仍然占用查找时间。
  4)随着时间的推移,被标记为碰撞的槽越来越多,怎么办?
  5)必须在创建容器的时候指定大小,不能自动扩张。
  6)只是一个 HashSet,而不是HashTable。

  继续改造上一篇最后给出的 IntSet4。

支持所有对象而不仅限于整数

  要想支持所有对象而不只是整数,就需要一个能把各种类型的对象变换成整数的方法。这一点得到了 .net 特别的优待,Object 类的 GetHashCode() 就是专门干这个的。它提供的默认实现是:对于引用类型,每创建一个新对象都会把Object里的一个内部的计数器增加1,并把计数器的值作为这个对象的 HashCode;对于 struct 对象,将基于每个字段的 HashCode 计算得出一个整型值作为对象的 HashCode。Object 的子类型可以 override GetHashCode() 函数,对于整数类型的变量,GetHashCode() 的返回值与变量的值相同;小数、字符串等都有自己的变换规则(至于具体的规则限于篇幅将不再详细介绍)。总之,我们只要调用对象的 GetHashCode() 函数,把得到的整型值作为 k 的值就行了。另外还需要一个 Object 类型的变量 Key 保存添加的对象,我们把这两个变量封装到一个名为 Bucket 的 struct 里,Add()、Remove()、Contains() 函数也要做相应的修改:

view sourceprint?01 public class HashSet1

02 {

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

04 private struct Bucket

05 {

06 public Object Key;

07 public int k; // Store hash code;

08 }

09 private Bucket[] _buckets;

10 private readonly int DELETED = -1;

11 private int GetHashCode(Object key)

12 {

13 return key.GetHashCode();

14 }

15 public HashSet1(int capacity)

16 {

17 int size = GetPrime(capacity);

18 _buckets = new Bucket[size];

19 }

20

21 public void Add(Object item)

22 {

23 int i = 0; // 已经探查过的槽的数量

24 Bucket bucket = new Bucket { Key = item, k = GetHashCode(item) };

25 do

26 {

27 int j = DH(bucket.k, i); // 想要探查的地址

28 if (_buckets[j].Key == null || _buckets[j].k == DELETED)

29 {

30 _buckets[j] = bucket;

31 return;

32 }

33 else

34 {

35 i += 1;

36 }

37 } while (i <= _buckets.Length);

38 throw new Exception("集合溢出");

39 }

40 public bool Contains(Object item)

41 {

42 int i = 0; // 已经探查过的槽的数量

43 int j = 0; // 想要探查的地址

44 int hashCode = GetHashCode(item);

45 do

46 {

47 j = DH(hashCode, i);

48 if (_buckets[j].Key == null)

49 return false;

50

51 if (_buckets[j].k == hashCode && _buckets[j].Key.Equals(item))

52 return true;

53 else

54 i += 1;

55 } while (i <= _buckets.Length);

56 return false;

57 }

58 public void Remove(Object item)

59 {

60 int i = 0; // 已经探查过的槽的数量

61 int j = 0; // 想要探查的地址

62 int hashCode = GetHashCode(item);

63 do

64 {

65 j = DH(hashCode, i);

66 if (_buckets[j].Key == null)

67 return;

68

69 if (_buckets[j].k == hashCode && _buckets[j].Key.Equals(item))

70 {&nbs

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