16

我正在为何时使用二叉搜索树以及何时使用字典的概念而苦苦挣扎。

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

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

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

4

6 回答 6

8

我认为 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(2 h - n) 空间，其中 h 是树的高度，n 是集合中的项目数。
    • 由于红黑树的有界高度为 O(1.44 * n)，因此数组实现的有界内存使用量应约为 O(2 1.44n - n)

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

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

字典有一些不受欢迎的属性：

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

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

    • Int32 的GetHashCode方法实际上是 just return this，因此您很难找到带有 int 键的哈希表比树字典慢的情况。

RB 树有一些理想的属性：

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

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

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

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

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

于 2010-01-28T03:16:38.757 回答
2

树节点需要比字典条目更多的存储空间是有道理的。二叉树节点需要存储值以及左右子树。泛型Dictionary<TKey, TValue>被实现为一个哈希表——我假设它——或者为每个桶使用一个链表（值加上一个指针/引用）或某种重新映射（只是值）。我必须先看看 Reflector 才能确定，但​​就这个问题而言，我认为这并不重要。

哈希表越稀疏，在存储/内存方面的效率就越低。如果您创建一个哈希表（字典）并将其容量初始化为 100 万，并且只填充 10,000 个元素，那么我很确定它会比具有 10,000 个节点的 BST 消耗更多的内存。

不过，如果节点/键的数量只有数千个，我不会担心这些。与物理 RAM 的千兆字节相比，这将以千字节为单位。

如果问题是“为什么要使用二叉树而不是哈希表？” 那么最好的答案 IMO 是二叉树是有序的，而哈希表不是。您只能在哈希表中搜索与某物完全相等的键；使用树，您可以搜索一系列值、最接近的值等。如果您要创建索引或类似的东西，这是一个非常重要的区别。

于 2010-01-28T02:39:23.760 回答
0

树和哈希表的界面（我猜这是您的字典所基于的）应该非常相似。始终围绕键控查找。

我一直认为字典更适合创建一次然后对其进行大量查找。如果你对它进行显着修改，一棵树会更好。但是，我不知道我是从哪里得到这个想法的。

（函数式语言通常使用树作为它们集合的基础，因为如果您对其进行小的修改，您可以重用大部分树）。

于 2010-01-28T02:40:16.677 回答
0

您不是在比较“苹果与苹果”，BST 将为您提供有序的表示，而字典允许您查找键值对（在您的情况下）。

我不希望 2 之间的内存占用量很大，但字典会给你一个更快的查找。要在 BST 中找到一个项目，您（可能）需要遍历整个树。但是要进行字典查找，您只需根据键进行查找。

于 2010-01-28T03:05:18.783 回答
0

在我看来，你正在做一个过早的优化。

我建议你创建一个接口来隔离你实际使用的结构，然后使用 Dictionary 实现接口（这似乎效果最好）。

如果内存/性能成为问题（对于 20k 数字可能不会），那么您可以创建其他接口实现，并检查哪个最有效。您几乎不需要更改其余代码中的任何内容（您正在使用的实现除外）。

于 2010-01-28T02:26:17.380 回答
0

如果您需要保护您的数据结构免受延迟峰值和哈希冲突攻击，则最好使用平衡的 BST。

前者发生在数组支持的结构增长和调整大小时，后者是散列算法的必然属性，作为从无限空间到有限整数范围的投影。

.NET 中的另一个问题是存在 LOH，如果字典足够大，您会遇到 LOH 碎片。在这种情况下，您可以使用 BST，但要付出更大的算法复杂度等级的代价。

简而言之，使用由分配堆支持的 BST，您将获得最坏情况 O(log(N)) 的时间，而使用哈希表，您将获得 O(N) 最坏情况的时间。

BST 以 O(log(N)) 平均时间、更差的缓存局部性和更多的堆分配为代价，但它具有延迟保证并且可以防止字典攻击和内存碎片。

值得注意的是，BST 在其他平台上也容易产生内存碎片，而不是使用压缩垃圾收集器。

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

标题 3 个字 = 24 字节 子指针 2 个字 = 16 字节 颜色 1 个字 = 8 个字节 值至少 1 个字 8+ 字节 = 24+16+8+8 = 56 字节（+8 字节如果树使用父节点指针）。

同时，字典条目的最小大小仅为 16 个字节。

于 2018-12-10T13:18:03.953 回答