图书馆与哈希表

 Oct. 30, 2012, 6:46 p.m.   2 comments    北邮 图书馆 哈希表 数据结构 考研

众所周知,敝校图书馆自习室的座位数量非常有限,为了充分利用座位资源,图书馆将每个座位编号,分配给大四的同学使用。而这,似乎与哈希表有着微妙的联系。

建立哈希表

每一位大四的同学,都可以通过将自己的学号(或者序号)通过使用一定的算法,计算出哈希值而得到自己的座位编号。这样,就建立起一个“学生-座位”的映射,我们的图书馆座位哈希表就构造成功了。

碰撞处理

哈希表可能存在冲突,图书馆的座位也不例外。当两位同学到了自习室,却发现他们的座位编号(哈希值)一致,此时,有两种方案可以用来解决冲突:

线性探测再散列

直接到相邻的下一个座位坐下,如果下一个座位已经有人则继续向后查询,直到遍历完整个图书馆自习室。

伪随机探测再散列

直接找个没人的座位坐下好了,so easy~


Aenon

Aenon Nov. 8, 2012, 8:55 p.m. Reply

不懂觉疼。


jingYi

jingYi Nov. 10, 2012, 9:09 p.m. Reply

Thanks for posting, 看起来比较幽默啊..