-
-
-
[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别
- 2天前 261
-
[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别
上一篇文章我们详细介绍了红黑树，但初学者往往云里雾里，不知道实战项目该用谁，今天笔者就从结合himqtt的源码，从物联网安全角度来对比一下哈希数据结构和红黑树的应用场景。 哈希和红黑树的详细教程很多，本文就不重复了，
一、哈希和红黑树基本原理
哈希（hash）也称散列，通过散列算法变成固定的输出到数组，所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。
红黑树的自旋是天才的设计，是一种特殊的平衡二叉树数据结构，特点也是从几十万的数据里面几步就能查找到，速度快。
二、物联网安全使用场景
首先github上下载源码，https://github.com/qq4108863/himqtt ，在src\waf目录有hashmap.c和mqtt_rbtree.c ，分别是哈希和红黑树算法。
1、速度对比
物联网可能是数百万设备联网，对高并发要求很大，所以，对网络安全产品第一要求的是性能和速度。总体来说，哈希查找速度会比红黑树快，而且查找速度基本和数据量大小无关，属于常数级别;而RB树的查找速度是log(n)级别。
红黑树查找和删除的时间复杂度都是O(logn)，Hash查找和删除的时间复杂度都是O(1)。 如果红黑树的树高度不深如小于8，采用的是整形数字查找，两者性能没有太多的差异。
也就是并非所有的场景，哈希都比红黑树快，要看代码的优化程度。himqtt使用的linux高并发EPOLL模式事件管理，就是红黑树。
2、数据预知
静态数据，可以基本预知大小，用哈希。如himqtt初始化的攻击规则就几百条在可控范围内，另外TOPIC黑白名单、URL地址等也不会太多，也是用的哈希就可以了。
动态数据，如统计IP地址、任务调度、epoll高并发事件管理，无法判断多少，可能很少，也可能巨多，用红黑树更佳。当然，如果大概知道设备IP地址数量在一定范围，如只有几千，完全也可以用哈希。
3、内存消耗
对内存要求严格的地方，如嵌入式系统，用红黑树。红黑树占用的内存更小（仅需要为其存在的节点分配内存），而哈希事先就应该分配足够的内存存储散列表，浪费内存。
对内存消耗无所谓的地方，如服务器有巨大的内存，用哈希。哈希最大的缺点是内存分配得小，可能元素就会冲突，冲突的元素大于8个成链表，效率还不如红黑树。 Java 的hashmap就是把哈希和红黑树结合在以前的。当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树。
4 复杂程度
哈希更简单，红黑树算法复杂一点，不过这都不是事，大神早开源了很多稳定的版本。
三、应用场景总结
红黑树是有序的，哈希是无序的，根据项目需求来选择，阿里巴巴的很多项目用红黑树更多，笔者认为主要还是和内存有关，如果内存要求苛刻的项目，就用红黑树；如果内存足够大，牺牲内存换取更快的速度，哈希完全适合。
himqtt开源版大量采用哈希算法，可能和速度并发要求有关。总之，数据结构是物联网安全最基础的学科。
|
|
|---|---|
|
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 17层才能达到10万级别的容量，从这个树里查找一个字符串，通常情况估计要10次左右的字符串比较，有另外一个算法，性能和内存都碾压红黑树：https://linux.thai.net/~thep/datrie/datrie.html |
|
看了楼主产品介绍感觉对ai有兴趣，想问一些楼主关于研究ai流量检测一些问题:1.用什么中间语言去填写矩阵数据。看了几篇文章，目前我是想采用cws的log行为监控或者翻译成十六进制字符串去建立中间语言，问题是如果是oday的话，那些log日志行为监控输出的信息可能不可靠,因为有些函数是你监控不到。如果翻译成十六进制字符串，那么怎么截取才好呢。2.因数据少目前用的是DPCNN瘦身版防止过拟合，但也最多也只能到9成准确率。 |
|
是的，我一直在研究AI，就目前来说， AI就像大猩猩，智力很低，比如识别一些图片都很费力。 而黑客攻击和0day漏洞，即使是人类，不是学这个专业的，怎么教也教不会，何况是机器。 AI最不可能取代的就是网络安全行业， 至于中间语言更不能复杂，否则安全专家一眼就知道是攻击，转换成中间语言了，人类也识别不了。 网络安全，坚持最小化原则 + 异常检测 是正道，人工智能在网络安全上，还有很长的路要走。 |
|
|
trie树，实际上是hash树的一种变种，其特点是快，但内存消耗很大。 我个人在服务器上，不严格要求内存的地方很喜欢用hash， 但是嵌入式设备 就不行了。 |
|
|
LZ不仔细看看就下结论啦。。Double-Array Trie，它是通过2个数组保存trie树，所以又叫"双数组"，可以"见缝插针"，避免了普通trie树中容易存在大量空闲结点的问题，而且比如"1234567AAA"、"1234567BBB"这2个字符串，由于公共的"1234566"只占一份内存，所以假设用一个.txt文件保存了10万条url，大小为S，用这10万条url构造成的双数组trie，大小往往比S还小。性能的话，不管树中有多少条url，查询1条url永远只需要1次匹配。感兴趣的话，可以花时间看看，顺便看看别人是怎么描述算法的。另外还有个你不喜欢听的建议，红黑树本身就很复杂了，你没描述清楚也就算了，就别再搞个标题吓人了。。 |
返回
如有侵权请联系:admin#unsafe.sh