C#二叉树和字典

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

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

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

另外,作为一个附带问题,有没有人知道是否存在更快+更高内存效率的数据结构,用于存储字典类型访问的对,而不是上述任何一种结构?

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

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

通常,字典实际上只是一组链接列表的奇特包装。 你插入字典中的东西:

 LinkedList> 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方法实际上就是return this ,所以你会很难找到一个带有int键的哈希表比一个树词典慢的情况。

RB树有一些理想的属性:

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

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

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

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

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

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

我建议你创建一个接口来隔离你实际使用的结构,然后使用Dictionary实现接口(这看起来效果最好)。

如果内存/性能成为一个问题(可能不会出现20k数字),那么您可以创建其他接口实现,并检查哪个工作最佳。 您不需要更改其余代码中的任何内容(除了您正在使用的实现)。

有意义的是,树节点需要比字典条目更多的存储空间。 二叉树节点需要存储该值以及左右子树。 通用Dictionary实现为哈希表 – 我假设 – 使用每个桶的链表(值加一个指针/引用)或某种重新映射(只是值)。 我必须先看看Reflector才能确定,但​​出于这个问题的目的,我认为这并不重要。

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

如果节点/键的数量仅为数千,我仍然不担心这些。 与千兆字节的物理RAM相比,这将以千字节为单位进行测量。


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

Tree和Hash表的接口(我猜的是你的Dictionary基于它的接口)应该非常相似。 始终围绕键控查找。

我一直认为字典更适合创建一次,然后对其进行大量查找。 虽然如果你对它进行大幅修改,树会更好。 但是,我不知道从哪里挑选了这个想法。

(函数式语言通常使用树作为它们集合的基础,因为如果对它进行少量修改,可以重用大部分树)。

你不是在比较“苹果和苹果”,BST会给你一个有序的表示,而字典允许你对一个键值对进行查找(在你的情况下)。

我不希望2之间的内存占用大小,但字典会给你更快的查找。 要在BST中查找项目,您(可能)需要遍历整个树。 但是要做一个dictnary查找,你只需根据键进行查找。