哈希表（Hash table）
哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數(shù)據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
哈希表hashtable(key，value) 就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉換成一個整型數(shù)字即哈希值，然后就將該數(shù)字對數(shù)組長度進行取余，取余結果就當作數(shù)組的下標，將value存儲在以該數(shù)字為下標的數(shù)組空間里。
而當使用哈希表進行查詢的時候，就是再次使用哈希函數(shù)將key轉換為對應的數(shù)組下標，并定位到該空間獲取value，如此一來，就可以充分利用到數(shù)組的定位性能進行數(shù)據定位。
哈希表的本質是一個數(shù)組，數(shù)組中每一個元素稱為一個箱子(bin)，箱子中存放的是鍵值對。數(shù)組長度即箱子數(shù)。
哈希表還有一個重要的屬性: 負載因子(load factor)，它用來衡量哈希表的 空/滿 程度，一定程度上也可以體現(xiàn)查詢的效率，計算公式為:
負載因子 = 總鍵值對數(shù) / 箱子個數(shù)
負載因子越大，意味著哈希表越滿，越容易導致沖突，性能也就越低。因此，一般來說，當負載因子大于某個常數(shù)(可能是 1，或者 0.75 等)時，哈希表將自動擴容。
哈希表在自動擴容時，一般會創(chuàng)建兩倍于原來個數(shù)的箱子，因此即使 key 的哈希值不變，對箱子個數(shù)取余的結果也會發(fā)生改變，因此所有鍵值對的存放位置都有可能發(fā)生改變，這個過程也稱為重哈希(rehash)。
哈希表的擴容并不總是能夠有效解決負載因子過大的問題。假設所有 key 的哈希值都一樣，那么即使擴容以后他們的位置也不會變化。雖然負載因子會降低，但實際存儲在每個箱子中的鏈表長度并不發(fā)生改變，因此也就不能提高哈希表的查詢性能。
基于以上總結，細心的讀者可能會發(fā)現(xiàn)哈希表的兩個問題:
如果哈希表中本來箱子就比較多，擴容時需要重新哈希并移動數(shù)據，性能影響較大。
如果哈希函數(shù)設計不合理，哈希表在極端情況下會變成線性表，性能極低。
時間復雜度
時間復雜度是一個偏理論的概念，我們要描述它，首先需要了解它的描述方法，即：「大 O 表示法」。
其實大 O 表示法的意思挺簡單的，就是表示：隨著輸入的值變化，程序運行所需要的時間與輸入值的變化關系。如果不理解也沒關系，我們看兩行代碼就很容易懂了。
我們先看第一個代碼，這是一個函數(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 呈「線性」關系的。
在時間復雜度中，我們用 O(N) 表示這種「線性」時間復雜度。
那是不是所有的函數(shù)都是「線性」關系的呢？我們再來看下面的程序。這是一個二分查找程序，從一個有序數(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ù)字。所以假如 N = 1024，那么它最多要找多少次呢？答案是 10 次，因為 2^10 = 1024，每次去掉一半，10 次之后就只剩下唯一一個元素了。
好，這個時候，如果元素的個數(shù)翻一倍，變成 2048 個，那么它最多要找多少次呢？相信大家都能算出來吧？答案是 11 次，因為 2 ^ 11 = 2048。
所以在這個例子中，輸入的元素個數(shù)雖然翻倍，但是程序運行所花的時間卻只增加了 1，我們把這種時間復雜度要叫「對數(shù)」時間復雜度，用 O(logN) 來表示。
除了剛剛講的「線性」時間復雜度和「對數(shù)」時間復雜度。我們還有以下這次常見的時間復度數(shù)。
「常數(shù)」時間復雜度，例如返回一個有序數(shù)組中的最小數(shù)，這個數(shù)因為始終在第一個位置，所以就不會受到數(shù)組大小的影響，無論數(shù)組多大，我們都可以在一個固定的時間返回結果。
「線性對數(shù)」時間復雜度，即 O(N*logN)，這個復雜度比較常見，因為常見的高效的排序算法，都是這個時間復雜度，比如快速排序，堆排序，歸并排序等。
別的時間復雜度還有很多，每個具體的問題，我們都可以通過具體的分析，得到這個問題的時間復雜度。
總結一下學習時間復雜度的知識對于我們的工作有什么用：
- 對于不同的數(shù)據規(guī)模，能夠決策采用不同的解決方案。
- 了解什么情況下用暴力解法就能夠解決問題，避免寫復雜的代碼。
- 在寫代碼之前，就能夠預估程序的運行時間，從而可以知道是否能夠滿足產品需求。
4.在程序出現(xiàn)性能瓶頸時，能夠有解決方案而不是抓瞎。
鏈表
鏈式存儲的線性表，簡稱鏈表。鏈表由多個鏈表元素組成，這些元素稱為節(jié)點。結點之間通過邏輯連接，形成鏈式存儲結構。存儲結點的內存單元，可以是連續(xù)的也可以是不連續(xù)的。邏輯連接與物理存儲次序沒有關系。
**鏈表分為兩個域： **
值域：用于存放結點的值
鏈域：用于存放下一個結點的地址或位置
從內存角度出發(fā)： 鏈表可分為 靜態(tài)鏈表、動態(tài)鏈表。
從鏈表存儲方式的角度出發(fā)：鏈表可分為 單鏈表、雙鏈表、以及循環(huán)鏈表。
靜態(tài)鏈表：
把線性表的元素存放在數(shù)組中，這些元素可能在物理上是連續(xù)存放的，也有可能不是連續(xù)的，它們之間通過邏輯關系來連接，數(shù)組單位存放鏈表結點，結點的鏈域指向下一個元素的位置，即下一個元素所在的數(shù)組單元的下標。顯然靜態(tài)鏈表需要數(shù)組來實現(xiàn)。
引出的問題：數(shù)組的長度定義的問題，無法預支。
**動態(tài)鏈表：（實際當中用的最多） **
改善了靜態(tài)鏈表的缺點。它動態(tài)的為節(jié)點分配存儲單元。當有節(jié)點插入時，系統(tǒng)動態(tài)的為結點分配空間。在結點刪除時，應該及時釋放相應的存儲單元，以防止內存泄露。
**單鏈表： **
單鏈表是一種順序存儲的結構。
有一個頭結點，沒有值域，只有連域，專門存放第一個結點的地址。
有一個尾結點，有值域，也有鏈域，鏈域值始終為NULL。
所以，在單鏈表中為找第i個結點或數(shù)據元素，必須先找到第i - 1 結點或數(shù)據元素，而且必須知道頭結點，否者整個鏈表無法訪問。
循環(huán)鏈表：
循環(huán)鏈表，類似于單鏈表，也是一種鏈式存儲結構，循環(huán)鏈表由單鏈表演化過來。單鏈表的最后一個結點的鏈域指向NULL，而循環(huán)鏈表的建立，不要專門的頭結點，讓最后一個結點的鏈域指向鏈表結點。
循環(huán)鏈表與單鏈表的區(qū)別
區(qū)別一、鏈表的建立。單鏈表需要創(chuàng)建一個頭結點，專門存放第一個結點的地址。單鏈表的鏈域指向NULL。而循環(huán)鏈表的建立，不要專門的頭結點，讓最后一個結點的鏈域指向鏈表的頭結點。
區(qū)別二、鏈表表尾的判斷。單鏈表判斷結點是否為表尾結點，只需判斷結點的鏈域值是否是NULL。如果是，則為尾結點；否則不是。而循環(huán)鏈表盤判斷是否為尾結點，則是判斷該節(jié)點的鏈域是不是指向鏈表的頭結點。
