众所周知,敝校图书馆自习室的座位数量非常有限,为了充分利用座位资源,图书馆将每个座位编号,分配给大四的同学使用。而这,似乎与哈希表有着微妙的联系。
建立哈希表
每一位大四的同学,都可以通过将自己的学号(或者序号)通过使用一定的算法,计算出哈希值而得到自己的座位编号。这样,就建立起一个“学生-座位”的映射,我们的图书馆座位哈希表就构造成功了。
碰撞处理
哈希表可能存在冲突,图书馆的座位也不例外。当两位同学到了自习室,却发现他们的座位编号(哈希值)一致,此时,有两种方案可以用来解决冲突:
线性探测再散列
直接到相邻的下一个座位坐下,如果下一个座位已经有人则继续向后查询,直到遍历完整个图书馆自习室。
伪随机探测再散列
直接找个没人的座位坐下好了,so easy~
Leave a Comment