几种常见 容器 比较和分析 hashmap, map, vector, list …hash table

list支持快速的插入和删除,但是查找费时;

vector支持快速的查找,但是插入费时。

map查找的时间复杂度是对数的,这几乎是最快的,hash也是对数的。
如果我自己写,我也会用二叉检索树,它在大部分情况下可以保证对数复杂度,最坏情况是常数复杂度,而std::map在任何情况下都可以保证对数复杂度,原因是它保证存诸结构是完全二叉检索树,但这会在存诸上牺牲一些时间。

STL   中的   map   内部是平衡二叉树,所以平衡二叉树的性质都具备。查找数据的时间也是对数时间。 vector,在分配内存上一般要比   new   高效的多。

为什么说   hash_map   是对数级的?在不碰撞的情况下,hash_map是所有数据结构中查找最快的,它是常数级的。
如果对问题设计了足够好的hash算法,保证碰撞率很低,hash_map的查找效率无可置疑。
另外,STL的map,它的查找是对数级的,是除hash_map外最高的了,你可以说“也许还有改进余地”,但对于99.9999%的程序员,设计一个比STL   map好的map,我执悲观态度。
STL的map有平衡策略(比如红黑树什么的),所以不会退化,不需要考虑数据本身的分布问题。只不过,如果数据本身是排好序的,用vector或heap会明显的快些,因为它们的访问比较简单。

我想没必要怀疑stl::map的查找效率,影响效率最主要的因素是什么?算法,在查找问题上,有什么算法比RB_tree更好吗?至少现在还没有。不否 认你可以通过自己写代码,设计一个符合你需要的BR—TREE,比stl::map简捷那么一点,但最多也就每次迭代中少一行指令而已,处理十万个数据多 执行十万行指令,这对你重要吗?如果你不是在设计OS像LINUX,没人会关注这十万行指令花的时间。
rb-tree的时间花在了插入和删除上,如果你不是对插入和删除效率要求很高,你没有理由不选择基于rb-tree的stl::map。

大多数程序员写不出比std::map更好的map,这是当然的。然而并不是std::map的所有特性都出现在我们的程序中,自己编写的可以更适合自己的程序,的确会比std::map更快一些。

关于hash_map,它与map的实现机制是不一样的,map内部一般用树来实现,其查找操作是O(logN)的,这个没有争议,我就不多说了。
hash_map的查找,内部是通过一个从key到value的运算函数来实现的,这个函数“只接受key作为参数”,也就是说,hash_map的查找 算法与数据量无关,所以认为它是O(1)级的。来这里的应该都是达人,可以参看《数据结构》。当然,事实总不这样完美,再引一段前面我自已说的话,进一步 说明,以免误会:

—————————————–
在不碰撞的情况下,hash_map是所有数据结构中查找最快的,它是常数级的。
——————————————
注意我的前提:“在不碰撞的情况下”,其实换句话说,就是要有足够好的hash函数,它要能使key到value的映射足够均匀,否则,在最坏的情况下,它的计算量就退化到O(N)级,变成和链表一样。
如果说   hash_map   是所有容器中最慢的,也只能说:“最拙劣的hash函数”会使hash_map成为查找最慢的容器。但这样说意义不大,因为,最凑巧的排列能使冒泡排序成为最快的排序算法。

BS: “对于大型容器而言,hash_map能够提供比map快5至10倍的元素查找速度是很常见的,尤其是在查找速度特别重要的地方.另一方面,如果hash_map选择了病态的散列函数,他也可能比map慢得多. “

ANSIC++在1998年之后就没再有重大改变,并且决定不再向C++标准库中做任何重大的变更,正是这个原因,hash   table(包括hash_map)并没有被列入标准之中,虽然它理应在C++标准之中占有一席之地。
虽然,现在的大多数编译平台支持hash   table,但从可移植性方面考虑,还是不用hash   table的好。

hehe俺也来凑凑热闹。
1.有的时候vector可以替代map
比如key是整数,就可以以key的跨度作为长度来定义vector。
数据规模很大的时候,差异是惊人的。当然,空间浪费往往也惊人。
2.hash是很难的东西
没有高效低碰撞的算法,hash_xxx没有意义。
而对不同的类型,数据集,不可能有优良的神仙算法。必须因场合而宜。
俺有的解决方法是GP,可不是饭型,是遗传编程,收效不错。

你的百万级的数据放到vector不大合适。因为vector需要连续的内存空间,显然在初始化这个容器的时候会花费很大的容量。
使用map,你想好了要为其建立一个主键吗?如果没有这样的需求,为什么不考虑deque或者list?
map默认使用的是deque作为容器。其实map不是容器,拿它与容器比较意义不大。因为你可以配置它的底层容器类型。

如果内存不是考虑的问题。用vector比map好。map每插入一个数据,都要排序一次。所以速度反不及先安插所有元素,再进行排序。

用 binary_search对已序区间搜索,如果是随机存取iterator,则是对数复杂度。可见,在不考虑内存问题的情况下,vector比map 好。

如果你需要在数据中间进行插入,list 是最好的选择,vector   的插入效率会让你痛苦得想死。

涉及到查找的话用map比较好,因为map的内部数据结构用rb-tree实现,而用vector你只能用线性查找,效率很低。

stl还提供了 hash容器,理论上查找是飞快~~~。做有序插入的话vector是噩梦,map则保证肯定是按key排序的,list要自己做些事情。

HASH类型的查找肯定快,是映射关系嘛,但是插入和删除却慢,要做移动操作, LIST类型的使链式关系,插入非常快,但是查找却费时,需要遍历~~ , 还是用LIST类型的吧,虽然查找慢点,

先快速排序,然后二分查找,效率也不低

6 Responses so far.

  1. quest bars says:
    An intriguing discussion is definitely worth comment.
    I do believe that you need to publish more about this subject, it might not be a taboo matter but typically people
    don’t discuss these topics. To the next! All the best!!
  2. quest bars says:
    Greetings I am so delighted I found your weblog, I really found you by error, while I
    was looking on Yahoo for something else, Anyhow I am here now and would
    just like to say thanks a lot for a remarkable post and a all round interesting
    blog (I also love the theme/design), I don’t have time to read through it
    all at the moment but I have saved it and also added your RSS feeds, so when I have time I will be back
    to read a lot more, Please do keep up the great work.
  3. quest bars says:
    Your style is very unique in comparison to other people I’ve read stuff from.
    Many thanks for posting when you’ve got the opportunity, Guess I’ll just book mark this site.
  4. Jacalyn says:
    Wow, amazing blog layout! How long have you been blnioggg for? you make blogging look easy. The overall look of your site is great, let alone the content!

LEAVE A COMMENT