algorithm - 处理使用自平衡树实现的关联数组中的冲突

Question

如何在使用自平衡树实现的关联数组中处理冲突？如果两个对象具有相同的哈希值，它们是存储在连接到树节点的链表中还是创建了两个节点？如果是前者，那么它是怎样的O(log n)，如果是后者，二叉搜索树如何处理相同的键（哈希）？

Answer 1

搜索树绝对不能处理具有相同键的两个节点，因此您确实需要将具有冲突键的条目存储在单独的数据结构中（通常，如您所说，附加到树节点的链表）。您确实不会有 O(log n) 的最坏情况复杂性，就像实现为哈希表的关联数组不会有最坏情况 O(1) 操作一样。

正如墓志铭所言，要尝试的一件事是增加哈希键的长度，以免发生冲突。但是，您不能保证不会，并且确实需要为具有相同哈希的两个对象做出某种规定。但是，如果您正确选择散列算法，这应该是一种罕见的情况，并且您的平均查找时间复杂度将为 O(log n)，即使在所有具有相同的哈希键。