hash算法在FPGA中的实现(4)

在前面的文章中主要介绍了hash表及其链表的结构，以及key值的插入方法，既然有key值的插入，那就有key值的删除，一种删除是CPU通过重新刷新链表来删除，另外一种就是FPGA删除了，这里主要讨论FPGA如何删除链表。

应用场景

什么场景需要删除hash表项呢？其实很多时候是不需要删除表现的，比如最常见的类似bitmap的场景，还有字符串匹配场景等。但是如果hash表项需要老化的时候，就需要删除hash链表了。

比如MAC地址学习建立的MAC地址表，需要在一定的间隔时间内对所有的MAC地址进行一次老化。如果采用hash算法来实现MAC地址表，那就是要删除长期没有匹配的链表节点。我们知道，在链表插入的时候，需要对链表地址进行有效的管理，同理，当链表地址删除后，也需要对链表地址重新管理，这里不讨论具体业务，只讨论在删除链表的时候如何管理链表。

链表的删除

我们先看一个例子，如下图所示，hash桶后面跟了3个链表（链表的删除，和链表实现的方案没有关系）。那如何删除链表呢？

假如我们要删除addr1，删除后的形式如下图所示，只需要修改hash桶中下一链的地址，即把要删除的链表节点addr1中下一链的地址addr2，写回到hansh桶中即可。

但是这里有一个问题，我们链表可以从头链到尾，即可以从上家找到下家，但是没有办法从下家找到上家。要删除的链表节点addr1，知道下一链是addr2，但是它不知道它的上一链在哪里？这里就引出一个新的问题，双向链表。

双向链表

关于什么是双向链表，这里不做解释，网上有很多资料，这里先用一个图来表示，我们把上面有3个链表的图做一个改造，就可以得到双向链表，如下图所示：

每个链表节点包含有2个地址，左边的地址指向上一链，右边的地址指向下一链。比如keyB所在的链表节点，它的下一链地址为addr3，上一链地址为addr1。

再回到开始的问题，假如addr1要被删除掉。我们知道addr1的上一链是NULL，即没有链表，是hash桶，下一链是addr2，所以，我们只需要把addr1的下一链的地址addr2，写入到addr1的上一链hash桶中，同时把add2的上一链指向addr1的上一链即可。

同理，如果要删除addr2的时候，我们只需要把addr2的下一链的地址addr3，写入addr2的上一链addr1中即可，同时把addr3的上一链指向addr2的上一链，即addr1即可，如下图所示：

总结

当需要删除链表的时候，需要做的就是2读2写。

1、分别读出要删除链表addr2的上一链和下一链（读出addr1和addr3的内容）；

2、将要删除链表addr2的上一链地址addr1，写入下一链的上一链地址中；

3、将要删除链表addr2的下一链地址addr3，写入上一链的下一链地址中；

hash在FPGA中的设计已经完全介绍完毕，这些都是一些基础的典型方法，当然肯定还有其他一些更加优秀的方案，欢迎讨论交流。