數(shù)據(jù)結構和算法（三）：二分查找、跳表、散列表、哈希算法

從廣義上來講：數(shù)據(jù)結構就是一組數(shù)據(jù)的存儲結構 ， 算法就是操作數(shù)據(jù)的方法

數(shù)據(jù)結構是為算法服務的，算法是要作用在特定的數(shù)據(jù)結構上的。

10個最常用的數(shù)據(jù)結構：數(shù)組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie樹

10個最常用的算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、字符串匹配算法

本文總結了20個最常用的數(shù)據(jù)結構和算法，不管是應付面試還是工作需要，只要集中精力攻克這20個知識點就足夠了。

數(shù)據(jù)結構和算法（一）：復雜度、數(shù)組、鏈表、棧、隊列的傳送門

數(shù)據(jù)結構和算法（二）：遞歸、排序、通用排序算法的傳送門

數(shù)據(jù)結構和算法（三）：二分查找、跳表、散列表、哈希算法的傳送門

數(shù)據(jù)結構和算法（四）：二叉樹、紅黑樹、遞歸樹、堆和堆排序、堆的應用的傳送門

數(shù)據(jù)結構和算法（五）：圖、深度優(yōu)先搜索和廣度優(yōu)先搜索、字符串匹配算法、Trie樹、AC自動機的傳送門

數(shù)據(jù)結構和算法（六）：貪心算法、分治算法、回溯算法、動態(tài)規(guī)劃、拓撲排序的傳送門

第十一章 二分查找

一、什么是二分查找？
    1. 二分查找是對一個有序的數(shù)據(jù)集合進行查找，通過每次跟區(qū)間中間的元素對比，將待查找的區(qū)間縮小為之前的一半，直到找到元素或者區(qū)間為空為止。
    1. 對于排好序的數(shù)組來說，使用二分查找，查找某個元素的時間復雜度為：O(logn)。第一次查找時區(qū)間大小為n，第二次查找時區(qū)間大小為n/2，第三次查找時區(qū)間大小為n/4，...，第k次查找時區(qū)間為n/(2 ^ k)，最壞情況下第k次的時候區(qū)間變成空了，也就是n/(2^k) = 1，k =log2n，所以時間復雜度為O(logn)。
    1. O(logn)的查找效率非常驚人，有時候甚至比常量級時間復雜度O(1)效率還要高，為什么這么說呢？logn是個非?！翱植馈钡臄?shù)量級，即便n非常大，對應的logn也很小。例如：2的32次方，也就是大約42億，在42億個數(shù)據(jù)中，使用二分查找，最多需要比較32次。而O(1)代表的常數(shù)可能是一個非常大的數(shù)字，例如O(1000)、O(10000)等等，所以常數(shù)級時間復雜度算法有時候還沒有O(logn)級別的執(zhí)行效率高。
二、二分查找的局限性
    1. 二分查找依賴的是順序表結構，簡單來說就是數(shù)組。因為數(shù)組通過下標隨機訪問的時間復雜度為O(1)，而鏈表想要隨機訪問一個數(shù)時間復雜度為O(n)，通過一些系列計算，我們可以分析出來基于鏈表的二分查找時間復雜度為O(n)。
    1. 二分查找針對的是有序數(shù)據(jù)。如果數(shù)組沒有序，那我們就需要先排序，一般排序的時間復雜度最低為O(nlogn)，如果我們針對的是一組靜態(tài)的數(shù)據(jù)，沒有頻繁的插入和刪除，我們可以一次排序，多次二分查找，這樣排序的成本可被均攤，二分查找的邊際成本就會比較低。
    • 但是，如果我們的數(shù)據(jù)集合涉及到頻繁的插入、刪除操作，維護有序的成本都會比較高，所以二分查找只適合于插入、刪除操作不頻繁、一次排序多次查找的場景中。針對動態(tài)變化的的數(shù)據(jù)集合的查找，可以使用二叉樹。
    1. 數(shù)據(jù)量太少不適合二分查找。如果處理的數(shù)據(jù)很少，那就完全沒有必要使用二分查找了，順序遍歷就夠了；當數(shù)據(jù)量比較大時，二分查找的優(yōu)勢才會比較明顯。
    • 但是有一個特例，那就是比較操作特別耗時的時候，此時不管數(shù)據(jù)量大小，都推薦使用二分查找。例如：數(shù)組中存儲的是長度超過300的字符串，如此長的字符串之間的大小比較非常耗時，我們就需要盡可能的減少比較次數(shù)，減少比較次數(shù)就會大大提高性能，這時二分查找就會比順序遍歷更有優(yōu)勢。
    1. 數(shù)據(jù)量太大也不適合二分查找。因為二分查找的底層依賴于數(shù)組，數(shù)組這種數(shù)據(jù)結構為了支持隨機訪問的特性，占用的空間必須是連續(xù)的，對內(nèi)存要求比較苛刻。例如我們有個1G的數(shù)據(jù)要查找，用數(shù)組存儲的話就需要連續(xù)的1G內(nèi)存空間，如果系統(tǒng)剩余的空間都是零散的，不是連續(xù)的，也就無法開辟這樣的數(shù)組了。所以太大的數(shù)據(jù)用數(shù)組存儲就比較吃力，也就不能用二分查找了。
