"冲突处理方法：开放定址法及其解决冲突方案"

11.3冲突处理方法 开放定址法（Open Addressing）是一种处理散列表冲突的方法。当散列表中的某个地址已经有其他元素时，开放定址法会按照一定的规则寻找另一个空地址来处理冲突。 开放定址法中常用的处理冲突思路有两种：换个位置和将冲突对象组织在一起。针对换个位置的思路，开放定址法采用线性探测法；针对将冲突对象组织在一起的思路，开放定址法采用链地址法。 线性探测法是开放定址法中常用的一种方法。它以增量序列1，2，……，（TableSize -1）循环试探下一个存储地址。当发生冲突时，线性探测法会依次尝试下一个地址，直到找到一个空地址来存储元素。 以一个例子来说明线性探测法的应用。假设散列表中的关键词序列为{47，7，29，11，9，84，54，20，30}，散列表的表长为13（装填因子 α = 9/13 ≈ 0.69），散列函数为h(key) = key mod TableSize。 按照线性探测法的规则，我们对关键词序列进行散列。首先将47散列到位置8，然后7也散列到位置8，发生冲突，线性探测法会尝试下一个地址，即位置9。29散列到位置1，11散列到位置11，9散列到位置9，84散列到位置8，发生冲突，会继续尝试下一个地址，即位置10。54散列到位置4，20散列到位置7，30散列到位置4，发生冲突，会继续尝试下一个地址，即位置5。最终得到散列结果为{47，7，29，11，9，84，54，20，30}，分别存储在散列表的位置8、9、1、11、10、2、6、7、5。 除了线性探测法，开放定址法还有其他两种常见的解决冲突方案：平方探测法和双散列法。平方探测法的增量序列是通过平方计算得到的，而双散列法的增量序列是通过另一个散列函数计算得到的。这两种方法具体的计算公式分别为di = ±i^2和di = i*h2(key)，其中h2(key)是第二个散列函数。 综上所述，开放定址法是一种处理散列表冲突的方法，常用的处理冲突思路有换个位置和将冲突对象组织在一起。其中，线性探测法是一种常见的开放定址法，它通过不断尝试下一个地址来处理冲突。除了线性探测法，还有平方探测法和双散列法等其他解决冲突方案。开放定址法的选择取决于具体的应用场景和需求。