使用自平衡树实现关联数组中的冲突处理
使用自平衡树实现的关联数组中如何处理冲突？如果两个对象具有相同的哈希值，它们是否存储在附加到树节点的链表中或创建两个节点？如果是前者，那么它是如何O(log n)的，如果是后者，二叉搜索树如何处理相同的键（哈希）？
How are collisions handled in associative arrays implemented using self-balanced tree? If two objects have same hash are they stored in a linked list attached to a tree node or two nodes are created? In it's the former, then how it is O(log n) and if latter, how binary search tree can handle same keys (hashes)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
搜索树绝对不能处理具有相同键的两个节点，因此您确实需要将具有冲突键的条目存储在单独的数据结构中（通常，正如您所说，附加到树节点的链表）。您确实不会有最坏情况下的 O(log n) 复杂度，就像作为哈希表实现的关联数组不会有最坏情况下的 O(1) 操作一样。
正如墓志铭所指出的，要尝试的一件事是增加散列键的长度，以免发生冲突。但是，您不能保证不会，并且确实需要为具有相同哈希值的两个对象做出某种规定。不过，如果您正确选择散列算法，这应该是一种罕见的情况，并且查找的平均时间复杂度将为 O(log n)，即使它可能会降级为 O(n)所有具有相同哈希键的退化情况。
Search trees can definitely not handle two nodes with the same key, so you do need to store the entries with colliding keys in a separate data structure (typically, as you say, a linked list attached to a tree node). You will indeed not have a worst-case complexity of O(log n), just as an associative array implemented as a hash table will not have worst-case O(1) operations.
As epitaph notes, one thing to try is increasing the length of your hash keys, so as to not get collisions. You can't guarantee that you won't, though, and do need to make some sort of provision for two objects with the same hash. If you choose your hashing algorithm properly, though, this should be a rare case, and your average time complexity for lookups will be O(log n), even though it can degrade to O(n) in the degenerate case of everything having the same hash key.