三、簡單二分查找的代碼實現(xiàn)
//二分查找-循環(huán)
var array = [1,2,3,4,5,6,7,8,9,11]
func searchArray(array: Array<NSInteger>,target: NSInteger) -> NSInteger{
    var low = 0
    var hight = array.count - 1
    while low <= hight {
        let middle = (low + hight) / 2
        if target == array[middle]{
            return middle
        }else if target < array[middle]{
            hight = middle - 1
        }else{
            low = middle + 1
        }
    }
    return -1
}
searchArray(array: array, target: 10)
searchArray(array: array, target: 3)

//二分查找-遞歸
func searchInternally(array:Array<NSInteger>,low:NSInteger,high:NSInteger,target:NSInteger) -> NSInteger{
    if low > high{
        return -1;
    }
    let middle = (low + high) / 2
    if array[middle] == target{
        return middle
    }else if array[middle] > target{
        let newHigh = middle - 1
        return searchInternally(array: array, low: low, high: newHigh, target: target)
    }else{
        let newLow = middle + 1
        return searchInternally(array: array, low: newLow, high: high, target: target)
    }
}
func recursionSearch(array:Array<NSInteger>,target:NSInteger) -> NSInteger{
    return searchInternally(array: array, low: 0, high: array.count - 1, target: target)
}

recursionSearch(array: array, target: 10)
recursionSearch(array: array, target: 3)
四、二分查找的四個變體問題
    1. 查找第一個值等于給定值的元素
//二分查找-第一個值等于給定值的元素
var array = [1,2,3,4,5,6,6,6,7,8,9,11]
func searchFistEqual(array:Array<NSInteger>,target:NSInteger) -> NSInteger{
    var low = 0
    var high = array.count - 1
    while low <= high {
        let middle = (low + high) / 2
        if array[middle] > target{
            high = middle - 1
        }else if array[middle] < target{
            low = middle + 1
        }else{
            if middle == 0 || array[middle - 1] != target{
                return middle
            }else{
                high = middle - 1
            }
        }
    }
    return -1
}

let a1 = searchFistEqual(array: array, target: 6)
print(a1)
    1. 查找最后一個值等于給定值的元素
//二分查找-最后一個值等于給定值的元素
var array = [1,2,3,4,5,6,6,6,7,8,9,11]
func searchLastEqual(array:Array<NSInteger>,target:NSInteger) -> NSInteger{
    var low = 0
    var high = array.count - 1
    while low <= high {
        let middle = (low + high) / 2
        if array[middle] > target{
            high = middle - 1
        }else if array[middle] < target{
            low = middle + 1
        }else{
            if (middle == array.count - 1 || array[middle + 1] != target){
                return middle
            }else{
                low = middle + 1
            }
        }
    }
    return -1
}
let a2 = searchLastEqual(array: array, target: 6)
print(a2)
    1. 查找第一個大于等于給定值的元素
//二分查找-查找第一個大于等于給定值的元素
var array3 = [1,2,3,4,5,6,6,6,7,7,8,9,11]
func searchFirstResult(array: Array<NSInteger>,target: NSInteger) -> NSInteger{
    var low = 0
    var high = array.count - 1
    while low <= high {
        let middle = (low + high) / 2
        if(array[middle] >= target){
            if middle == 0 || array[middle - 1] < target{
                return middle
            }else{
                high = middle - 1
            }
        }else{
            low = middle + 1
        }
    }
    return -1
}
let a3 = searchFirstResult(array: array3, target: 7)
print(a3)
    1. 查找最后一個小于等于給定值的元素
//二分查找-查找最后一個小于等于給定值的元素
var array4 = [1,2,3,4,5,6,6,6,7,7,8,9,11]
func searchLastResult(array: Array<NSInteger>,target: NSInteger) -> NSInteger{
    var low = 0
    var high = array.count - 1
    while low <= high {
        let middle = (low + high) / 2
        if array[middle] <= target{
            if middle == array.count - 1 || array[middle + 1] > target{
                return middle
            }else{
                low = middle + 1
            }
        }else{
            high = middle - 1
        }
    }
    return -1
}

let a4 = searchLastResult(array: array4, target: 5)
print(a4)
    1. 一般情況下，凡使用二分查找能解決的，絕大部分我們更傾向于用散列表或者二叉查找樹。即便是二分查找更省內(nèi)存，但是畢竟內(nèi)存如此緊俏的時候不多，那么二分查找真的沒什么作用了嗎? 實際上，二分查找更適合用在“近似”查找問題上，在這類問題上二分查找的優(yōu)勢比較明顯，例如這幾個變體問題，用其他數(shù)據(jù)結構，比如二叉樹、散列表，就比較難以實現(xiàn)了。
五、課后題

第十二章 跳表

