一、散列表是什么

散列表（Hash table），也稱哈希表、哈希映射，是一種以鍵值對形式存儲數據的數據結構，可以支持高效的插入、查找和刪除操作。散列表通過將關鍵字映射到一個固定大小的數組索引來實現快速訪問。

散列表的基本思想是將關鍵字通過一個哈希函數（Hash function）映射到一個固定大小的數組索引上，稱為哈希值（Hash value）。哈希函數將關鍵字轉換為一個整數，然后將其與數組大小取模，得到的余數即為該關鍵字的哈希值。這樣，散列表就將關鍵字映射到了一個固定的位置上，可以直接訪問該位置的數據，從而實現了快速的查找和插入操作。

散列表的關鍵技術是哈希函數的設計。一個好的哈希函數應該滿足以下條件：

散列值應該具有少數性。不同的關鍵字應該映射到不同的位置上，避免沖突。散列值應該具有均勻性。哈希函數應該將關鍵字均勻地分布在散列表中，避免出現熱點，從而保證散列表的高效性。哈希函數應該盡量簡單，以提高計算效率。

常見的哈希函數包括：

直接取模法：將關鍵字直接除以數組大小，取余數作為哈希值。這種方法簡單、快速，但是容易出現沖突，特別是當數組大小和關鍵字之間存在某種特殊的關系時。乘法哈希法：將關鍵字乘以一個常數 A，取其小數部分，再乘以數組大小，取整數部分作為哈希值。這種方法可以有效地減少沖突，但是計算復雜度較高。分離鏈接法：將散列表的每個位置設置為一個鏈表，當發生沖突時，將關鍵字插入到對應位置的鏈表中。這種方法可以有效地避免沖突，但是需要額外的空間存儲鏈表。開放尋址法：當發生沖突時，通過某種方式尋找其他空閑位置，直到找到一個合適的位置為止。這種方法可以減少空間的浪費，但是需要考慮如何解決沖突，避免出現死循環。

延伸閱讀1：什么是數據結構

數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。

數據結構(data structure)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構類型。簡而言之，數據結構是相互之間存在一種或多種特定關系的數據元素的集合，即帶“結構”的數據元素的集合。“結構”就是指數據元素之間存在的關系，分為邏輯結構和存儲結構。

數據的邏輯結構和物理結構是數據結構的兩個密切相關的方面，同一邏輯結構可以對應不同的存儲結構。算法的設計取決于數據的邏輯結構，而算法的實現依賴于指定的存儲結構。