1月9日,在线听RF检波器如何简化系统设计,与ADI工程师一起学习吧!→ 报名参会 ←
电子产品世界 » 论坛首页 » 综合技术 » 物联网技术 » 从物联网防火墙himqtt源码谈哈希和红黑树的应用场景区别

共1条 1/1 1 跳转至

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

菜鸟
2019-11-29 09:58:12    评分

himqtt是首款完整源码的高性能MQTT物联网防火墙 - MQTT Application FireWall,C语言编写,很多数据结构适合初学者收藏。

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

一、哈希和红黑树基本原理

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

1574992635908308.png

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

1574992635693920.png

二、物联网安全使用场景

首先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开源版大量采用哈希算法,可能和速度并发要求有关。总之,数据结构是物联网安全最基础的学科。




关键词: 防火墙     himqtt     源码    

共1条 1/1 1 跳转至

回复

匿名不能发帖!请先 [ 登陆 注册 ]