我們知道二分查找依賴的是數(shù)組的隨機訪問特性，那么鏈表真的無法使用二分查找了嗎？

一、什么是跳表
    1. 跳表使用了空間換時間的設計思想，通過構建多級索引來提高查詢效率，實現(xiàn)了基于鏈表的“二分查找”，插入、刪除、查找的時間復雜度都是O(logn)。（跳表其實就是鏈表+多級索引，索引占用了更多的內(nèi)存空間，同時索引也提高了提高查找效率）
    1. 跳表的空間復雜度為O(n)，可以通過改變索引構建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。
二、跳表的索引是怎么構建的呢？
    1. 對于一個單鏈表來說，即便鏈表中存儲的數(shù)據(jù)是有序的，查找一個元素也只能從頭開始遍歷，時間復雜度就會很高，是O(n)。
單向鏈表
    1. 為了提高效率，我們像下圖一樣建立一級索引，每兩個節(jié)點提取一個節(jié)點到上一級，提取出來的節(jié)點就構成了索引。圖中的down表示down指針，指向下一級結點。
    • 如下圖，原來查找“16”需要遍歷10個結點，建立1級索引之后，查找16只需要遍歷7個結點了，查詢效率提高了。
第一級索引
    1. 按照上述方式，我們在建立二級索引，查找效率又會提升很多。
    • 如下圖，一級索引的時候查找“16”需要遍歷7個結點，建立二級索引之后，就只需要6個結點了。
二級索引
    1. 由于案例中的數(shù)據(jù)量并不大，所以即便是建立了二級索引，效率提升也不是很明顯，下圖是包含64個結點的鏈表，為它建立五級索引之后，查找效率大幅提高。
    • 原來沒有建立索引時，查找“62”，需要遍歷62個結點，建立五級索引后，只需要遍歷11個結點了，查找效率大幅提高。
五級索引
三、跳表的查詢有多快？
跳表查詢的時間復雜度為O(logn)，這是怎樣計算出來的呢？
    1. 假設一個鏈表一共有n個結點，每兩個結點抽取一個建立一級索引，那么第一級索引的節(jié)點數(shù)量大約為n/2，第二級索引大約有n/4個結點，第三級索引大約有n/8個結點...
    1. 依次類推，第k級索引大約有n/(2k)個結點，已知最高等級索引有2個結點，所以當?shù)趉級索引為最高等級的索引時，即 n/(2k) = 2，k=log2n - 1，在加上原始鏈表這一層之后，整個跳表就有l(wèi)og2n個等級的索引，也可以說跳表的高度為log2n。
    1. 我們在鏈表中查詢某個數(shù)據(jù)時，通過索引查找，不僅需要橫向遍歷每一級，又要一級一級往下走，所以如果每一層都要遍歷m個結點，一共有l(wèi)og2n層，那么總共就需要遍歷m * log2n個結點，時間復雜度也就是O(m * logn)
    1. 我們每兩個結點取一個結點作為索引，那么每一級索引最多只需要遍歷3個結點就可以了，也就是m = 3，所以時間復雜度就變成了O(3 * log2n)，也就是O(logn)。
    1. 從這個分析過程我們可以看出，跳表通過建立索引進行查詢，雖然額外占用了內(nèi)存空間，但是可以大幅提高查找效率，這就是典型的空間換時間的設計思想。
四、跳表額外占用了多大的內(nèi)存空間呢？
    1. 假設鏈表有n個結點，每兩個結點抽取一個建立一級索引，那么第一級索引的節(jié)點數(shù)量大約為n/2，第二級索引大約有n/4個結點，第三級索引大約有n/8個結點...

  • 2.額外使用的節(jié)點個數(shù)為n/2 + n/4 + n/8 + ... + 2，這是一個等比數(shù)列，通過公式求和，我們可以知道總共額外使用了n-2個結點，也就是空間復雜度為O(n)

  • 3.也是就說n個結點的鏈表，每兩個結點抽取一個建立索引，就額外需要大約n個結點存儲索引。為了節(jié)省內(nèi)存空間，我們可以每三個結點或每五個結點，抽取一個建立索引，額外需要的內(nèi)存空間就會變成n/2或n/4.

    1. 但是實際開發(fā)中，大可不必如此在意額外內(nèi)存空間，因為原始鏈表中存放的很可能是很大的對象，而索引結點只需要存儲關鍵值和幾個指針，并不需要存儲對象，所以當對象遠大于索引結點時，索引占用的內(nèi)存空間就可以忽略了。
五、跳表的插入和刪除
跳表插入、刪除查詢的時間復雜度為O(logn)，這是怎樣計算出來的呢？
    1. 在單鏈表中，一旦確認好要插入的位置，那么插入和刪除操作的時間復雜度都是O(1)
    1. 在跳表中，查找某個位置需要O(logn)，之后在進行插入和刪除，所以跳表的插入和刪除時間復雜度也是O(logn)。
