所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

    它的公式是：

    f i (key)=(f(key)+d i )MOD m(d i =1,2,3,......,m-1)

    比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34}，表长为12。我们用散列函数f(key)=key mod 12。

    当计算前5个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入，如表8-11-1所示。
    image.png
    计算key=37时，发现f(37)=1，此时就与25所在的位置冲突。于是我们应用上面的公式f(37)=(f(37)+1)mod 12=2。于是将37存入下标为2的位置。

    这其实就是房子被人买了于是买下一间的作法，如表8-11-2所示。
    image.png
    接下来22,29,15,47都没有冲突，正常的存入，如表8-11-3所示。
    image.png
    到了key=48，我们计算得到f(48)=0，与12所在的0位置冲突了，不要紧，我们f(48)=(f(48)+1)mod 12=1，此时又与25所在的位置冲突。于是f(48)=(f(48)+2)mod 12=2，还是冲突……一直到f(48)=(f(48)+6)mod 12=6时，才有空位，机不可失，赶快存入，如表8-11-4所示。
    image.png
    我们把这种解决冲突的开放定址法称为线性探测法。从这个例子我们也看到，我们在解决冲突的时候，还会碰到如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。

    到了key=48，我们计算得到f(48)=0，与12所在的0位置冲突了，不要紧，我们f(48)=(f(48)+1)mod 12=1，此时又与25所在的位置冲突。于是f(48)=(f(48)+2)mod 12=2，还是冲突……一直到f(48)=(f(48)+6)mod 12=6时，才有空位，机不可失，赶快存入，如表8-11-4所示。

    考虑深一步，如果发生这样的情况，当最后一个key=34，f(key)=10，与22所在的位置冲突，可是22后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差。因此我们可以改进d i =1 2 ,-1 2 ,2 2 ,-2 2 ,……,q 2 ,-q 2 ,(q≤m/2)，这样就等于是可以双向寻找到可能的空位置。对于34来说，我们取di=-1即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。我们称这种方法为二次探测法。

    f i (key)=(f(key)+d i )MOD m(d i =1 2 ,-1 2 ,2 2 ,-2 2 ,...,q 2 ,-q 2 ,q≤m/2)

    还有一种方法是，在冲突时，对于位移量d i 采用随机函数计算得到，我们称之为随机探测法。

    此时一定有人问，既然是随机，那么查找的时候不也随机生成d i 吗？如何可以获得相同的地址呢？这是个问题。这里的随机其实是伪随机数。伪随机数是说，如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，我们在查找时，用同样的随机种子，它每次得到的数列是相同的，相同的d i 当然可以得到相同的散列地址。

    嗯？随机种子又不知道？罢了罢了，不懂的还是去查阅资料吧，我不能在课上没完没了的介绍这些基础知识呀。

    f i (key)=(f(key)+d i )MOD m(d i 是一个随机数列)

    总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。