红黑树还是hash？

xtlx2000

对于数据结构而言，红黑树和hash表二者的插入、删除、查找的时间复杂度都很小，但二者有什么区别？以及应用场景？IP层数据包重组用的hash, socket端口用的hash, vm_area用的红黑树，内核的设计者们都是基于什么来考虑的？stl库对set和map的实现有红黑树和hash 2个版本，于是凌乱了，求大神指导。。。

ztz0223

这个，什么叫做复杂度都很小？rb整体是不如hash的，当然垃圾的hash是不考虑了。set能做到有序 ，但是hash就无法了。比如呢要求你的数据集是字典序的，那么hash自然退避

Godbach

回复 1# xtlx2000
hash 用起来还是比较省事。bucket 大的时候，合理的选择算法，查找的速度就会更快。


   

xtlx2000

回复 3# Godbach


    谢谢斑竹，那么既然hash快且方便，为什么内核中上述部分还用到了红黑树？基于什么的考虑？

xtlx2000

回复 2# ztz0223


    为什么红黑树整体不如hash，求解，谢谢

Godbach

回复 4# xtlx2000

红黑树查找的复杂度和总的表项有关。而 hash 使用时要考虑总的表项数以及选取的 bucket 数。不同的场合用不同的算法。

   

liuiang

2楼解释了，红黑树是排序的，hash是无序的。hash只求等值，红黑则可以判断大小。

ztz0223

对数复杂度和常数复杂度能比么？

瀚海书香

回复 1# xtlx2000
RB数关键是有大小的概念。
而且像VM这用结果，不好hash啊，除非你的bucket非常大，而且线性地址有大小的概念，所以RB数更适合vm.

   

xparmenides

如果考虑遍历等涉及顺序的问题时还是用红黑树较好。但也不是原则性问题，例如可以将hash表中的结点再串联成链表也未尝不可。选择何种数据结构有时还有主观的成分，其实有些代码在新版本中可能会采用其他的数据结构，这在内核代码中是很常见的。