hash算法在FPGA中的實現(xiàn)(4)

在前面的文章中主要介紹了hash表及其鏈表的結(jié)構(gòu)，以及key值的插入方法，既然有key值的插入，那就有key值的刪除，一種刪除是CPU通過重新刷新鏈表來刪除，另外一種就是FPGA刪除了，這里主要討論FPGA如何刪除鏈表。

應用場景

什么場景需要刪除hash表項呢？其實很多時候是不需要刪除表現(xiàn)的，比如最常見的類似bitmap的場景，還有字符串匹配場景等。但是如果hash表項需要老化的時候，就需要刪除hash鏈表了。

比如MAC地址學習建立的MAC地址表，需要在一定的間隔時間內(nèi)對所有的MAC地址進行一次老化。如果采用hash算法來實現(xiàn)MAC地址表，那就是要刪除長期沒有匹配的鏈表節(jié)點。我們知道，在鏈表插入的時候，需要對鏈表地址進行有效的管理，同理，當鏈表地址刪除后，也需要對鏈表地址重新管理，這里不討論具體業(yè)務，只討論在刪除鏈表的時候如何管理鏈表。

鏈表的刪除

我們先看一個例子，如下圖所示，hash桶后面跟了3個鏈表（鏈表的刪除，和鏈表實現(xiàn)的方案沒有關(guān)系）。那如何刪除鏈表呢？

假如我們要刪除addr1，刪除后的形式如下圖所示，只需要修改hash桶中下一鏈的地址，即把要刪除的鏈表節(jié)點addr1中下一鏈的地址addr2，寫回到hansh桶中即可。

但是這里有一個問題，我們鏈表可以從頭鏈到尾，即可以從上家找到下家，但是沒有辦法從下家找到上家。要刪除的鏈表節(jié)點addr1，知道下一鏈是addr2，但是它不知道它的上一鏈在哪里？這里就引出一個新的問題，雙向鏈表。

雙向鏈表

關(guān)于什么是雙向鏈表，這里不做解釋，網(wǎng)上有很多資料，這里先用一個圖來表示，我們把上面有3個鏈表的圖做一個改造，就可以得到雙向鏈表，如下圖所示：

每個鏈表節(jié)點包含有2個地址，左邊的地址指向上一鏈，右邊的地址指向下一鏈。比如keyB所在的鏈表節(jié)點，它的下一鏈地址為addr3，上一鏈地址為addr1。

再回到開始的問題，假如addr1要被刪除掉。我們知道addr1的上一鏈是NULL，即沒有鏈表，是hash桶，下一鏈是addr2，所以，我們只需要把addr1的下一鏈的地址addr2，寫入到addr1的上一鏈hash桶中，同時把add2的上一鏈指向addr1的上一鏈即可。

同理，如果要刪除addr2的時候，我們只需要把addr2的下一鏈的地址addr3，寫入addr2的上一鏈addr1中即可，同時把addr3的上一鏈指向addr2的上一鏈，即addr1即可，如下圖所示：

總結(jié)

當需要刪除鏈表的時候，需要做的就是2讀2寫。

1、分別讀出要刪除鏈表addr2的上一鏈和下一鏈（讀出addr1和addr3的內(nèi)容）；

2、將要刪除鏈表addr2的上一鏈地址addr1，寫入下一鏈的上一鏈地址中；

3、將要刪除鏈表addr2的下一鏈地址addr3，寫入上一鏈的下一鏈地址中；

hash在FPGA中的設(shè)計已經(jīng)完全介紹完畢，這些都是一些基礎(chǔ)的典型方法，當然肯定還有其他一些更加優(yōu)秀的方案，歡迎討論交流。