摘要：文章在簡要介紹散列表工作原理的基礎上，提出了一種分離鏈接散列表的FPGA實現方案，并對方案涉及的各功能模塊實現進行了詳細闡述。
關鍵詞：散列表；FPGA；Wishbone總線；SRAM

0 引言
在軟硬件開發過程中，經常需要通過關鍵字對數據信息進行存儲、查找、刪除等操作，從而實現數據信息的管理。散列表能夠以常數平均時間實現插入、刪除和查找，因此在實現過程中得到廣泛應用。本文基于FPGA設計并實現了一種分離鏈接法解決散列表，利用快速查找緩沖區提高查詢效率，采用空閑存儲區管理模塊實現存儲空間的高效分配及釋放。

1 工作原理
散列表根據設定的散列函數Hash(Key)和處理沖突的方法將一組關鍵字映像到一個有限的連續的地址區間上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置。散列表的實現主要研究兩個問題：散列函數的選取和沖突解決的辦法。
1．1 散列函數選取
一個好的散列函數可以使關鍵字盡量隨機均勻地分布在散列表中，降低沖突發生的概率，提高散列表查找的效率。理想的散列函數對于關鍵字集合中的任一個關鍵字，經散列后映象到地址集合中任何一個地址的概率是相等的。考慮到FPGA實現的效率及復雜度，本文采用了CRC算法作為散列函數，實現關鍵字到散列表地址的映射。
1．2 沖突解決方法
散列表解決沖突的方法主要有開放地址法和分離鏈接法。在開放定址散列算法系統中，如果有沖突發生，那么就要嘗試選擇另外的單元，直到找出空的單元位置。在分離鏈接散列算法系統，通過給新單元分配地址空間，建立鏈表來解決沖突。因為所有的數據都要置于表內，所以開放定址散列法所需要的表要比分離鏈接散列用表大。一般說來，對開放定址散列算法來說，裝填因子應低于0．5。

本文采用分離鏈接法解決散列表存在的沖突，建立如圖1所示散列表存儲結構，每個鏈表首地址存放在FPGA內部的連續RAM中，表元存放在SRAM芯片中。每個表元主要包含關鍵字(Key)、數據(Data)和下一表元地址(Next)，由于關鍵字和下一表元地址字段訪問頻繁，在FPGA實現過程中把這兩個字段置于每個表元的頭部，盡量在一次SRAM的Brust讀／寫操作內完成。

2 FPGA實現
如圖2所示，分離鏈接散列表采用Wishbone總線標準接口與外部組件交互，采用接口控制器實現Wishbone總線管理，采用主控制器生成表元查找、表元添加、表元刪除等模塊的控制信號，采用存儲訪問仲裁器實現各模塊SRAM訪問的分時復用，采用基于內部CAM的快速查找緩沖模塊實現表元地址的快速查找。

2．1 接口控制器
接口控制器作為本模塊與FPGA內部其它功能模塊之間交互的橋梁通道，采用Wishbone總線接口標準。Wishbone總線是由Silicore公司開發的完全免費的片上總線規范，具有靈活、“輕量級”的優點。Wishone采用主／從設備架構，本模塊工作于從設備模式，支持“單次讀／寫”和“塊讀／寫”操作。接口控制器實現以下功能：
(1)根據地址信息的不同，調用不同的功能邏輯處理輸入數據，并返回應答；
(2)把關鍵字(Key)送到Hash運算模塊進行運算；
(3)把命令類型、Hash值、關鍵字按格式送入命令輸入緩沖區；
(4)把待寫入SRAM的數據送入數據輸入緩沖區；
(5)處理狀態讀取命令，返回模塊當前狀態；
(6)處理數據讀取命令，從緩沖區輸出數據、讀取數據并輸出。
2．2 主控制器
主控制器是散列表FPGA實現的核心模塊，循環讀取命令輸入緩沖區中的命令數據，并根據命令類型生成表元查找、表元添加、表元刪除、空閑表元申請、空閑表元釋放及輸入／輸出等請求信號。

(1)主控制器在復位信號失效后，給空閑存儲區管理模塊發送初始化請求，在初始化完成后進入空閑狀態，等待命令輸入緩沖區送入的命令數據；
(2)主控制器在收到查找命令后，給表元查找模塊發送請求，匹配成功則根據命令內容給數據輸入／輸出模塊發送請求，完成數據讀取和寫入，否則完成本次操作返回應答；
(3)主控制器在收到添加命令后，首先查找是否存在關鍵字匹配表元，匹配失敗則向緩沖區管理模塊發送請求獲取空閑表元，成功后根據命令內容給數據輸入／輸出模塊發送請求，完成數據讀取和寫入。
(4)主控制器在收到刪除命令后，首先查找是否存在關鍵字匹配表元，匹配成功則向表元刪除模塊發送請求，并在刪除成功后釋放緩沖區到空閑緩沖區池。