-
-
[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别
-
发表于: 2019-11-29 09:44
-
上一篇文章我们详细介绍了红黑树，但初学者往往云里雾里，不知道实战项目该用谁，今天笔者就从结合himqtt的源码，从物联网安全角度来对比一下哈希数据结构和红黑树的应用场景。 哈希和红黑树的详细教程很多，本文就不重复了，
哈希（hash）也称散列，通过散列算法变成固定的输出到数组，所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。
红黑树的自旋是天才的设计，是一种特殊的平衡二叉树数据结构，特点也是从几十万的数据里面几步就能查找到，速度快。
首先github上下载源码，https://github.com/qq4108863/himqtt ，在src\waf目录有hashmap.c和mqtt_rbtree.c ，分别是哈希和红黑树算法。
物联网可能是数百万设备联网，对高并发要求很大，所以，对网络安全产品第一要求的是性能和速度。总体来说，哈希查找速度会比红黑树快，而且查找速度基本和数据量大小无关，属于常数级别;而RB树的查找速度是log(n)级别。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
LZ不仔细看看就下结论啦。。Double-Array Trie，它是通过2个数组保存trie树，所以又叫"双数组"，可以"见缝插针"，避免了普通trie树中容易存在大量空闲结点的问题，而且比如"1234567AAA"、"1234567BBB"这2个字符串，由于公共的"1234566"只占一份内存，所以假设用一个.txt文件保存了10万条url，大小为S，用这10万条url构造成的双数组trie，大小往往比S还小。性能的话，不管树中有多少条url，查询1条url永远只需要1次匹配。感兴趣的话，可以花时间看看，顺便看看别人是怎么描述算法的。另外还有个你不喜欢听的建议，红黑树本身就很复杂了，你没描述清楚也就算了，就别再搞个标题吓人了。。 |
