在前面的文章中：hash算法在FPGA中的實(shí)現(xiàn)（一）——hash表的組建，記錄了關(guān)于hash表的構(gòu)建，這里記錄另外一個(gè)話題，就是hash鏈表。我們知道，只要有hash的地方，就一定有沖突，關(guān)鍵就看如何解決沖突了。這里介紹兩種常見(jiàn)的設(shè)計(jì)hash鏈表的方案。當(dāng)然，解決hash沖突也不一定就要用鏈表的方法，還有其他方案。

hash鏈表說(shuō)明

首先說(shuō)下什么hash鏈表？還是借用上一篇文章中的圖片來(lái)說(shuō)明這個(gè)問(wèn)題，如下圖所示。hash鏈表是為了解決hash沖突而建立的一種數(shù)據(jù)結(jié)構(gòu)。當(dāng)某個(gè)key計(jì)算出hash值后，對(duì)應(yīng)的hash桶中已經(jīng)有了數(shù)據(jù)，出現(xiàn)了沖突，那這個(gè)時(shí)候就需要用一個(gè)鏈表來(lái)將具體相同hash值的key“鏈”起來(lái)，方便后續(xù)的查詢。

圖中關(guān)于hash鏈表的示意，只是一種簡(jiǎn)單的表示，在FPGA的實(shí)際設(shè)計(jì)中，情況往往要復(fù)雜得多。

方案1——DDR

有的時(shí)候，我們并不知道鏈表到底會(huì)有多長(zhǎng)，那么自然地會(huì)想到用DDR來(lái)存放鏈表。如何在DDR里組織數(shù)據(jù)結(jié)構(gòu)呢？一般來(lái)講，hash鏈表的數(shù)據(jù)結(jié)構(gòu)如下：

hash桶中除了上文所講的數(shù)據(jù)結(jié)構(gòu)外，還有一個(gè)下一鏈的地址addr1，它指向鏈表的一個(gè)節(jié)點(diǎn)，該鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)和hash桶類似，也包括key值和地址，如圖中key A和addr2，對(duì)于由addr2指向的最后一鏈，只有key B和最后一鏈標(biāo)記NULL。

這樣的數(shù)據(jù)結(jié)構(gòu)，在DDR中存放的時(shí)候，顯然是不高效的。因?yàn)槊刻幚硪淮蝖ash，有多少個(gè)鏈表節(jié)點(diǎn)就要讀多少次DDR。我們知道DDR的性能有2個(gè)指標(biāo)，一個(gè)是Gbps，一個(gè)是Mpps。處理一次hash時(shí)讀DDR的次數(shù)越多，處理的hash次數(shù)就會(huì)越少，性能就越低，所以我們優(yōu)化鏈表的數(shù)據(jù)結(jié)構(gòu)，降低對(duì)DDR的讀取次數(shù)。

優(yōu)化的思路和hash桶的數(shù)據(jù)結(jié)構(gòu)類似，如下圖所示：

在一個(gè)節(jié)點(diǎn)中，不再只存放一個(gè)key，上圖示例是存放了5個(gè)key。實(shí)際一次DDR的讀寫，可能最少是128byte或者256byte，以104bit的五元組為key來(lái)計(jì)算，可以存放9個(gè)key。一次可以讀取N個(gè)key，相比以前的鏈表方案，讀DDR的次數(shù)為原來(lái)的N分之一，性能提升N倍。

將這個(gè)話題繼續(xù)引申下，如果hash桶存放在DDR中，那又如何構(gòu)建hash表呢？如果真的需要把hash桶存放在DDR中，hash表的構(gòu)建和hash鏈表的構(gòu)建就是完全一模一樣的了。

方案二——內(nèi)部RAM

如果考慮所有的沖突次數(shù)在一定范圍之內(nèi)，那么可以把所有的鏈表存放在一起，即存放在一個(gè)內(nèi)部的RAM中，實(shí)現(xiàn)對(duì)所有hash桶的鏈表管理。如下圖所示：

以4個(gè)hash桶為例子說(shuō)明鏈表的管理，key1的hash值為0，落入到hash桶0，因此時(shí)hash桶中的指針指向地址0，即addr0，addr0為空，即可以寫入key1在地址0中。同樣key2的hash值也為0，由于addr0中已經(jīng)有數(shù)據(jù)，此時(shí)addr1為空，因此將key2寫入addr1中，同時(shí)把a(bǔ)ddr1寫入key1中的下一鏈，完成鏈表的構(gòu)建。

其他的key值大家可以自行推敲演練。采用這樣的方案，所有的鏈表都存放在一個(gè)ram中，處理沖突的次數(shù)是有限的，相比DDR的方案，還是簡(jiǎn)單一些。

總結(jié)

關(guān)于上述2種方案，這里做一個(gè)簡(jiǎn)單的總結(jié)。

不管采用哪種方案，高效地組建表項(xiàng)，減少對(duì)hash表和鏈表的訪問(wèn)次數(shù)是hash處理性能的關(guān)鍵。