z****e 发帖数: 2024 | 1 why is STL map implemented by RB-tree, rather than hash table?
can some one explain the cons and pros of RB-tree and hash table, when to
pick which to use?
RB-tree VS. hash table.
Thanks. |
h****8 发帖数: 599 | 2 因为map的元素是按照key排序的 所以要用rbt,hashtable不能排
序 |
z****e 发帖数: 2024 | 3 你这点说得非常对,map里边有iterator,是可以按顺序遍历的,hash 无法排序,无法
选择(比如第ith smallest)。
我还加一点,就是dynamic hash table. 因为事先不知道元素多少,无法确定table大
小,只能用table被填满一半,就把table大小翻倍,(linear probing 情况下)。这
个操作比较昂贵。用separate chaining 的话,元素越多,就越来效率越低。说是O(1)
的操作,最后都不知道O几了。
所以,不知道大小,就RB-tree,实现动态调整大小,而且,插,删,找,永远log(N)。
不知道这样说对不对,还有没有其他补充。
多谢大家。
【在 h****8 的大作中提到】 : 因为map的元素是按照key排序的 所以要用rbt,hashtable不能排 : 序
|
h****8 发帖数: 599 | 4 table size翻倍到不一定 因为可以表中存指针,指针指向指针数组,数组
里的指针都指向动态分配的内存块,这才是真正key所在的位置 一旦满了就多分配
一块好了,不需要复制已有的元素
麻烦的是删除 而且有时候space开销太大如果hash func取得不好的话 |
B*******g 发帖数: 1593 | 5 http://www.codeguru.com/forum/archive/index.php/t-386222.html
里面有一些讨论和link
to
【在 z****e 的大作中提到】 : why is STL map implemented by RB-tree, rather than hash table? : can some one explain the cons and pros of RB-tree and hash table, when to : pick which to use? : RB-tree VS. hash table. : Thanks.
|