六、跳表索引的動態(tài)更新
    1. 當我們不停的往跳表中插入數(shù)據(jù)，如果我們不更新索引，就有可能出現(xiàn)某兩個索引結點中間數(shù)據(jù)非常多，極端情況下，跳表還會退化成鏈表。
    1. 跳表作為一種動態(tài)的數(shù)據(jù)結構，是通過隨機函數(shù)來維護索引和原始鏈表大小之間的平衡的，也就是說，鏈表結點多了，索引結點也就相應增加一點，避免復雜度退化，以及查找、插入、刪除性能下降。
    1. 跳表通過隨機函數(shù)，來決定將這個結點插入到哪幾級索引中，比例隨機生成了3，那么我們就將這個結點插入到第一級索引到第三級索引，這三個等級的索引中。隨機函數(shù)的選擇非常有講究，從概率上要保證跳表的索引大小和數(shù)據(jù)大小的平衡性，不至于讓性能退化。

第十三章 散列表

一、什么是散列表？
    1. 散列表，也叫哈希表，利用了數(shù)組支持下標隨機訪問的特性，通過散列函數(shù)把元素的鍵值key映射為數(shù)組的下標，然后把數(shù)據(jù)存儲在下標對應的位置。按照鍵值key查找數(shù)據(jù)時，只需要用同樣的散列函數(shù)，就可以把key轉(zhuǎn)化為數(shù)組下標，進而從數(shù)組下標的位置取到數(shù)據(jù)，時間復雜度為O(1)。
    1. 散列函數(shù)，在散列表中起到了非常關鍵的作用，它是一個函數(shù)，所以我們可以把它定義為hash(key)，其中key代表元素的鍵值，hash(key)的值代表經(jīng)過散列函數(shù)計算得到的散列值。
散列表來源于數(shù)組，借助散列函數(shù)對數(shù)組進行了擴展.png
    1. 散列函數(shù)的設計非?？季?，需要滿足以下三個條件：
    - (1). 散列函數(shù)計算得出的散列值是一個非負整數(shù)；
    - (2). 如果key1 = key2，那么hash(k1) = hash(k2)；
    - (3). 如果key1 != key2，那么hash(k1) != hash(k2)。
    1. 第一點很好理解，因為數(shù)組下標從0開始的，所以需要非負整數(shù)；第二點也好理解，key相同，那么散列值也應相同；
    • 第三點，看起來合情合理，但是實際情況下，想要找到key不同，散列值一定不同的散列函數(shù)幾乎是不可能的，即便是業(yè)界著名的MD5、SHA、CRC等哈希算法，也無法完全避免這種散列沖突。而且數(shù)組的存儲空間有限，也會加大散列沖突的概率。
二、如何解決散列沖突？

所謂散列沖突，上面也講過了，就是key不同的時候，散列值hash(key)卻意外的相同了。而且再好的散列函數(shù)也無法避免散列沖突，那么應該怎么解決呢? 常用的有兩種解決辦法：開放尋址法、鏈表法

1. 開放尋址法

  • (1). 開放尋址法的核心思想就是：如果出現(xiàn)了散列沖突，我們就重新探測一個空閑位置，插入進去。

  • (2). 那么如何重新探測空閑位置呢？這里介紹一個比較簡單的方法：線性探測，當我們給散列表插入數(shù)據(jù)時，如果發(fā)現(xiàn)存儲位置已經(jīng)被占用了，我們就從當前位置依次往后查找，直到找到空閑位置為止。

  • (3). 探測空閑位置除了線性探測法，還有兩種比較經(jīng)典的探測方法：二次探測法、雙重散列法。

    • 二次探測跟線性探測很相似，線性探測每次探測的步長是1，探測的下標為hash(key) + 0、hash(key) + 1、hash(key) + 2、hash(key) + 3......，而二次探測步長是原來的二次方，探測下標為hash(key) + 02 、hash(key) + 12、hash(key) + 22、hash(key) + 32......

    • 雙重散列法，就是不僅要使用一個散列函數(shù)，而是使用一組散列函數(shù)hash1(key)、hash2(key)、hash3(key)、hash4(key)......，我們先使用第一個散列函數(shù)，如果計算得到的存儲空間被占用了，在用第二個散列函數(shù)，依次類推，知道找到空閑的存儲位置。

  • (4). 不管用哪種探測辦法，當散列表中空閑位置不多時，散列沖突發(fā)生的概率都會大大提高。為了更加直觀的表示散列表中的空閑位置的多少，引入了裝載因子的概念，裝載因子越大，說明空閑位置越少，沖突發(fā)生的概率越大，散列表的性能下降。

//裝載因子用來衡量散列中空閑位置的多少
散列表的裝載因子 = 填入表中的數(shù)據(jù) / 散列表的長度
2. 鏈表法

  • (1). 鏈表法是一種更加常用的散列沖突解決辦法，相比于開發(fā)尋址法，鏈表法要簡單的多，如下圖所示，在散列表中，每個桶（bucket）或者槽（slot）都會對應一條鏈表，所有散列值相同的元素都放在相同的槽位所對應的鏈表中。


    鏈表法

  • (2). 使用鏈表法解決散列沖突的散列表，插入元素的時候，只需要通過散列函數(shù)計算出數(shù)組下標，然后插入到下標所對應的鏈表中即可，所以時間復雜度為O(1)

  • (3). 但是查找和刪除的時間復雜度就跟鏈表長度有關系了，如果鏈表長度是k的話，那么查找和刪除的時間復雜度就是O(k)。如果是散列比較均勻的散列函數(shù)，分到每個槽的數(shù)據(jù)都差不多，平均鏈表長度k就等于數(shù)據(jù)總數(shù)/槽的個數(shù)。

