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 因为ｍａｐ的元素是按照ｋｅｙ排序的 所以要用ｒｂｔ，ｈａｓｈｔａｂｌｅ不能排
序 |
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 的大作中提到】
: 因为ｍａｐ的元素是按照ｋｅｙ排序的 所以要用ｒｂｔ，ｈａｓｈｔａｂｌｅ不能排
: 序
|
h****8
发帖数: 599 | 4 ｔａｂｌｅ ｓｉｚｅ翻倍到不一定 因为可以表中存指针，指针指向指针数组，数组
里的指针都指向动态分配的内存块，这才是真正ｋｅｙ所在的位置 一旦满了就多分配
一块好了，不需要复制已有的元素
麻烦的是删除 而且有时候ｓｐａｃｅ开销太大如果ｈａｓｈ ｆｕｎｃ取得不好的话 |
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.
|
