一、散列表是什么

散列表（Hash table），也稱哈希表、哈希映射，是一種以鍵值對形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，可以支持高效的插入、查找和刪除操作。散列表通過將關(guān)鍵字映射到一個(gè)固定大小的數(shù)組索引來實(shí)現(xiàn)快速訪問。

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

散列表的關(guān)鍵技術(shù)是哈希函數(shù)的設(shè)計(jì)。一個(gè)好的哈希函數(shù)應(yīng)該滿足以下條件：

散列值應(yīng)該具有少數(shù)性。不同的關(guān)鍵字應(yīng)該映射到不同的位置上，避免沖突。散列值應(yīng)該具有均勻性。哈希函數(shù)應(yīng)該將關(guān)鍵字均勻地分布在散列表中，避免出現(xiàn)熱點(diǎn)，從而保證散列表的高效性。哈希函數(shù)應(yīng)該盡量簡單，以提高計(jì)算效率。

常見的哈希函數(shù)包括：

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

延伸閱讀1：什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來的結(jié)構(gòu)類型。簡而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合?！敖Y(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個(gè)密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于指定的存儲(chǔ)結(jié)構(gòu)。