在計算機科學中，鍊表散列通常是檔案或檔案集中的數據塊的鍊表散列。散列鍊表用於許多不同的目的，例如快速表查找（散鍊表）和分散式資料庫（分散式散鍊表）。本文介紹用於保證數據完整性的鍊表散列。
鍊表散列是散列項目（例如，檔案）的概念的擴展。鍊表散列通常足以滿足大多數需求，但概念的更高級形式是哈希樹。
基本介紹
- 中文名：鍊表散列
- 外文名：Hash list
介紹,鍊表散列的作用,根鍊表散列,
介紹
當散列發生溢出時，鍊表是一種好的解決方法。在散列表的組織中，每個桶僅含有一個節點指針，所有的元素都存儲在該指針所指向的鍊表中。圖給出了散列表在發生溢出時採用鍊表來進行解決的方法。
在搜尋關鍵字值為k的元素時，長度為D，首先要計算其起始桶。起始桶號為k%D，然後搜尋該桶所對應的鍊表。在插入時，首先要保證表中不含有相同關鍵字的元素。當然，此時的搜尋僅限於該元素的起始桶所對應的鍊表。由於每次插入都要首先進行一次搜尋，因此把鍊表按照升序排列比無序排列會更有效。最後，為了刪除關鍵字值為k的元素，首先訪問起始桶對應的鍊表，找到該元素，然後刪除。
鍊表散列的作用
鍊表散列可用於保護在計算機之間和之間存儲，處理和傳輸的任何類型的數據。鍊表散列的一個重要用途是確保從對等網路中的其他對等方接收的數據塊未受損壞且未經更改地接收，並檢查其他對等方是否“謊言”並傳送假塊。
通常，諸如SHA-256的加密散列函式用於散列。如果鍊表散列僅需要防止意外損壞，則可以使用不安全的校驗和（例如CRC）。
散列鍊表優於整個檔案的簡單散列，因為在數據塊損壞的情況下，會注意到這一點，並且只有損壞的塊需要重新載入。只有檔案的散列，許多未損壞的塊必須重新載入，檔案重建並測試，直到獲得整個檔案的正確散列。散列鍊表還可以防止嘗試通過傳送偽塊進行破壞的節點，因為在這種情況下，可以從其他來源獲取損壞的塊。
根鍊表散列
通常，使用散列鍊表本身的附加散列（頂部散列，也稱為根散列或主散列）。 在p2p網路上下載檔案之前，在大多數情況下，從受信任的來源獲取頂級散列，例如，已知具有要下載的檔案的良好推薦的朋友或網站。 當頂部哈希可用時，可以從任何不可信任的源（例如p2p網路中的任何對等體）接收鍊表散列。 然後針對受信任的頂部哈希檢查接收的鍊表散列，並且如果鍊表散列被損壞或偽造，則將嘗試來自另一源的另一鍊表散列，直到程式找到與頂部哈希匹配的鍊表散列。
