C#二叉树和字典

Question

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

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

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

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

Answer 1

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

RB树有一些理想的属性:

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

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

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

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

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