通常你会看到各种操作的复杂性,这是一个很好的指南:分摊O(1)插入,O(1)查找,删除哈希映射,而不是O(log N)插入,查找,删除树 - 基于地图.
然而,在某些情况下,复杂性具有误导性,因为所涉及的常数术语是极端的.例如,假设您的10k项目已键入字符串.进一步假设这些字符串的长度均为100k字符.假设不同的字符串通常在字符串的开头附近不同(例如,如果它们基本上是随机的,则第一个字节中的对将有所不同,概率为255/256).
然后要进行查找,hashmap必须散列100k字符串.这是集合大小的O(1),但可能需要相当长的时间,因为它可能是字符串长度的O(M).平衡树必须进行log N <= 14比较,但每个只需要查看几个字节.这可能不会花很长时间.
在内存访问方面,使用64字节高速缓存行大小,散列映射加载超过1500个连续行,并执行100k字节操作,而树加载15个随机行(实际上可能是30个由于通过字符串的间接)并且确实为14*(一些小数字)字节操作.你可以看到前者可能比后者慢.或者它可能更快:您的架构的FSB带宽,停顿时间和推测性读取缓存有多好？
如果查找找到匹配,那么除此之外,两个结构都需要执行单个全长字符串比较.如果桶中发生冲突,则hashmap也可能会执行其他失败的比较.
因此,假设失败的比较是如此之快以至于可以忽略不计,而成功的比较和散列运算速度很慢,那么树的速度大约是散列的1.5-2倍.如果这些假设不成立,那就不会.
当然,这是一个极端的例子,但很容易看出,在您的数据上,特定的O(log N)操作可能比特定的O(1)操作快得多.您当然需要进行测试,但如果您的测试数据不能代表现实世界,那么您的测试结果也可能不具代表性.基于复杂性的数据结构的比较是指当N接近无穷大时的极限行为.但是N并没有接近无穷大.这是10000.
它不仅仅是插入和移除.您必须考虑在hash_map vs map中以不同方式分配内存,并且每次都必须计算要搜索的值的哈希值.
我认为Dr.Dobbs的文章最能回答你的问题:
| 归档时间： |
|
| 查看次数： |
15285 次 |
| 最近记录： |