哈希表针对冲突的两种方式优缺点是什么?

Question

如题所述

Answer 1

哈希表，一种高效数据结构，通过关键字 key 直接定位数据，减少无用比较。然而，两个不等 key 如 f(key1) = f(key2) 产生冲突，那么 key2 需要寻找其他存放位置。常见的处理哈希冲突方法有开放定址法、再哈希（散列）函数法、链地址法等。

开放定址法，一旦发生冲突，寻找另一可用位置存放 key。其策略有线性探测法和二次探测法。线性探测法线性探测冲突位置，公式为 f(key) = (f(key) + di) % m (di = 1, 2, 3, ... , m-1)。如哈希示例中，将 4，10，11，19，29，39 散列至 n = 10 的数组，29 % 10 = 9 占位后，探测 (9 + 1) % 10，(9 + 2) % 10，(9 + 3) % 10 直至找到空位，但 29 实际与 19、10、11 冲突，探测次数增加，造成效率降低。二次探测法改进线性探测法，将 di 整为平方，公式为 f(key) = (f(key) + di) % m (di = 1², -1², 2², -2², ..., q², -q², q ≤ m/2)。对于 29，探测 (9 + 1²) % 10 = 0，(9 - 1²) % 10 = 8，最终插至下标 8 的空位。

再哈希法使用一组哈希函数 f1(key)、f2(key)、f3(key)....，当第一个哈希函数计算结果冲突时，使用第二个哈希函数，直至找到空位存放 key。这种方法避免了大量数字聚集，但增加了计算时间。

链地址法则允许多个 key 占用同一结果，通过单链表存储冲突的 key。如哈希示例中，4、10、11、19、29、39 散列至 n = 10 的数组后，冲突的 key 会存入同一单链表中。链地址法避免了寻找其他空位的情况，插入效率高，但查找性能降低，时间复杂度为 O(k)，其中 k = n / 单链表条数。

哈希表高效查找特性，使其处理冲突等细节显得次要，毕竟有得必有失。开放定址法、再哈希（散列）函数法、链地址法等方法各有优缺点，选择合适的处理冲突方法是哈希表设计的关键。