c - 以内存效率管理二叉树中的重复项

Question

我有一个自平衡的键值二叉树(类似于 Tarjan 的 Zip 树)，其中会有重复的键。为了确保 O(log N) 性能，我唯一能想到的就是为每个节点维护三个指针；小于、大于和“等于”。 equals 指针是指向具有相同键的成员链表的指针。

这对我来说似乎内存效率低下，因为我将在整个树中为每个节点额外分配 8 个字节来处理偶发的重复事件。有没有更好的方法不涉及“作弊”，例如将左指针或右指针用作标志位？

Answer 1

• 当你有一个碰撞插入时，分配新的缓冲区，复制新的数据。
• 将新数据指针散列为一个或两个字节。您需要一个仅在零输入时返回零的散列!
• 将散列值存储在您的节点中。如果没有碰撞数据，该字段将为零，因此对于没有额外数据元素的所有键，您都是 O(log KeyCount)。最糟糕的情况是 log KeyCount 加上您的哈希算法在查找时产生的任何结果，这可能是一个常量，接近 1 个额外步骤，直到您的表必须调整大小。

显然，哈希算法的选择在这里很关键。寻找一个适用于您所针对的任何体系结构的指针值的函数。对于不同的架构，您可能需要不同的哈希值。

您可以通过仅使用一个字节的哈希值来进一步实现这一点，这些哈希值会为您提供哈希表，然后您可以使用键哈希(可以是更大的整数)来查找指向其他数据的指针。当哈希表填满时，将新的哈希表插入父表。我会把数学留给你。

关于数据局部性。由于节点数据很大，无论如何您已经没有对实际数据局部性的良好节点记录。这个方案不会改变这一点，除非你有多个数据节点用于一个特定的键，在这种情况下，你可能有缓存未命中嵌入在节点中的变量数组的正确索引。此方案避免了在发生冲突时必须重新分配节点，并且可能不会对您的缓存未命中率产生严重影响。