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

CPU寫入表項

當表項由CPU寫入的時候，FPGA只進行讀取（查表）的時候，那么表項的插入就和FPGA沒有什么關系了。唯一要注意的就是表項要有一個CPU的寫接口。以hash表為例，如果hash表在內部ram中，那么該ram就是CPU寫，邏輯讀；如果hash表在DDR中，那只需要給DDR留一個CPU的讀寫接口即可。

FPGA寫入表項

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

hash表的寫入

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

當key6來查表時，如果計算出hash值為3，如果讀取addr3，發現里面已經有key6，所以查表得到的結果是key6命中的；

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

hash鏈表的寫入

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

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

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

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

當有key需要繼續插入時，以此類推。

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

無論是從鏈表頭插入還是鏈表尾插入，都不影響最終結果，可以根據自己設計，選擇相對簡單的實現方案。

總結

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