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

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

2011-04-19

不用链接法,还有别的方法能处理碰撞吗?扪心自问,我不敢问这个问题。链接法如此的自然、直接,以至于我不敢相信还有别的(甚至是更好的)方法。推动科技进步的人,永远是那些敢于问出比外行更天真、更外行的问题,并且善于运用丰富的想

不用链接法,还有别的方法能处理碰撞吗?扪心自问,我不敢问这个问题。链接法如此的自然、直接,以至于我不敢相信还有别的(甚至是更好的)方法。推动科技进步的人,永远是那些敢于问出比外行更天真、更外行的问题,并且善于运用丰富的想象力找到新的可能性,而且有能力运用科学的方法实践的人。
  如果可以不用链表,把节省下来的链表的指针所占用的空间用作空槽,就可以减少碰撞的机会,提高查找速度。

使用开放寻址法处理碰撞

  不用额外的链表,以及任何其它额外的数据结构,就只用一个数组,在发生碰撞的时候怎么办呢?答案只能是,再找另一个空着的槽啦!这就是开放寻址法(open addressing)。但是这样难道不是很不负责任的吗?想象一下,有一趟对号入座的火车,假设它只有一节车厢,上来一位坐7号座位的旅客。过了一会儿,又上来一位旅客,他买到的是一张假票,也是7号座位,这时怎么办呢?列车长想了想,让拿假票的旅客去坐8号座位。过了一会儿,应该坐8号座位的旅客上来了,列车长对他说8号座位已经有人了,你去坐9号座位吧。哦?9号早就有人了?10号也有人了?那你去坐11号吧。可以想见,越到后来,当空座越来越少时,碰撞的几率就越大,寻找空座愈发地费劲。但是,如果是火车的上座率只有50%或者更少的情况呢?也许真正坐8号座位的乘客永远不会上车,那么让拿假票的乘客坐8号座位就是一个很好的策略了。所以,这是一个空间换时间的游戏。玩好这个游戏的关键是,让旅客分散地坐在车厢里。如何才能做到这一点呢?答案是,对于每位不同的旅客使用不同的探查序列。例如,对于旅客 A,探查座位 7,8,23,56……直到找到一个空位;对于旅客B,探查座位 25,66,77,1,3……直到找到一个空位。如果有 m 个座位,每位旅客可以使用 <0, 1, 2, ..., m-1> 的 m! 个排列中的一个。显而易见,最好减少两个旅客使用相同的探查序列的情况。也就是说,希望把每位旅客尽量分散地映射到 m! 种探查序列上。换句话说,理想状态下,如果能够让每个上车的旅客,使用 m! 个探查序列中的任意一个的可能性是相同的,我们就说实现了一致散列。(这里没有用“随机”这个词儿,因为实际是不可能随机取一个探查序列的,因为在查找这名旅客时还要使用相同的探查序列)。
  真正的一致散列是难以实现的,实践中,常常采用它的一些近似方法。常用的产生探查序列的方法有:线性探查,二次探查,以及双重探查。这些方法都不能实现一致散列,因为它们能产生的不同探查序列数都不超过 m2 个(一致散列要求有 m! 个探查序列)。在这三种方法中,双重散列能产生的探查序列数最多,因而能给出最好的结果(注:.net framework 的 HashTable 就是使用的双重散列法)。
  在上一篇中,我们实现了一个函数 h(k),它的任务是把数值 k 映射为一个数组(尽量分散)的地址。这次,我们使用开发寻找法,需要实现一个函数 h(k, i),它的任务是把数值 k 映射为一个地址序列,序列的第一个地址是 h(k, 0),第二个地址是 h(k, 1)……序列中的每个地址都要尽可能的分散。

线性探查

  有这样一个可以用 10 个槽保存 0~int.MatValue (但是不能处理碰撞)的 IntSet1:

view sourceprint?01 public class IntSet1

02 {

03 private object[] _values = new object[10];

04

05 private int H(int value)

06 {

07 return value % 10;

08 }

09

10 public void Add(int item)

11 {

12 _values[H(item)] = item;

13 }

14 public void Remove(int item)

15 {

16 _values[H(item)] = null;

17 }

18 public bool Contains(int item)

19 {

20 if (_values[H(item)] == null)

21 return false;

22 else

23 return (int)_values[H(item)] == item;

24 }

25 }

现在想用开放寻址法处理碰撞,该怎么改造它?最简单的方法是,如果发现 values[8] 已经被占用了,就看看 values[9] 是否空着,如果 values[9] 也被占用了,就看看 values[0] 是不是还空着。完整的描述是,先使用 H() 函数获取 k 的第一个地址,如果这个地址已被占用,就探查下一个紧挨着的地址,如果还是不能用,就探查下一个紧挨着的地址,如果到达了数组的末尾,就卷绕到数组的开头,如果探查了 m 次还是没有找到空槽,就说明数组已经满了,这就是线性探查(linear probing)。实现代码是:

view sourceprint?01 public class IntSet2

02 {

03 private object[] _values = new object[10];

04

05 private int H(int value)

06 {

07 return value % 10;

08 }

09

10 private int LH(int value, int i)

11 {

12 return (H(value) + i) % 10;

13 }

14

15 public void Add(int item)

16 {

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

18 do

19 {

20 int j = LH(item, i); // 想要探查的地址

21 if (_values[j] == null)

22 {

23 _values[j] = item;

24 return;

25 }

26 else

27 {

28 i += 1;

29 }

30 } while (i <= 10);

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

32 }

33 public bool Contains(int item)

34 {

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

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

37 do

38 {

39 j = LH(item, i);

40 if (_values[j] == null)

41 return false;

42

43 if ((int)_values[j] == item)

44 &nbsp

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