哈希表（Hash table）
哈希表（Hash table辙喂，也叫散列表）捶牢，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說巍耗，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄秋麸，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)炬太，存放記錄的數(shù)組叫做散列表灸蟆。
哈希表hashtable(key，value) 就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個整型數(shù)字即哈希值亲族，然后就將該數(shù)字對數(shù)組長度進(jìn)行取余炒考，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲在以該數(shù)字為下標(biāo)的數(shù)組空間里霎迫。
而當(dāng)使用哈希表進(jìn)行查詢的時候斋枢，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value知给，如此一來杏慰，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位。
哈希表的本質(zhì)是一個數(shù)組炼鞠，數(shù)組中每一個元素稱為一個箱子(bin)，箱子中存放的是鍵值對轰胁。數(shù)組長度即箱子數(shù)谒主。
哈希表還有一個重要的屬性: 負(fù)載因子(load factor)，它用來衡量哈希表的 空/滿 程度赃阀，一定程度上也可以體現(xiàn)查詢的效率霎肯，計算公式為:
負(fù)載因子 = 總鍵值對數(shù) / 箱子個數(shù)
負(fù)載因子越大，意味著哈希表越滿榛斯，越容易導(dǎo)致沖突观游，性能也就越低。因此驮俗，一般來說懂缕，當(dāng)負(fù)載因子大于某個常數(shù)(可能是 1，或者 0.75 等)時王凑，哈希表將自動擴(kuò)容搪柑。
哈希表在自動擴(kuò)容時聋丝，一般會創(chuàng)建兩倍于原來個數(shù)的箱子，因此即使 key 的哈希值不變工碾，對箱子個數(shù)取余的結(jié)果也會發(fā)生改變弱睦，因此所有鍵值對的存放位置都有可能發(fā)生改變，這個過程也稱為重哈希(rehash)渊额。
哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過大的問題况木。假設(shè)所有 key 的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會變化旬迹。雖然負(fù)載因子會降低火惊，但實(shí)際存儲在每個箱子中的鏈表長度并不發(fā)生改變，因此也就不能提高哈希表的查詢性能舱权。
基于以上總結(jié)矗晃，細(xì)心的讀者可能會發(fā)現(xiàn)哈希表的兩個問題:
如果哈希表中本來箱子就比較多，擴(kuò)容時需要重新哈希并移動數(shù)據(jù)宴倍，性能影響較大张症。
如果哈希函數(shù)設(shè)計不合理，哈希表在極端情況下會變成線性表鸵贬，性能極低俗他。
時間復(fù)雜度
時間復(fù)雜度是一個偏理論的概念，我們要描述它阔逼，首先需要了解它的描述方法兆衅，即：「大 O 表示法」。
其實(shí)大 O 表示法的意思挺簡單的嗜浮，就是表示：隨著輸入的值變化羡亩，程序運(yùn)行所需要的時間與輸入值的變化關(guān)系。如果不理解也沒關(guān)系危融，我們看兩行代碼就很容易懂了畏铆。
我們先看第一個代碼，這是一個函數(shù)吉殃，輸入一個數(shù)組辞居，輸出這個數(shù)組里元數(shù)的和。
int count(int a[], int n) {
int result = 0;
for (int i = 0; i < n; ++i) {
result += a[i];
}
return result;
}
對于這個程序來說蛋勺，如果它處理 N 個元素求和所花的時間是 T瓦灶，那么它處理 N2 個元素的和所花的時間就是 T2。所以隨著 N 變大抱完，時間 T 的變大是與 N 呈「線性」關(guān)系的贼陶。
在時間復(fù)雜度中，我們用 O(N) 表示這種「線性」時間復(fù)雜度。
那是不是所有的函數(shù)都是「線性」關(guān)系的呢每界？我們再來看下面的程序捅僵。這是一個二分查找程序，從一個有序數(shù)組中尋找指定的值眨层。
int binary_search(int A[], int key, int imin, int imax)
{
if (imax < imin) {
return KEY_NOT_FOUND;
} else {
int imid = midpoint(imin, imax);
if (A[imid] > key)
return binary_search(A, key, imin, imid - 1);
else if (A[imid] < key)
return binary_search(A, key, imid + 1, imax);
else
return imid;
}
}
對于這個程序來說庙楚，如果它處理 N 個元素求和所花的時間是 T，那么它處理 N 2 個元素的和所花的時間是多少呢趴樱？是 T 2 嗎馒闷？
如果頭腦算不清楚，我們可以拿實(shí)際的數(shù)字來實(shí)驗(yàn)叁征，二分查找每次（幾乎）可以去掉一半的候選數(shù)字纳账。所以假如 N = 1024，那么它最多要找多少次呢捺疼？答案是 10 次疏虫，因?yàn)?2^10 = 1024，每次去掉一半啤呼，10 次之后就只剩下唯一一個元素了卧秘。
好，這個時候官扣，如果元素的個數(shù)翻一倍翅敌，變成 2048 個，那么它最多要找多少次呢惕蹄？相信大家都能算出來吧蚯涮？答案是 11 次，因?yàn)?2 ^ 11 = 2048卖陵。
所以在這個例子中遭顶，輸入的元素個數(shù)雖然翻倍，但是程序運(yùn)行所花的時間卻只增加了 1泪蔫，我們把這種時間復(fù)雜度要叫「對數(shù)」時間復(fù)雜度液肌，用 O(logN) 來表示。
除了剛剛講的「線性」時間復(fù)雜度和「對數(shù)」時間復(fù)雜度鸥滨。我們還有以下這次常見的時間復(fù)度數(shù)。
「常數(shù)」時間復(fù)雜度谤祖，例如返回一個有序數(shù)組中的最小數(shù)婿滓，這個數(shù)因?yàn)槭冀K在第一個位置，所以就不會受到數(shù)組大小的影響粥喜，無論數(shù)組多大凸主，我們都可以在一個固定的時間返回結(jié)果。
「線性對數(shù)」時間復(fù)雜度额湘，即 O(N*logN)卿吐，這個復(fù)雜度比較常見旁舰，因?yàn)槌Ｒ姷母咝У呐判蛩惴ǎ际沁@個時間復(fù)雜度嗡官，比如快速排序箭窜，堆排序，歸并排序等衍腥。
別的時間復(fù)雜度還有很多磺樱，每個具體的問題，我們都可以通過具體的分析婆咸，得到這個問題的時間復(fù)雜度竹捉。
總結(jié)一下學(xué)習(xí)時間復(fù)雜度的知識對于我們的工作有什么用：
- 對于不同的數(shù)據(jù)規(guī)模，能夠決策采用不同的解決方案尚骄。
- 了解什么情況下用暴力解法就能夠解決問題块差，避免寫復(fù)雜的代碼。
- 在寫代碼之前倔丈，就能夠預(yù)估程序的運(yùn)行時間憨闰，從而可以知道是否能夠滿足產(chǎn)品需求。
4.在程序出現(xiàn)性能瓶頸時乃沙，能夠有解決方案而不是抓瞎起趾。
鏈表
鏈?zhǔn)酱鎯Φ木€性表，簡稱鏈表警儒。鏈表由多個鏈表元素組成训裆，這些元素稱為節(jié)點(diǎn)。結(jié)點(diǎn)之間通過邏輯連接蜀铲，形成鏈?zhǔn)酱鎯Y(jié)構(gòu)边琉。存儲結(jié)點(diǎn)的內(nèi)存單元，可以是連續(xù)的也可以是不連續(xù)的记劝。邏輯連接與物理存儲次序沒有關(guān)系变姨。
**鏈表分為兩個域： **
值域：用于存放結(jié)點(diǎn)的值
鏈域：用于存放下一個結(jié)點(diǎn)的地址或位置
從內(nèi)存角度出發(fā)： 鏈表可分為 靜態(tài)鏈表、動態(tài)鏈表厌丑。
從鏈表存儲方式的角度出發(fā)：鏈表可分為 單鏈表定欧、雙鏈表、以及循環(huán)鏈表怒竿。
靜態(tài)鏈表：
把線性表的元素存放在數(shù)組中砍鸠，這些元素可能在物理上是連續(xù)存放的，也有可能不是連續(xù)的耕驰，它們之間通過邏輯關(guān)系來連接爷辱，數(shù)組單位存放鏈表結(jié)點(diǎn)，結(jié)點(diǎn)的鏈域指向下一個元素的位置，即下一個元素所在的數(shù)組單元的下標(biāo)饭弓。顯然靜態(tài)鏈表需要數(shù)組來實(shí)現(xiàn)双饥。
引出的問題：數(shù)組的長度定義的問題，無法預(yù)支弟断。
**動態(tài)鏈表：（實(shí)際當(dāng)中用的最多） **
改善了靜態(tài)鏈表的缺點(diǎn)咏花。它動態(tài)的為節(jié)點(diǎn)分配存儲單元。當(dāng)有節(jié)點(diǎn)插入時夫嗓，系統(tǒng)動態(tài)的為結(jié)點(diǎn)分配空間迟螺。在結(jié)點(diǎn)刪除時，應(yīng)該及時釋放相應(yīng)的存儲單元舍咖，以防止內(nèi)存泄露矩父。
**單鏈表： **
單鏈表是一種順序存儲的結(jié)構(gòu)。
有一個頭結(jié)點(diǎn)排霉，沒有值域窍株，只有連域，專門存放第一個結(jié)點(diǎn)的地址攻柠。
有一個尾結(jié)點(diǎn)球订，有值域，也有鏈域瑰钮，鏈域值始終為NULL冒滩。
所以，在單鏈表中為找第i個結(jié)點(diǎn)或數(shù)據(jù)元素浪谴，必須先找到第i - 1 結(jié)點(diǎn)或數(shù)據(jù)元素开睡，而且必須知道頭結(jié)點(diǎn)，否者整個鏈表無法訪問苟耻。
循環(huán)鏈表：
循環(huán)鏈表篇恒，類似于單鏈表，也是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)凶杖，循環(huán)鏈表由單鏈表演化過來胁艰。單鏈表的最后一個結(jié)點(diǎn)的鏈域指向NULL，而循環(huán)鏈表的建立智蝠，不要專門的頭結(jié)點(diǎn)腾么，讓最后一個結(jié)點(diǎn)的鏈域指向鏈表結(jié)點(diǎn)。
循環(huán)鏈表與單鏈表的區(qū)別
區(qū)別一杈湾、鏈表的建立解虱。單鏈表需要創(chuàng)建一個頭結(jié)點(diǎn)，專門存放第一個結(jié)點(diǎn)的地址毛秘。單鏈表的鏈域指向NULL。而循環(huán)鏈表的建立，不要專門的頭結(jié)點(diǎn)叫挟，讓最后一個結(jié)點(diǎn)的鏈域指向鏈表的頭結(jié)點(diǎn)艰匙。
區(qū)別二、鏈表表尾的判斷抹恳。單鏈表判斷結(jié)點(diǎn)是否為表尾結(jié)點(diǎn)员凝，只需判斷結(jié)點(diǎn)的鏈域值是否是NULL。如果是奋献，則為尾結(jié)點(diǎn)健霹；否則不是。而循環(huán)鏈表盤判斷是否為尾結(jié)點(diǎn)瓶蚂，則是判斷該節(jié)點(diǎn)的鏈域是不是指向鏈表的頭結(jié)點(diǎn)糖埋。
