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

應(yīng)用場(chǎng)景

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

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

鏈表的刪除

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

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

但是這里有一個(gè)問(wèn)題，我們鏈表可以從頭鏈到尾，即可以從上家找到下家，但是沒(méi)有辦法從下家找到上家。要?jiǎng)h除的鏈表節(jié)點(diǎn)addr1，知道下一鏈?zhǔn)莂ddr2，但是它不知道它的上一鏈在哪里？這里就引出一個(gè)新的問(wèn)題，雙向鏈表。

雙向鏈表

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

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

再回到開(kāi)始的問(wèn)題，假如addr1要被刪除掉。我們知道addr1的上一鏈?zhǔn)荖ULL，即沒(méi)有鏈表，是hash桶，下一鏈?zhǔn)莂ddr2，所以，我們只需要把a(bǔ)ddr1的下一鏈的地址addr2，寫入到addr1的上一鏈hash桶中，同時(shí)把a(bǔ)dd2的上一鏈指向addr1的上一鏈即可。

同理，如果要?jiǎng)h除addr2的時(shí)候，我們只需要把a(bǔ)ddr2的下一鏈的地址addr3，寫入addr2的上一鏈addr1中即可，同時(shí)把a(bǔ)ddr3的上一鏈指向addr2的上一鏈，即addr1即可，如下圖所示：

總結(jié)

當(dāng)需要?jiǎng)h除鏈表的時(shí)候，需要做的就是2讀2寫。

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

2、將要?jiǎng)h除鏈表addr2的上一鏈地址addr1，寫入下一鏈的上一鏈地址中；

3、將要?jiǎng)h除鏈表addr2的下一鏈地址addr3，寫入上一鏈的下一鏈地址中；

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