三、如何設計工業(yè)級別的散列表？

散列表的查詢效率不能簡單地說是O(1)，它跟散列函數(shù)、裝載因子、散列沖突都有關系，如果散列函數(shù)設計的不好或者裝載因子過高，都有可能導致散列沖突發(fā)生的概率提高，查詢效率下降。

極端情況下，有些惡意攻擊者，會精心構造數(shù)據(jù)，使所有的數(shù)據(jù)經(jīng)過散列函數(shù)之后，都跳到同一個槽里，如果用鏈表法解決散列沖突，散列表就會退化為鏈表，時間復雜度從O(1)退化到O(n)

如果散列表中有10萬條數(shù)據(jù)，那么退化后的查詢效率就下降了10萬倍，原先只需要0.1秒就可以查詢到，現(xiàn)在需要1萬秒，這樣的查詢操作就會消耗大量CPU或線程資源，導致系統(tǒng)無法響應其他請求，從而達到拒絕服務攻擊(DOS)的目的，這就是散列表碰撞攻擊的基本原理。

那么，如何設計一個可以應對各種異常情況的工業(yè)級別的散列表，避免在散列沖突的
情況下，散列表的性能急劇下降，并且能抵抗散列碰撞攻擊？

1. 工業(yè)級散列表的要求
    1. 支持快速的插入、查詢、刪除操作
    1. 內(nèi)存占用合理，不能浪費過多內(nèi)存空間
    1. 性能穩(wěn)定，極端情況下，散列表的性能也不能退化到無法接受。
2. 如何設計一個合適的散列函數(shù)？
    1. 散列函數(shù)設計的不能太復雜，太復雜勢必會消耗很多計算時間，間接影響了散列表性能。
    1. 散列函數(shù)生成的值要盡可能隨機并且均勻分布，這樣才能最小化散列沖突，即便出現(xiàn)沖突，散列到每個槽里的數(shù)據(jù)也會比較均勻，不會出現(xiàn)某個槽里的數(shù)據(jù)特別多的情況。
    1. 實際工作中，還需要考慮各種因素，包括key的長度、特點、分布，還有散列表的大小。常用的設計方法有：數(shù)據(jù)分析法、直接尋址法、平方取中法、折疊法、隨機數(shù)法等等。
3. 如何設計動態(tài)擴容策略？
    1. 隨著不斷的插入操作，裝載因子不斷擴大，當裝載因子大到一定程度后，散列沖突就會變得不可接受。這個時候我們就需要動態(tài)擴容了，當裝載因子達到一定的閾值的時候，重新申請一個更大的散列表，將數(shù)據(jù)搬移到新的散列表中。
    1. 裝載因子閾值的設置要權衡時間、空間復雜度。如果內(nèi)存不緊張，對執(zhí)行效率要求比較高，就可以適當降低裝載因子閾值；相反，如果內(nèi)存空間緊張，對執(zhí)行效率要求又不高，那么就可以適當增加裝載因子閾值。
    1. 大部分情況下，往散列表中插入一個數(shù)據(jù)都會很快，但是當裝載因子達到閾值之后，需要進行動態(tài)擴容的時候，需要新建一個更大的散列表，并且進行數(shù)據(jù)搬運操作，數(shù)據(jù)搬運的時候還得重新計算哈希值，此時就會非常耗時。

    • 為了避免這種極個別的非常耗時操作，我們一般都會把集中一次的數(shù)據(jù)搬運操作，分散到多次操作中，當裝載因子達到閾值之后，我們申請新的散列表，但并不搬移數(shù)據(jù)，當有新數(shù)據(jù)插入的時候直接插入到新的散列表，并且從舊散列表中搬運一條數(shù)據(jù)到新散列表，沒有集中的搬運操作，就使得每次插入操作都很快了。

    • 這期間的查詢操作，需要先查新的散列表，再查老散列表，通過這樣均攤下來，將以此擴容分攤到多次插入操作中，就可以保證任何情況下插入一個數(shù)據(jù)的時間復雜度都是O(1)了。

4. 如何選擇合適的沖突解決辦法？
    1. 開放尋址法的數(shù)據(jù)都在數(shù)組中，可以有效利用CPU緩存加快查詢速度；但是刪除數(shù)據(jù)比較麻煩，沖突的代價更高，裝載因子的上限不能太大。

    • 開放尋址法的裝載因子不能超過1，接近1時，就會產(chǎn)生大量的散列沖突，導致大量的探測、再散列等，性能會下降很多。

    • 而鏈表法的裝載因子即便變成10，只要散列函數(shù)的值隨機均勻，也就是鏈表的長度長了點而已，還是比順序查找快多了。

