NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 18 题

散列表的地址区间为 $0\sim 10$，散列函数为 $H(K)=K \bmod 11$。采用开地址法的线性探查法处理冲突，并将关键字序列 $26,25,72,38,8,18,59$ 存储到散列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素 $59$ 存放在散列表中的可能地址有：

直接算59的哈希值是4，但线性探查是‘占坑’游戏。别盯着4看，要想：4被谁占了？谁又占了5？谁堵死了6？只要把26,25,72,38,8,18这几个‘拦路虎’按不同顺序插进去，看59被挤到哪一步，就能枚举出所有可能位置。

学生最容易犯两个错：一是死记硬背‘59 mod 11 = 4’，以为答案就是4，完全忽略冲突链；二是只考虑一种插入顺序（比如26最先），得出59一定在5，就漏掉了其他顺序下59被挤到7或9的情况。线性探查的坑就在于‘顺序不同，结局不同’，必须穷举关键字的插入次序，看59最终停在哪。

考点与概念

本题考查散列表（哈希表）的线性探查法处理冲突。散列函数 $H(K)=K \bmod 11$ 把关键字映射到 $0\sim 10$ 的地址。当目标地址已被占用时，线性探查依次检查 $(H(K)+1)\bmod 11, (H(K)+2)\bmod 11, \dots$，直到找到空位插入。

命题视角

命题人爱挖的坑就是：只算理论地址而忽略插入顺序。59的理论地址是 $59\bmod 11=4$，但4可能被26（$26\bmod 11=4$）占据，5可能被38（$38\bmod 11=5$）占据，6可能被72（$72\bmod 11=6$）占据。谁先谁后，59就被挤到不同的位置。题目特意说‘存入顺序不确定’，就是要你枚举所有可能。