相关疑难解决方法(0)

二进制搜索树比哈希表有什么优势？

哈希表可以在Theta(1)时间查找任何元素,并且添加元素也同样容易....但我不确定反过来的优势.

当给定一组静态对象(在某种意义上是静态的,一旦加载它很少会发生变化),需要重复的并发查找以及最佳性能,哪个更好,一个HashMap或一个二进制搜索使用一些自定义比较器的数组？

答案是对象或结构类型的函数吗？哈希和/或平等功能表现？哈希的独特性？清单大小？ Hashset尺寸/尺寸？

我正在看的集合的大小可以是500k到10m之间的任何地方 - 这些信息很有用.

虽然我正在寻找一个C#答案,但我认为真正的数学答案不在于语言,所以我不包括那个标签.但是,如果需要注意C#特定的事情,那么需要该信息.

我已经注意到O(1)在讨论涉及散列和搜索类型的算法时的一些非常奇怪的用法,通常是在使用语言系统提供的字典类型的上下文中,或者使用使用数组使用的字典或散列数组类型 - 索引符号.

基本上,O(1)意味着以恒定时间和(通常)固定空间为界.一些非常基本的操作是O(1),尽管使用中间语言和特殊虚拟机往往会扭曲思考的人(例如,如何将垃圾收集器和其他动态过程分摊到O(1)活动之外).

但是忽略了延迟,垃圾收集等的摊销,我仍然不明白如何假设某些涉及某种搜索的技术可以是O(1),除非在非常特殊的条件下.

虽然我之前已经注意到这一点,但是在Pandincus问题中出现了一个例子,"'正确'集合用于在C#.NET中获取O(1)时间内的项目？" .

正如我在那里所说的那样,我所知道的唯一一个提供O(1)访问作为保证边界的集合是一个带有整数索引值的固定绑定数组.假设通过一些映射到随机存取存储器来实现该阵列,该存储器使用O(1)操作来定位具有该索引的单元.

对于涉及某种搜索以确定不同类型索引(或具有整数索引的稀疏数组)的匹配单元的位置的集合,生活并不那么容易.特别是,如果存在可能的碰撞和拥堵,则访问不完全是O(1).而如果集合是灵活的,必须认识和摊销扩大基础结构的成本(如树或哈希表),其纾缓交通挤塞(例如,高发病碰撞或树的不平衡).

我永远不会想到将这些灵活和动态的结构称为O(1).然而,我认为它们作为O(1)解决方案提供,而没有任何必须保持​​的条件,以确保实际上具有O(1)访问(以及使该常数可忽略地小).

问题:所有这些准备都是一个问题.O(1)的偶然性是什么？为什么这么盲目地被接受？是否认识到即使O(1)可能不合需要地大,即使接近常数？或者O(1)只是将计算复杂性概念挪用于非正式用途？我很困惑.

更新:答案和评论指出了我自己定义O(1)的习惯,我已经修复了.我仍然在寻找好的答案,在一些情况下,一些评论主题比他们的答案更有趣.

有没有人知道一个很好的资源来简明扼要地解释C#中可用的不同类型的列表以及它们的使用是否合适？

例如,List,Hashtable,Dictionaries等.

我不知道什么时候应该使用什么.

我们都知道,如果很好地选择了哈希函数,哈希表对插入和查找都有O(1)时间.那么,我们想要使用二进制搜索树的原因是什么？仅仅因为完美的哈希函数难以设计？

我在这里如何提出这个问题？我注意到,标准 C++ STL具有set和map其与二叉搜索树实现,但没有哈希(不是说非参考标准hash_set,hash_map).虽然,Ruby只有Hash.我想了解这种差异背后的理性.

默认情况下,C++提供基于树的映射.使用Boost,您可以获得一个hashmap.

有什么优点和缺点

1. C++的基于树的地图和

2. Boost的Hashmap？