總結一下： 當數(shù)據(jù)量較小、裝載因子小的時候，適合采用開放尋址法。
    1. 鏈表法對內(nèi)存利用率較高，對大的裝載因子容忍度更高；但是鏈表的內(nèi)存是零散的，對CPU緩存不友好。
    • 其實我們對鏈表法稍加改造，將鏈表法中的鏈表改成跳表、紅黑樹等更高效的數(shù)據(jù)結構，就會更加高效。這樣的話，即便出現(xiàn)散列沖突，極端情況下，所有的數(shù)據(jù)都進入到一個槽里，退化之后的查詢時間也只不過是O(logn)，這樣就有效的避免了散列碰撞攻擊。
總結一下： 鏈表法更適合于存儲大對象、大數(shù)據(jù)量的散列表，支持更多的優(yōu)化策略，例如用紅黑樹代替鏈表。
四、舉例說明工業(yè)級別的散列表，以JAVA中的HashMap為例
    1. 初始大小，HashMap中的默認初始大小是16，如果事先知道大致數(shù)據(jù)量，就可以通過修改默認大小，減少動態(tài)擴容次數(shù)，提高HashMap性能。
    1. 裝載因子和動態(tài)擴容，HashMap的裝載因子默認是0.75，超過這個閾值，就會啟動動態(tài)擴容，每次擴容都會變成原來大小的2倍。
    1. 散列沖突解決辦法，HashMap底層采用鏈表法解決散列沖突，當鏈表長度過長時，鏈表就會轉(zhuǎn)化成紅黑樹；當紅黑樹結點個數(shù)少于8個時，紅黑樹又會轉(zhuǎn)化為鏈表。
    1. 散列函數(shù)，HashMap的散列函數(shù)并不復雜，追求的是簡單高效、分局均勻，如下所示：
int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}

第十四章 為什么散列表和鏈表經(jīng)常放在一起使用？

一、為什么散列表和鏈表經(jīng)常放在一起使用？
    1. 散列表支持高效的查詢、插入、刪除操作，時間復雜度都是O(1)，但是散列表中的數(shù)據(jù)都是通過散列函數(shù)打亂之后無規(guī)律存放的，也就是說，它無法支持按照某種順序快速的遍歷數(shù)據(jù)。
    1. 因為散列表是動態(tài)數(shù)據(jù)結構，會有很多插入或刪除操作，當我們想按照順序遍歷散列表中的數(shù)據(jù)時，就需要先排序，這樣效率勢必會很低，為了解決這個問題，我們將散列表和鏈表(或者跳表)結合在一起使用。
二、如何將散列表和鏈表組合使用？

以一個插入、刪除、查找時間復雜度均為O(1)的，LRU緩存淘汰算法為例。

    1. 先回顧一下如何用鏈表實現(xiàn)的LRU緩存淘汰算法的

    • (1). 我們需要維護一個訪問時間從大到小有序排列的鏈表結構，因為緩存大小有限，當緩存空間不足時，將鏈表的頭部結點刪除。

    • (2). 當要插入某個數(shù)據(jù)時，先查找鏈表中是否存在，存在的話，就把它移動到鏈表尾部；不存在的話，就直接把它放到鏈表尾部；當要刪除某個數(shù)據(jù)時，先查找到數(shù)據(jù)的位置再刪除它。因為查找數(shù)據(jù)需要遍歷整個鏈表，所以單純用鏈表實現(xiàn)的LRU緩存淘汰算法，插入、刪除、查找的時間復雜度都會很高，均為O(n)。

    • (3). 那么我們?nèi)绾蝺?yōu)化一下這個LRU算法，可以使得插入、刪除、查找的時間復雜度都變成O(1)呢？

    1. 答案就是將散列表和鏈表組合使用

    • (1). 我們使用雙向鏈表存儲數(shù)據(jù)，鏈表中每個節(jié)點都需要存儲：數(shù)據(jù)(data)、前驅(qū)指針(prev)、后繼指針(next)、hnext指針(解決散列沖突用的)

    • (2). 同時呢也使用散列表存儲數(shù)據(jù)（這個散列表使用鏈表法來解決散列沖突），所以每個節(jié)點都會在兩條鏈中。一條是雙向鏈表鏈、一條是散列表的鏈表鏈。前驅(qū)指針和后繼指針是為了將結點串在雙向鏈表中，hnext指針為了將結點串在散列表的鏈表中。最終組合效果如下圖所示：

散列表和雙向鏈表組合使用，以實現(xiàn)高效的LRU
    1. 通過這樣組合使用之后呢，查找一個數(shù)據(jù)可以直接使用散列表查找，時間復雜度就變成了O(1)了，同理刪除和插入的時間復雜度也降低為O(1)了。
總結：鏈表的優(yōu)勢是可以記錄順序，散列表的優(yōu)勢是可以快速查找，兩個結合使用，可以大幅提高效率。

第十五章 哈希算法

