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

在前面的文章中主要介紹了hash表及其鏈表的結(jié)構(gòu)，同時說明了如何讀取表項。那表項是如何寫入的了？前期的文章中有少量的提及，這里單獨(dú)寫一篇，介紹兩種常見的方案。

CPU寫入表項

當(dāng)表項由CPU寫入的時候，FPGA只進(jìn)行讀?。ú楸恚┑臅r候，那么表項的插入就和FPGA沒有什么關(guān)系了。唯一要注意的就是表項要有一個CPU的寫接口。以hash表為例，如果hash表在內(nèi)部ram中，那么該ram就是CPU寫，邏輯讀；如果hash表在DDR中，那只需要給DDR留一個CPU的讀寫接口即可。

FPGA寫入表項

FPGA寫入表項的情況相對就要復(fù)雜一些，總體來說，不管什么場景，它都是用key計算hash值，然后查表，命中就返回命中結(jié)果，不命中就把key寫入表中的過程，用一個流程圖表示，如下圖所示：

hash表的寫入

根據(jù)前面hash表的構(gòu)建，我們討論一種情況，hash桶中存放多個key的場景，其他情況都是相似的處理方式。如下表所示：

當(dāng)key6來查表時，如果計算出hash值為3，如果讀取addr3，發(fā)現(xiàn)里面已經(jīng)有key6，所以查表得到的結(jié)果是key6命中的；

當(dāng)key10來查表時，如果計算出的hash值也是3，讀取addr3，發(fā)現(xiàn)里面沒有key10，返回的結(jié)果是不命中，同時還需要把key10和已經(jīng)存在的其他的key一起寫入addr3中，變成如下表：

hash鏈表的寫入

hash鏈表的寫入比hash表的寫入要復(fù)雜，因為除了key的寫入，還涉及到鏈表地址的回寫。以一個具體的例子說明插入鏈表的過程。

假定hash桶的內(nèi)容如下圖所示，此時假定hash桶已經(jīng)滿了，但是還沒有鏈表，hash桶中具體存放什么key，如何存放key不影響hash鏈表的寫入，所以不在這里說明。

現(xiàn)在來了一個keyA，其hash值對應(yīng)到上述hash桶，且沒有命中，由于hash桶已經(jīng)滿了，無法繼續(xù)寫入hash桶中，必須寫入鏈表了。因為將該keyA給到鏈表處理模塊，鏈表處理模塊會返回一個地址，addr1，表示當(dāng)前的keyA，已經(jīng)寫入鏈表，位置在addr1，這時需要把a(bǔ)ddr1這個地址寫回到hash桶中，這樣鏈表才能建立，如下圖所示，這樣在查表的時候，就可以根據(jù)hash桶中的addr1，得到keyA。

同理，如果繼續(xù)來一個keyB，hash值和keyA相同，在進(jìn)行key比較的時候，發(fā)現(xiàn)hash桶中沒有命中，同時鏈表addr1中也沒有命中，即keyB沒有命中，需要寫入hash桶或者h(yuǎn)ash鏈表中。我們在查表的時候得知addr1是最后一鏈（NULL），因此將keyB送給鏈表處理模塊，鏈表處理模塊返回一個地址，假定為addr2，表示keyB已經(jīng)寫入addr2中，這次也需要把地址addr2寫入地址addr1中，實現(xiàn)鏈表在尾部的插入。如下圖所示：

當(dāng)有key需要繼續(xù)插入時，以此類推。

對于鏈表插入的位置，可以在尾部插入外，也可以在頭部插入。當(dāng)鏈表處理模塊返回keyB寫入的地址addr2后，將該地址寫入hash桶中，同時將hash桶中的地址addr1和keyB寫入到addr2中。如下圖所示：

無論是從鏈表頭插入還是鏈表尾插入，都不影響最終結(jié)果，可以根據(jù)自己設(shè)計，選擇相對簡單的實現(xiàn)方案。

總結(jié)

hash鏈表的插入，一般就是CPU寫入和邏輯自己寫入。邏輯寫入的時候，無論hash桶或者鏈表每一鏈的結(jié)構(gòu)如何，都可以采用上述的方式插入鏈表。