本章主要介紹線性表的鏈?zhǔn)酱鎯?、散列表的壓縮映射建立量數(shù)據(jù)類型間關(guān)系的作用。

一般條件下散列查找的性能可以媲美順序表的查找，即時間復(fù)雜度O(1)。

動態(tài)鏈表

（一）單鏈表結(jié)點的定義

單鏈表中每個節(jié)點都是一個節(jié)點，不僅要存儲元素值，還要存儲指向下一個元素的指針。可用如下類來表示這樣的節(jié)點：

（二）單鏈表的基本操作（插入、刪除、遍歷、查找）

①插入結(jié)點：

插入時需要先找到第p個節(jié)點的位置（0<=p<=n），因此最壞的時間復(fù)雜度為O(n)。

②刪除結(jié)點：

刪除時需要先找到第p個節(jié)點的位置（0<=p<=n），因此最壞的時間復(fù)雜度為O(n)。

③遍歷鏈表：

遍歷的時間復(fù)雜度為O(n)。

④查找結(jié)點：

查找第p個結(jié)點的時間復(fù)雜度為O(n)。

靜態(tài)鏈表

靜態(tài)鏈表中的指針不是通常意義的指針類型變量，而是存儲一個數(shù)組下標(biāo)的整型變量，通過它可以找到后繼節(jié)點在數(shù)組中的位置，其功能類似于真實的指針。

其結(jié)點定義如下：

但實際上為了簡便，編程上一般使用array<int,2>來作為一個結(jié)點的類型，其中下標(biāo)為0的元素存儲節(jié)點的值，下標(biāo)為1的元素存儲結(jié)點的下一個結(jié)點地址。

在工程項目中，動態(tài)鏈表是最常見的鏈表的實現(xiàn)方法。但是在程序設(shè)計競賽或考試中，由于一般數(shù)據(jù)量是已知的，因此用靜態(tài)鏈表會易于編碼和查找。

雙向鏈表

雙向鏈表既可以向后遍歷，也可以向前遍歷。因此在單鏈表結(jié)點的基礎(chǔ)上增添一個指針域pre即可。雙向鏈表結(jié)點的定義如下：

C++標(biāo)準(zhǔn)庫中l(wèi)ist就是雙向鏈表，因此當(dāng)你獲取list中一個元素的迭代器時，可以快速找到其前驅(qū)和后繼。通常情況下，當(dāng)需要使用鏈表時，都可以用list容器實現(xiàn)相關(guān)功能。

散列表

散列表提供一個數(shù)組，為每個可能的關(guān)鍵字保留一個位置，通過一個轉(zhuǎn)換函數(shù)將關(guān)鍵字轉(zhuǎn)換為一個它在數(shù)組中的下標(biāo)，這個轉(zhuǎn)換函數(shù)稱為散列函數(shù)（或哈希函數(shù)）。理想情況下，也能夠以O(shè)(1)的時間訪問散列表中的任意元素。

（一）散列函數(shù)

散列是一種壓縮映射，其核心思想是將一種類型的關(guān)鍵字通過一個函數(shù)轉(zhuǎn)換成一個整數(shù)，使得這個整數(shù)能夠盡可能地表示這個關(guān)鍵字本身。這個函數(shù)稱為散列函數(shù)或哈希函數(shù)，轉(zhuǎn)換成的整數(shù)稱為該關(guān)鍵字的散列值或哈希值。

常見的散列函數(shù)設(shè)計方法為

?除留余數(shù)法，即將key對一個指定的數(shù)字m（通常取散列表表長）取余數(shù)作為散列值，即：

（二）沖突

當(dāng)對于不同key得到同樣的哈希值時，稱之為沖突或碰撞。設(shè)計的散列函數(shù)應(yīng)當(dāng)盡可能避免沖突，為此散列表的表長通常設(shè)置為一個素數(shù)（例如1e9+7）。

補充：1e9+7是最小的10位素數(shù)，對其取模后可以保證值在int（大概-2e9~2e9）范圍內(nèi)。

?常見的沖突解決方法有：

①開放定址法：，其中hash(key)是散列函數(shù)，m是散列表長,d_i是增量序列，i是已經(jīng)發(fā)生沖突的次數(shù)。增量序列可以有以下取法：

1）當(dāng)時，稱為線性探測法。

2）當(dāng)時，稱為平方探測法。

②再散列法：定義多個散列函數(shù)，若一個散列函數(shù)發(fā)生沖突，則逐一利用其他散列函數(shù)產(chǎn)生新的散列值，直到?jīng)_突不再發(fā)生。

③鏈地址法：將散列到同一位置得到所有元素保存在一個鏈表中。當(dāng)訪問一個元素時，先計算該元素的散列值，然后遍歷其對應(yīng)的單鏈表，查找相應(yīng)元素。當(dāng)需要使用散列表時，通常可以直接C++標(biāo)準(zhǔn)庫中的無序關(guān)聯(lián)容器（unordered_map、unordered_set），此時一般不需要實現(xiàn)這些解決沖突的辦法。

（三）自定義無序關(guān)聯(lián)容器的關(guān)鍵字哈希函數(shù)

無序關(guān)聯(lián)容器的關(guān)鍵字是限制類型的，當(dāng)需要將其他類型作為其關(guān)鍵字時，則要另外定義其哈希函數(shù)。無序容器在創(chuàng)建對象時，可以向它傳遞函數(shù)對象作為額外的參數(shù)，這個函數(shù)對象定義了針對關(guān)鍵字類型對象的哈希函數(shù)，它應(yīng)該返回一個整數(shù)值，建議返回long long類型。

例如：自定義關(guān)鍵字是array<int,2>的unordered_map的哈希函數(shù)代碼模板

選用容器實現(xiàn)哈希表的原則

①關(guān)鍵字能作為數(shù)組下標(biāo)且數(shù)據(jù)規(guī)模較小，使用數(shù)組（vector、array、bitset、C++內(nèi)置數(shù)組）；

②關(guān)鍵字不能作為數(shù)組下標(biāo)，但可以直接作為無序關(guān)聯(lián)容器的鍵，用無序關(guān)聯(lián)容器；

③關(guān)鍵字不能作為無序關(guān)聯(lián)容器的鍵，但能直接作為有序關(guān)聯(lián)容器的鍵，用有序關(guān)聯(lián)容器；

④關(guān)鍵字不能直接做數(shù)組下標(biāo)、有/無序關(guān)聯(lián)容器的鍵，應(yīng)當(dāng)自定義該類型的默認哈希函數(shù)并使用無序關(guān)聯(lián)容器。