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

hihttps

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

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

哈希和红黑树的详细教程很多，本文就不重复了，但初学者往往云里雾里，不知道实战项目该用谁，今天笔者就从结合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开源版大量采用哈希算法，可能和速度并发要求有关。总之，数据结构是物联网安全最基础的学科。