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

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

hash鏈表說明

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

圖中關于hash鏈表的示意，只是一種簡單的表示，在FPGA的實際設計中，情況往往要復雜得多。

方案1——DDR

有的時候，我們并不知道鏈表到底會有多長，那么自然地會想到用DDR來存放鏈表。如何在DDR里組織數(shù)據(jù)結構呢？一般來講，hash鏈表的數(shù)據(jù)結構如下：

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

這樣的數(shù)據(jù)結構，在DDR中存放的時候，顯然是不高效的。因為每處理一次hash，有多少個鏈表節(jié)點就要讀多少次DDR。我們知道DDR的性能有2個指標，一個是Gbps，一個是Mpps。處理一次hash時讀DDR的次數(shù)越多，處理的hash次數(shù)就會越少，性能就越低，所以我們優(yōu)化鏈表的數(shù)據(jù)結構，降低對DDR的讀取次數(shù)。

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

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

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

方案二——內部RAM

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

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

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

總結

關于上述2種方案，這里做一個簡單的總結。

不管采用哪種方案，高效地組建表項，減少對hash表和鏈表的訪問次數(shù)是hash處理性能的關鍵。