题

我正在努力思考何时使用二叉搜索树以及何时使用字典的概念。

在我的应用程序中，我做了一个使用 C5 库的小实验 TreeDictionary （我认为这是一个红黑二叉搜索树）和 C# 字典。字典的添加/查找操作总是更快，并且总是使用更少的内存空间。例如，16809 <int, float> 条目，字典使用 342 KiB，而树使用 723 KiB。

我认为 BST 应该具有更高的内存效率，但似乎树的一个节点比字典中的一个条目需要更多的字节。是什么赋予了？BST 是否有比字典更好的地方？

另外，作为一个附带问题，有谁知道是否有更快+内存效率更高的数据结构来存储 <int, float> 字典类型访问的对比上述任何一个结构？

有帮助吗？

解决方案

我认为BST应该更有效地记忆效率，但是看来树的一个节点需要比字典中的一个条目更多的字节。是什么赋予了？BST比字典更好吗？

我个人从未听说过这样的原则。即便如此，这只是一个一般原则，而不是刻在宇宙结构中的绝对事实。

一般来说，字典实际上只是链表数组的一个精美包装。您可以在字典中插入如下内容：

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

所以就是 几乎 O(1) 操作。该字典使用 O(internalArray.Length + n) 内存，其中 n 是集合中的项目数。

一般来说，BST 可以实现为：

  • 链表，使用 O(n) 空间，其中 n 是集合中的项目数。
  • 数组, ，使用 O(2H - n) space，其中 h 是树的高度，n 是集合中的项目数。
    • 由于红黑树的有限高度为 O(1.44 * n)，因此数组实现的有限内存使用量应约为 O(21.44n -n)

可能性是，C5 TreeDictionary 是使用数组实现的，这可能是造成空间浪费的原因。

是什么赋予了？BST比字典更好吗？

字典有一些不良特性：

  • 即使字典的内存需求远小于可用 RAM 总量，也可能没有足够的连续内存块来保存字典。

  • 评估哈希函数可能需要任意长的时间。例如，字符串使用 Reflector 来检查 System.String.GetHashCode 方法——您会注意到对字符串进行哈希处理总是需要 O(n) 时间，这意味着对于很长的字符串可能需要相当长的时间。另一方面，比较字符串的不等式几乎总是比散列更快，因为它可能只需要查看前几个字符。如果哈希码计算时间太长，则树插入完全有可能比字典插入更快。

    • Int32 的 GetHashCode 方法实际上只是 return this, ，所以你很难找到带有 int 键的哈希表比树字典慢的情况。

RB 树有一些理想的特性：

  • 与使用字典的 O(n) 时间相比，您可以在 O(log n) 时间内找到/删除最小和最大元素。

  • 如果一棵树被实现为链表而不是数组，则该树是 通常 比字典更节省空间。

  • 同样，编写支持在 O(log n) 时间内插入/查找/删除的不可变版本的树是非常容易的。字典不能很好地适应不变性，因为您需要为每个操作复制整个内部数组（实际上，我 有 见过一些基于数组的不可变手指树的实现，这是一种通用字典数据结构，但实现非常复杂）。

  • 您可以在恒定的空间和 O(n) 时间内按排序顺序遍历树中的所有元素，而您需要将哈希表转储到数组中并对其进行排序才能获得相同的效果。

因此，数据结构的选择实际上取决于您需要什么属性。如果您只想要一个无序的包并且可以保证您的哈希函数快速计算，请使用 .Net 字典。如果您需要有序包或哈希函数运行缓慢，请使用 TreeDictionary。

其他提示

这有一定道理，一个树节点将需要比一个字典条目更多的存储空间。二叉树节点需要存储的价值和左，右子树两者。通用Dictionary<TKey, TValue>被实现为哈希表 - 我假设 - 无论是使用链接的列表中为每个桶（价值加上一个指针/引用）或某种重映射（只值）。我不得不在反射偷看可以肯定的，但对这个问题的目的，我不认为这是非常重要的。

在稀疏哈希表，在存储装置/存储器方面的效率较低。如果你创建一个哈希表（字典）和初始化其容量为1万人，只与10,000个元素填充它，那么我敢肯定它会吃掉大量的内存大于10000个节点的BST。

但是，我不会担心任何的这一点，如果节点/键的量仅为数千。那将会在千字节进行测量时，相比于物理RAM的字节。

如果问题是“为什么你想使用二叉树而不是一个哈希表？”那么最好的答案IMO是二叉树是有序的，而哈希表都没有。您只能搜索是完全相等的东西键的哈希表;同一株树，你可以搜索值的范围，最接近的值，等等，这是一个非常重要的区别，如果你创建一个索引或类似的东西。

在我看来，你正在做一个不成熟的优化。

我建议你什么是它的结构，你实际上正在使用创建隔离的接口，然后实现使用字典（这似乎工作最好）的接口。

如果内存/性能就成了一个问题（这可能不会对20k-数字），那么你就可以创建其他的接口实现，并检查其中一个作品最好成绩。你不会需要更改代码的其余部分几乎所有的东西（除了实现您正在使用）。

有一棵树，接口哈希表（我猜是你的解释是基于一个）应该是非常相似的。总是旋转围绕键控查找。

我一直认为一个解释是一次创造一些东西，然后再在其上做大量的查找更好。虽然树是更好，如果你是显著修改它。不过，我不知道我在哪里捡到这个想法从最多。

（函数式语言经常使用的树木为基础，他们的集合，你可以重新使用大部分树，如果你做小的修改的话）。

你不比较“与苹果苹果”，一个BST会给你一个订购表示，而一本字典可以让你做一个键值对查找（你的情况）。

我不希望太多的大小在2的内存占用，但字典会给你一个更快的查找。若要查找BST的项目，你（可能）需要遍历整个树。但要做到一个dictnary查找您只需查找基于键。

如果你需要保护你的数据结构的等待时间尖峰和哈希冲突攻击的平衡BST是优选的。

前者发生在阵列支持结构生长的被调整尺寸，后者是散列算法从无限空间有限整数范围中的投影的必然性。

在.NET的另一个问题是，有LOH，并具有足够大的字典碰上LOH碎片。在这种情况下，你可以使用BST，付出更大的算法复杂度类的价格。

在短，具有BST支持由分配堆你得到最坏的情况下为O（log（N））的时间，用哈希表你得到O（N）最坏情况下的时间。

BST正值O（日志（N））的平均时间的价格，更糟糕的缓存局部性多堆分配，但它具有等待时间保证并从字典攻击和内存碎片保护。

值得关注的是BST也是在其他平台上存储器碎片的受试者，不使用压缩垃圾收集器。

对于存储器大小，.NET Dictionary`2类是更有效的存储器，因为它存储数据，为米堆链表，其中仅存储值和偏移信息。 BST具有存储对象标头（如每个节点是在堆上一个类的实例），两个指针和用于平衡树一些增强树数据。例如，红黑树需要解释为颜色（红色或黑色）一个布尔值。这是至少6点机的话，如果我没有记错。因此，在64位系统中的红 - 黑树的每个节点是最小的：

3个字头= 24个字节 2个字用于孩子指针= 16个字节 1个字为颜色= 8个字节 至少1个字为值8+字节 = 24 + 16 + 8 + 8 = 56个字节（8个字节，如果树使用一个父节点的指针）。

与此同时，字典条目的最小尺寸将只是16字节。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top