哈希函数处理冲突的方法

　　哈希函数是一种将数据映射到固定大小的索引值的函数。由于输入数据的无限性和哈希表大小的有限性，很可能会出现冲突，即两个不同的输入数据映射到相同的索引值上。

　　解决哈希函数处理冲突的方法主要有以下几种：

　　1、链地址法（拉链法）：这是最常见的解决哈希冲突的方法之一。在链地址法中，每个哈希桶存储的是一个链表或其他数据结构，当多个数据映射到同一个索引值时，它们会被插入到对应索引的链表中。这样，当需要查找某个数据时，需要遍历链表来找到目标数据。

　　2、开放地址法：在开放地址法中，每个哈希桶存储的是一个数据，当发生冲突时，将尝试在哈希表中的其他位置寻找空闲槽位来存储冲突的数据。开放地址法包括线性探测、二次探测和再哈希等方法。

　　- 线性探测：当发生冲突时，会依次查找哈希表中的下一个位置，直到找到一个空闲位置为止。具体地，如果某个数据映射到索引i，但是该位置已经被占用，那么会查找索引i+1，如果i+1仍然被占用，则继续查找i+2，以此类推，直到找到一个空闲位置为止。

　　- 二次探测：与线性探测类似，但是查找的步长不是固定的，而是通过一个二次函数计算得到的。具体地，如果某个数据映射到索引i，但是该位置已经被占用，那么会查找索引i+1²，如果i+1²仍然被占用，则继续查找i+2²，以此类推，直到找到一个空闲位置为止。

　　- 再哈希：这种方法会使用一个不同的哈希函数来计算新的索引值，以便当发生冲突时可以找到下一个空闲位置。具体地，如果某个数据映射到索引i，但是该位置已经被占用，那么会利用另外一个哈希函数计算出一个新的索引j，然后查找索引j，如果j仍然被占用，则继续计算新的索引值，直到找到一个空闲位置为止。

　　3、公共溢出区：这种方法会将所有冲突的数据都存储在一个公共的溢出区中。当哈希函数发生冲突时，将数据插入到溢出区中，然后通过一个指针将其链接到原本应该插入的位置。这样，在查找数据时，会根据哈希函数计算出索引值，然后再检查溢出区是否存在相应的数据。

　　不同的解决哈希冲突的方法有各自的优缺点。链地址法简单易实现，但是需要额外的空间来存储链表。开放地址法不需要额外的空间，但是容易产生聚集现象，导致查找效率下降。公共溢出区方法比较灵活，但是需要额外的指针来链接数据，增加了空间开销。在实际应用中，我们可以根据具体的情况选择合适的解决哈希冲突的方法。