【技术】解析查找表算法、应用和实现

随着汽车智能化、网联化的发展，整车系统存在众多数据交换和信息路由。为了快速查找信息，需要使用查找表，对信息进行归类，创建信息查找模型，以便通过模型，可以快速查找到tag所对应的信息内容。

本文ZHIXIN介绍了一些查找表的算法，和硬件电路上容易实现且常用的做法。

基本概念与应用

查找表是用简单的查询操作替换运行时计算的数组的数据结构，以达到快速查找结果，比对数据的目的。查找表广泛应用到生活中的方方面面。

在图像处理中，查找表经常称为LUT（lookup table），通常用于原色校准或gamma校正中，将索引信息与输出值建立联系，使用颜色查找表来确定特定图像所要显示的颜色和强度。

在加密算法AES-128中，对于SBOX的字节代换功能，作为一个常量查找表，把原数据通过SBOX代换成新的数据。采用trie查找方式，比如搜索0x12，把0x12拆成单字词0x1和0x2，先查找0x1，找到对应的行，再通过0x2，找到该行内对应的数据，比如0x12代换数据0xC9。

图1 AES字节查找与代换

查找表LUT按照应用分成两类：静态查找表和动态查找表，两者的主要差别是：动态查找表支持对表信息的插入、删除、更改，具有更强的灵活性和时效性，但会增加查找表维护难度。

图2 查找表分类

静态查找表的模型和内容，不会进行调整和改动。静态查找表适用于数据量较小、不需要频繁修改的场景，如字典、电话簿等。

动态查找表的内容，是可以实时进行调整的。动态查找表适用于数据量较大、需要频繁修改的场景，如数据库、文件系统等。

常见的查找表的算法

1. 顺序查找

顺序查找又叫线性查找，是最基本的查找技术。

查找过程是从表中第一个记录开始，逐一把所有记录和所需查找的内容进行比对。如果比对成功，表示查找顺利完成。如果遍历完，依旧没有相同数据，那么就是比对失败。

图3 顺序查找

该方案在硬件电路中很容易实现，如果数量比较多的话，所需查找的时间会比较长。

2. 分块查找（索引查找）

索引搜索（index search）方法使用了一个索引表以加快搜索速度。索引表中含有数据组的子数据组。搜索从该索引表开始，一旦表中某项匹配上，则搜索继续在有序数据组中进行。

索引表中必须存放该数据表中的某些关键字。

索引查找会适当提高查找的效率，不过制定索引表，需要提前确定索引表规律。比如线性有序，或者使用最大关键字法确定索引分块最大值。

下图4是索引查找，采用最大关键字的方式进行查找。

索引查找根据索引表，从索引地址开始查找，适当避免无效查找。如果整体是按照顺序排列的话，可以更快速的确定查找区间。索引分块内可以无序排列，查找范围固定，速度比较快。

不过对于无序的数据，会难以构建索引表。

3. 折半查找

在计算机科学中，折半搜索（half-interval search），也称二分搜索（binary search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

图5 折半查找

折半查找可以相对快速查找到所需内容，效率提升50%。不过只适合有序的数据排列方式。

4.哈希查找

根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希造表或散列，所得存储位置称为哈希地址或散列地址。

简单来说，就是把原来很长的数据，通过哈希函数，转化成数据量小的哈希地址。查找的时候，同样把数据计算成哈希地址。然后从哈希地址内读取之前保存的数据进行比对。

如下图6，有3个数据输入。0x1234经过哈希算法，得到哈希值为4，那么就把0x1234存入哈希表地址为4的区域。0x55aa经过哈希算法，存到地址1区域，0x7890存到地址2区域。当查找0x1234是否存在，可以通过哈希算法，读取地址4内的数据进行比较。

图6 哈希算法

常用的哈希算法

①直接地址法（直接定址法）取关键字或关键字的某个线性函数值为哈希地址。

即使用简单乘法或加法作为哈希算法，比如下图的：哈希值=原值÷1000

图7 直接地址法

②数字分析法

假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

如下图8所示，提取特定的位数，进行计算。

图8 数字分析法

③平方取中法：取关键字平方后的中间几位为哈希地址。

④折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

⑤除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。

哈希冲突

哈希冲突采用哈希函数计算哈希值，在所难免会因为存在两个原数据计算之后，得到相同哈希值的情况，这就是哈希冲突。比如采用直接地址法，哈希函数为：哈希值=原值÷0x1000

下图0x1212和0x1fff经过哈希算法，哈希值都为0x1，那么该现象成为哈希冲突。

图9 哈希冲突

处理冲突的解决方向

A：使用符合场景的哈希函数，该方式可以减少冲突，但不能避免冲突。

B：采用特殊的哈希冲突处理方法，存放冲突数据：

图10 哈希冲突处理方法

比如下图11，处理开放地址法中的线性探测：

0x1fff和0x1212使用哈希函数为：哈希值=原值÷0x1000，哈希值冲突，采用线性探测方式，寻找未使用空区间来存储数据。最后存放到哈希值0x5内。

图11 哈希冲突处理（开放地址法）

5.CAM查找

CAM是一种特殊的存储器。所谓CAM，即内容寻址存储器。概括地讲，RAM是一个根据地址读、写数据的存储单元，而CAM和RAM恰恰相反，它返回的是与端口数据内容相匹配的地址，如图12所示。CAM的应用也比较广泛，比如在路由器中的地址交换表，CPU的Cache控制器（Tag阵列）等。

图12 普通存储器和CAM存储器

如图13所示，通过对所有数据进行比较的方式，可以查找数据是否存在。CAM存储器在其每个存储单元都包含了一个内嵌的比较逻辑，写入CAM的数据会和其内部存储的每一个数据进行比较，并返回与端口数据相同的所有内部数据的地址。

图13 CAM实现方法

6. LC Trie

LC Trie(Level Compressed Trie)

Trie 树，又称字典树，是一种树形结构，可以用于保存字符串集合，并可在此集合中快速查找字符串。Trie 树中，从根节点到叶子节点的一条路径就代表一个字符串，从根节点到分支节点（非叶子节点）的一条路径就代表某个字符串的前缀，又称前缀树。

LC Trie则是紧凑前缀树，是经过压缩的Trie，具有更快的查找效率。

比如目前有4个IP地址：

使用Trie进行查找，需要先进行抽象出前缀树模型，如下图14。查找的时候按照IP分段，一级一级进行查找。

图14 前缀树模型

如下图15中左边的树模型，黄色单节点只有一个查找结果。

LC Trie模型，通过压缩单分支节点，可以得到紧凑前缀树LC Trie，提升查找的速率。

图15 LC Trie

LC Trie由于构建树模型的比较复杂，对于硬件实现会相对复杂。不过合适长度确定且有规律的查找内容。

智芯查找表应用

智芯自研的CAN路由加速引擎Communicate Engine中，深度使用查找表技术来提升CAN报文处理速度，大大提高整体系统性能。

具体体现在Filter;Route;Sort三种CAN报文处理功能上，如图16所示，优势在于：

1. 提升CAN报文过滤(Filter)的效率；

2. 加速CAN内部路由(Route)终点判定；

3.增加CAN斑纹优先级排序（Sort）速度；

图16 Communicate Engine的查找表应用

小结

使用查找表，可以有效的提高查找效率，查找表的构建算法各有优缺点。根据实际的应用场景和数据内容，选择合理的查找方式，可以事半功倍地实现所需功能。