首页
社区
课程
招聘
[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别
发表于: 2019-11-29 09:44 9428

[原创]从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别

2019-11-29 09:44
9428

    上一篇文章我们详细介绍了红黑树,但初学者往往云里雾里,不知道实战项目该用谁,今天笔者就从结合himqtt的源码,从物联网安全角度来对比一下哈希数据结构和红黑树的应用场景。 哈希和红黑树的详细教程很多,本文就不重复了,

    哈希(hash)也称散列,通过散列算法变成固定的输出到数组,所有的线性数据结构中,数组的定位速度最快,因为它可通过数组下标直接定位到相应的数组空间,就不需要一个个查找。


 

    红黑树的自旋是天才的设计,是一种特殊的平衡二叉树数据结构,特点也是从几十万的数据里面几步就能查找到,速度快。


 

    首先github上下载源码,https://github.com/qq4108863/himqtt ,在src\waf目录有hashmap.c和mqtt_rbtree.c ,分别是哈希和红黑树算法。

    物联网可能是数百万设备联网,对高并发要求很大,所以,对网络安全产品第一要求的是性能和速度。总体来说,哈希查找速度会比红黑树快,而且查找速度基本和数据量大小无关,属于常数级别;而RB树的查找速度是log(n)级别。


[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)

收藏
免费 1
支持
分享
最新回复 (5)
雪    币: 3295
活跃值: (10931)
能力值: ( LV9,RANK:240 )
在线值:
发帖
回帖
粉丝
2
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
2019-11-29 10:26
1
雪    币: 1319
活跃值: (1945)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
3
看了楼主产品介绍感觉对ai有兴趣,想问一些楼主关于研究ai流量检测一些问题:1.用什么中间语言去填写矩阵数据。看了几篇文章,目前我是想采用cws的log行为监控或者翻译成十六进制字符串去建立中间语言,问题是如果是oday的话,那些log日志行为监控输出的信息可能不可靠,因为有些函数是你监控不到。如果翻译成十六进制字符串,那么怎么截取才好呢。2.因数据少目前用的是DPCNN瘦身版防止过拟合,但也最多也只能到9成准确率。
2019-11-29 11:25
0
雪    币: 652
活跃值: (106)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
4
是的,我一直在研究AI,就目前来说, AI就像大猩猩,智力很低,比如识别一些图片都很费力。 而黑客攻击和0day漏洞,即使是人类,不是学这个专业的,怎么教也教不会,何况是机器。 AI最不可能取代的就是网络安全行业, 至于中间语言更不能复杂,否则安全专家一眼就知道是攻击,转换成中间语言了,人类也识别不了。 网络安全,坚持最小化原则 + 异常检测 是正道,人工智能在网络安全上,还有很长的路要走。 
2019-11-29 17:01
0
雪    币: 652
活跃值: (106)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
5
trie树,实际上是hash树的一种变种,其特点是快,但内存消耗很大。 我个人在服务器上,不严格要求内存的地方很喜欢用hash, 但是嵌入式设备 就不行了。
2019-11-29 17:08
0
雪    币: 3295
活跃值: (10931)
能力值: ( LV9,RANK:240 )
在线值:
发帖
回帖
粉丝
6
xiaoduoduo 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次匹配。感兴趣的话,可以花时间看看,顺便看看别人是怎么描述算法的。另外还有个你不喜欢听的建议,红黑树本身就很复杂了,你没描述清楚也就算了,就别再搞个标题吓人了。。
2019-11-29 18:34
0
游客
登录 | 注册 方可回帖
返回
//