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

CPU寫(xiě)入表項(xiàng)

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

FPGA寫(xiě)入表項(xiàng)

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

hash表的寫(xiě)入

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

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

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

hash鏈表的寫(xiě)入

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

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

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

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

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

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

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

總結(jié)

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