从hihttps开源waf教你红黑树和哈希表的不同

从hihttps开源waf教你红黑树和哈希表的不同

哈希和红黑树的详细教程很多，但初学者往往云里雾里，不知道实战项目该用谁，今天笔者就从结合hi，在src\waf目录有hashmap.c和mqtt_rbtree.c ，分别是哈希和红黑树算法。

二、使用场景

1、速度对比物联网可能是数百万设备或者用户联网，对高并发要求很大，所以，对网络安全产品第一要求的是性能和速度。总体来说，哈希查找速度会比红黑树快，而且查找速度基本和数据量大小无关，属于常数级别;而RB树的查找速度是log(n)级别。红黑树查找和删除的时间复杂度都是O(logn)，Hash查找和删除的时间复杂度都是O(1)。 如果红黑树的树高度不深如小于8，采用的是数字查找，两者性能没有太多的差异。也就是并非所有的场景，哈希都比红黑树快，要看代码的优化程度。hiJava 的hashmap就是把哈希和红黑树结合在以前的。当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树。

4 复杂程度哈希更简单，红黑树算法复杂一点，不过这都不是事，大神早开源了很多稳定的版本。

三、应用场景总结红黑树是有序的，哈希是无序的，根据项目需求来选择，阿里巴巴的很多项目用红黑树更多，笔者认为主要还是和内存有关，如果内存要求苛刻的项目，就用红黑树；如果内存足够大，牺牲内存换取更快的速度，哈希完全适合。Hiihttps开源waf大量采用哈希算法，可能和速度并发要求有关。总之，数据结构是网络安全最基础的学科。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。