一、什么是哈希算法？
    1. 哈希算法的定義非常簡單，一句話就可以概括，將任意長度的二進制值串映射為固定長度的二進制串，這個映射的規(guī)則就是哈希算法，原始數(shù)據(jù)經(jīng)過映射得到的二進制值串，就是哈希值。
    1. 設計一個優(yōu)秀的哈希算法并不容易，一般需要滿足以下條件：

    • 從哈希值不能反向推導出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）

    • 對輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了1Bit，最后得到的哈希值也大不相同。

    • 散列沖突的概率很小，針對不同的原始數(shù)據(jù)進行哈希，得到相同哈希值的概率很小。

    • 哈希算法的執(zhí)行效率要盡量高效，針對較長文本，也能快速計算得出哈希值。

    1. 例如經(jīng)典的MD5哈希算法，即便只有一個字符不同，得到的哈希值也大相庭徑。
MD5(" 我今天講哈希算法！") = 425f0d5a917188d2c3c3dc85b5e4f2cb
MD5(" 我今天講哈希算法 ") = a1fb91ac128e6aa37fe42c663971ac3d
    1. 哈希算法的應用非常多，這了介紹常見的7個應用：安全加密、唯一標識、數(shù)據(jù)校驗、散列函數(shù)、負載均衡、數(shù)據(jù)分片、分布式存儲。
