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

CPU寫入表項(xiàng)

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

FPGA寫入表項(xiàng)

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

hash表的寫入

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

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

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

hash鏈表的寫入

hash鏈表的寫入比hash表的寫入要復(fù)雜，因?yàn)槌薻ey的寫入，還涉及到鏈表地址的回寫。以一個(gè)具體的例子說明插入鏈表的過程。

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

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

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

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

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

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

總結(jié)

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