二、哈希算法的應用 - 安全加密
    1. 最常見的用于加密的哈希算法有：MD5(Message-Digest Algorithm,MD5 消息摘要算法) 和 SHA(Secure Hash Algorithm,SHA 安全散列算法)，除此之外，還有很多關于加密的哈希算法，例如DES(Data Encryption Standard，數(shù)據(jù)加密標準）、AES(Advanced Encryption Standard，高級加密標準)
    1. 對于加密的哈希算法而言，有兩點格外重要，第一點是很難通過哈希值反向推導出原始數(shù)據(jù)，第二點是散列沖突概率要小。
    1. 無論再好的哈希算法都無法避免散列沖突，這是為什么呢？這里有一個鴿巢理論，就是說，如果有10個鴿巢，11只鴿子，那么肯定有1個鴿巢中鴿子的數(shù)量超過1只，也就是肯定有1個鴿巢存在至少2只鴿子。
    1. 同理，哈希算法產(chǎn)生的哈希值的長度是固定的且有限的，例如MD5哈希算法，產(chǎn)生的哈希值是固定128位的二進制串，能表示的數(shù)據(jù)是有限的，最多能表示2^128個數(shù)據(jù)，而我們要哈希的數(shù)據(jù)是無窮的，就必然存在哈希值相同的情況。
    1. 沒有絕對安全的加密，越復雜、越難破解的加密方法，所需要的計算時間也就越長。例如SHA-265就比SHA-1更復雜、更安全，響應的計算時間也就會比較長。
三、哈希算法的應用 - 唯一標識
    1. 通過哈希算法，可以將部分數(shù)據(jù)抽取，并進行哈希，作為整體數(shù)據(jù)的唯一標識。
    1. 例如，如何從海量的圖庫中搜索一張圖？我們就可以從圖片的二進制碼串抽取數(shù)據(jù)，從開頭取100個字節(jié)，從中間取100個字節(jié)，從結尾取100個字節(jié)，然后將這300個字節(jié)放在一起，通過哈希算法，生成一個哈希值，作為唯一標識，通過這個唯一標識判斷是否在圖庫中。
    1. 如果想進一步優(yōu)化，我們就可以把圖片的唯一標識和圖片路徑存儲在散列表中，查詢的時候，通過哈希算法對圖片取唯一標識，然后去散列表中查找是否存在；如果不存在，則圖片不在圖庫中；如果存在，就用圖片路徑取到圖片，然后與要對比的圖片一起做全量對比，完全一致，則為同一張圖。
四、哈希算法的應用 - 數(shù)據(jù)校驗
    1. 我們使用BT下載文件時，需要先下載文件的種子，種子里面包含了文件的哈希值，文件下載完畢后，我們對文件進行哈希得到哈希值，與種子中的哈希值進行對比，就可以知道文件是否被篡改過或者缺失過，通過這種方式，我們就可以實現(xiàn)數(shù)據(jù)校驗。
    1. 之所以可以這樣對比，是因為哈希算法有一個特點，就是對數(shù)據(jù)非常敏感，只要文件有一丁點內(nèi)容改變，最后得出的哈希值也會完全不同，所以我們可以利用哈希算法數(shù)據(jù)敏感的特性，來實現(xiàn)數(shù)據(jù)校驗。
五、哈希算法的應用 - 散列函數(shù)
    1. 散列表中的散列函數(shù)，就是哈希算法的一種應用，散列函數(shù)是散列表的關鍵所在，直接決定了散列沖突的概率和散列表的性能。
    1. 散列函數(shù)對是否能反向解密并不關心，更加關心散列后的值是否可以分布均勻；即便出現(xiàn)散列沖突也沒事，只要不太過嚴重，都可以通過開放尋址法和鏈表法解決。
六、哈希算法的應用 - 負載均衡
    1. 如何實現(xiàn)一個會話粘滯的負載均衡算法呢？即同一個客戶端，一次會話中所有的請求都路由到同一個服務器上
    1. 最簡單的方法就是維護一張散列表，散列表中存放客戶端IP地址與服務器編號的映射關系，客戶端每次發(fā)出請求，都需要在映射表中查找服務器編號，再進行請求。這種做法很簡單，但是有幾個缺陷：
    • 如果客戶端很多，那么映射表可能會非常大，比較浪費內(nèi)存空間
    • 如果客戶端上線、下線，映射表擴容、縮容時都會導致映射失敗，需要重新維護映射表。
    1. 借助哈希算法，我們就可以很完美的解決這些問題，我們可以通過哈希算法，對客戶端IP地址計算哈希值，將哈希值與服務器列表的大小進行取模運算，最終得到的值就是應該被路由的服務器編號。這樣，我們就可以做到同一個IP地址過來的所有請求，都路由到同一個后端服務器上了。
七、哈希算法的應用 - 數(shù)據(jù)分片
    1. 如果我們對海量的數(shù)據(jù)進行分析，一臺機器的內(nèi)存不夠用怎么辦？我們可以采用多機分布式處理，對數(shù)據(jù)進行分片，以突破單機內(nèi)存、CPU等資源的限制。具體可以這樣來操作：我們將數(shù)據(jù)通過哈希算法計算出哈希值，與機器總數(shù)n進行取模，得到的值就是應該被分配到的機器編號，就可以將數(shù)據(jù)分配到不同的機器上。
    1. 例如：我們前邊講過的，如何快速判斷圖片是否在圖庫中？就是取圖片的唯一標識與路徑構建散列表。假設我們有1億張圖片，很顯然，所需要的內(nèi)存遠遠超過了單臺機器的上限。
    1. 我們就可以使用數(shù)據(jù)分片，采用多臺機器處理。從圖庫中取一張圖，計算唯一標識，然后與機器總數(shù)n取模，得到的值就是要分配的機器編號，然后將唯一標識和圖片路徑發(fā)往對應的機器構建散列表，這就完成了數(shù)據(jù)分片。
    1. 判斷某張圖是否在圖庫中時，就可以通過同樣的哈希算法，計算出唯一標識，然后與機器總數(shù)n取模，得到機器編號，然后去對應的機器中查詢散列表。
    1. 現(xiàn)在，我們來計算一下，給1億張圖片構建散列表大約需要多少臺機器呢？
    1. 假設我們用MD5計算哈希值，哈希值長度就是128比特，也就是16字節(jié)；文件路徑平均大小是128字節(jié)；用鏈表法解決散列沖突的話，需要存儲指針，指針占用8字節(jié)；所以散列表中的每個數(shù)據(jù)單元大約占用152個字節(jié)。
    1. 假設一臺機器內(nèi)存為2G大小，散列表的裝載因子為0.75，那么一臺機器大概可以給1000萬張圖片構建散列表，2x1024x1024x1024x0.75/152大約為1千萬，1億張圖片大約需要10臺機器。在工程中這種估算還是很重要的，能事先對需要投入的資源、資金有個大概了解，更好的評估解決方案的可行性。
八、哈希算法的應用 - 分布式存儲
    1. 現(xiàn)在的互聯(lián)網(wǎng)都是有海量的數(shù)據(jù)的，而海量的數(shù)據(jù)需要緩存，一個緩存機器肯定是不夠的，所以我們需要將數(shù)據(jù)分布在多臺機器上，這就是分布式存儲的思想。
    1. 我們可以借用數(shù)據(jù)分片的思想，通過哈希算法取到哈希值，然后與機器個數(shù)取模，得到機器編號，將數(shù)據(jù)存儲在對應編號的機器上。但是，這種做法會產(chǎn)生一個問題，就是需要擴容時，就會增加機器數(shù)，這是否取模的結果就會發(fā)生變化，導致所有數(shù)據(jù)請求都會穿透緩存，直接去請求數(shù)據(jù)庫，這樣就可能發(fā)生雪崩效應，壓垮數(shù)據(jù)庫。（例如：有10臺機器，數(shù)據(jù)13與10取模得到3，去3號機器拿緩存數(shù)據(jù)，此時，增加了1臺機器，數(shù)據(jù)13與11取模得到了2，就回去2號機器拿緩存數(shù)據(jù)，拿不到緩存，就會去請求數(shù)據(jù)庫，從而引發(fā)雪崩，所以機器擴容、縮容后，要對數(shù)據(jù)做大量的搬移工作，以避免雪崩）
    1. 但是大量的數(shù)據(jù)遷移費時費力，有沒有辦法可以避免大量的數(shù)據(jù)遷移呢？一致性哈希算法就要登場了。一致性哈希算法可以使我們在新增機器后，不需要大量遷移數(shù)據(jù)。
      這里有個漫畫很好的解釋了一致性哈希算法的原理，可以點擊查看
最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容