關(guān)于我的倉庫

• 這篇文章是我為面試準(zhǔn)備的學(xué)習(xí)總結(jié)中的一篇
• 我將準(zhǔn)備面試中找到的所有學(xué)習(xí)資料，寫的Demo，寫的博客都放在了這個(gè)倉庫里iOS-Engineer-Interview
• 歡迎star????
• 其中的博客在簡書，CSDN都有發(fā)布
• 博客中提到的相關(guān)的代碼Demo可以在倉庫里相應(yīng)的文件夾里找到

前言

• 該系列為學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)與算法之美》的系列學(xué)習(xí)筆記
• 總結(jié)規(guī)律為一周一更，內(nèi)容包括其中的重要知識帶你，以及課后題的解答
• 算法的學(xué)習(xí)學(xué)與刷題并進(jìn)，希望能真正養(yǎng)成解算法題的思維
• LeetCode刷題倉庫：LeetCode-All-In
• 多說無益，你應(yīng)該開始打代碼了

16講二分查找（下）：如何快速定位IP對應(yīng)的省份地址

• 十個(gè)二分九個(gè)錯(cuò)，確實(shí)感觸很深，一個(gè)字，學(xué)

• 唐納德·克努特（Donald E.Knuth）在《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的第3卷《排序和查找》中說到：“盡管第一個(gè)二分查找算法于1946年出現(xiàn)，然而第一個(gè)完全正確的二分查找算法實(shí)現(xiàn)直到1962年才出現(xiàn)?！?/p>

變體一：查找第一個(gè)值等于給定值的元素

503c572dd0f9d734b55f1bd12765c4f8

• hard做法【簡潔】

// 變體一：查找第一個(gè)值等于給定值的元素[hard]
int BinarySearchXH(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] >= value) {
            right = mid - 1;
        } else {
            left = mid + 1;
        } 
    }
    
    if (left < len && arr[left] == value) {
        return left;
    } else {
        return -1;
    }
}
// 其實(shí)這種做法也沒有那么難理解，只是對arr[mid] = value的情況將它視作沒找到，繼續(xù)進(jìn)行二分
// 就和上一章總結(jié)的那樣，如果出現(xiàn)的是return right會返回最接近那個(gè)，這里使用的是return left返回的就是第一個(gè)了

• easy做法：

// 變體一：查找第一個(gè)值等于給定值的元素[easy]
int BinarySearchXE(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            if ((mid == 0) || (arr[mid - 1] != value)) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return -1;
}

// 沒啥好說的，很簡單就是對與找到的mid不一定是第一個(gè)，遙往前找
// 這里其實(shí)找到一個(gè)一直往前推也可以，當(dāng)然這樣慢了，沒有二分的優(yōu)越性了

變體二：查找最后一個(gè)值等于給定值的元素

• 這題目好劃。。。

// 變體二：查找最后一個(gè)值等于給定值的元素
int BinarySearchY(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            if ((mid == len - 1) || (arr[mid + 1] != value)) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return -1;
}

變體三：查找第一個(gè)大于等于給定值的元素

• 感覺老師確實(shí)有一手
• 對于這類題目，我以前可以會在原二分基礎(chǔ)上修修改改碰碰運(yùn)氣，但是老師給了個(gè)其實(shí)還是可以按照二分的思路一點(diǎn)點(diǎn)的看

// 變體三：查找第一個(gè)大于等于給定值的元素
int BinarySearchZ(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] >= value) {
            if ((mid == 0) || (arr[mid - 1] < value)) {
                return mid;
            } else {
                right = mid - 1;
            }
        } else {
            left = mid + 1;
        }
    }   
    return -1;
}

變體四：查找最后一個(gè)小于等于給定值的元素

• 劃水呀 劃水呀

// 變體四：查找最后一個(gè)小于等于給定值的元素
int BinarySearchZA(vector<int> &arr, int value) {
    
    int len = arr.size();
    int left = 0;
    int right = len - 1;
    int mid = left + ((right - left) >> 1);
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (arr[mid] > value) {
            right = mid - 1;
        } else {
            if ((mid == len - 1) || (arr[mid + 1] > value)) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return -1;
}

開篇題目：如何快速定位出一個(gè)IP地址的歸屬地？

• 當(dāng)我們想要查詢202.102.133.13這個(gè)IP地址的歸屬地時(shí)，我們就在地址庫中搜索，發(fā)現(xiàn)這個(gè)IP地址落在[202.102.133.0, 202.102.133.255]這個(gè)地址范圍內(nèi)，那我們就可以將這個(gè)IP地址范圍對應(yīng)的歸屬地“山東東營市”顯示給用戶了。

[202.102.133.0, 202.102.133.255]  山東東營市 
[202.102.135.0, 202.102.136.255]  山東煙臺 
[202.102.156.34, 202.102.157.255] 山東青島 
[202.102.48.0, 202.102.48.255] 江蘇宿遷 
[202.102.49.15, 202.102.51.251] 江蘇泰州 
[202.102.56.0, 202.102.56.255] 江蘇連云港

• 當(dāng)我們要查詢某個(gè)IP歸屬地時(shí)，我們可以先通過二分查找，找到最后一個(gè)起始IP小于等于這個(gè)IP的IP區(qū)間，然后，檢查這個(gè)IP是否在這個(gè)IP區(qū)間內(nèi)，如果在，我們就取出對應(yīng)的歸屬地顯示；如果不在，就返回未查找到。

課后題：LeetCode 33 搜索旋轉(zhuǎn)有序數(shù)組

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。

搜索一個(gè)給定的目標(biāo)值，如果數(shù)組中存在這個(gè)目標(biāo)值，則返回它的索引，否則返回 -1 。

你可以假設(shè)數(shù)組中不存在重復(fù)的元素。

你的算法時(shí)間復(fù)雜度必須是 O(log n) 級別。

示例 1:

輸入: nums = [4,5,6,7,0,1,2], target = 0
輸出: 4
示例 2:

輸入: nums = [4,5,6,7,0,1,2], target = 3
輸出: -1

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
};

• 其實(shí)也很簡單，就是找有序的那段進(jìn)行判斷，不在里面就分另一段

17講跳表：為什么Redis一定要用跳表來實(shí)現(xiàn)有序集合

• 這個(gè)很新鮮啊，跳表，不說了哦，學(xué)
• 但是它確實(shí)是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以支持快速的插入、刪除、查找操作，寫起來也不復(fù)雜，甚至可以替代（Red-black tree）

理解跳表

• 先看原始單鏈表數(shù)據(jù)

e18303fcedc068e5a168de04df956f6d

• 下一步我們是每兩個(gè)節(jié)點(diǎn)中提取一個(gè)座位索引放在索引層

14753c824a5ee4a976ea799727adc78e

• 現(xiàn)在假如我們要查找一個(gè)16，在索引層發(fā)現(xiàn)在13 17之間，我們就會從13下降到原始鏈表層，在原始鏈表層繼續(xù)查找，就找到16了

• 當(dāng)然一層看到不夠，我們會繼續(xù)往上建，直到索引層只剩2，3個(gè)索引值

492206afe5e2fef9f683c7cff83afa65

• 現(xiàn)在，我們來看下假如查找一個(gè)64個(gè)節(jié)點(diǎn)的鏈表的，我們只需要經(jīng)過幾個(gè)節(jié)點(diǎn)呢？

46d283cd82c987153b3fe0c76dfba8a9

• 好快！

跳表的優(yōu)越性

• 第k級索引的結(jié)點(diǎn)個(gè)數(shù)是第k-1級索引的結(jié)點(diǎn)個(gè)數(shù)的1/2，那第k級索引結(jié)點(diǎn)的個(gè)數(shù)就是n/(2k)。
• 在每一級，注意是每一級，都最多只要經(jīng)過三個(gè)節(jié)點(diǎn)就能遍歷完

d03bef9a64a0368e6a0d23ace8bd450c

• 此時(shí)我們實(shí)現(xiàn)了查找任意數(shù)據(jù)的時(shí)間復(fù)雜度為O(logn)，在單鏈表中實(shí)現(xiàn)了二分查找，空間換時(shí)間計(jì)劃通?
• 空間復(fù)雜度O(n)

跳表的操作

• 我們看一個(gè)插入數(shù)據(jù)的操作，插入一個(gè)數(shù)據(jù)6

65379f0651bc3a7cfd13ab8694c4d26c

• 這里會出現(xiàn)一個(gè)問題，我們在兩集索引之間插入過多節(jié)點(diǎn)會導(dǎo)致其搜索效率降低，這就還涉及到了跳表索引的動(dòng)態(tài)更新
• 跳表通過隨機(jī)函數(shù)的方式進(jìn)行動(dòng)態(tài)更新，比如每次能生成一個(gè)隨機(jī)數(shù)k，在插入數(shù)據(jù)后，就在第1到k層索引層中插入該數(shù)據(jù)

a861445d0b53fc842f38919365b004a7

• 不要問，問就是已經(jīng)懂了

解答開篇：為什么Redis中的有序集合是通過跳表來實(shí)現(xiàn)的

• 其中，插入、刪除、查找以及迭代輸出有序序列這幾個(gè)操作，紅黑樹也可以完成，時(shí)間復(fù)雜度跟跳表是一樣的。但是，按照區(qū)間來查找數(shù)據(jù)這個(gè)操作，紅黑樹的效率沒有跳表高。
• 對于按照區(qū)間查找數(shù)據(jù)這個(gè)操作，跳表可以做到O(logn)的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了。這樣做非常高效。

課后題：在今天的內(nèi)容中，對于跳表的時(shí)間復(fù)雜度分析，我分析了每兩個(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)作為索引的時(shí)間復(fù)雜度。如果每三個(gè)或者五個(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)作為上級索引，對應(yīng)的在跳表中查詢數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢？

• 如果每三個(gè)或者五個(gè)節(jié)點(diǎn)提取一個(gè)節(jié)點(diǎn)作為上級索引，那么對應(yīng)的查詢數(shù)據(jù)時(shí)間復(fù)雜度，應(yīng)該也還是 O(logn)。
• 假設(shè)每 5 個(gè)節(jié)點(diǎn)提取，那么最高一層有 5 個(gè)節(jié)點(diǎn)，而跳表高度為 log5n，每層最多需要查找 5 個(gè)節(jié)點(diǎn)，即 O(mlogn) 中的 m = 5，最終，時(shí)間復(fù)雜度為 O(logn)。
• 空間復(fù)雜度也還是 O(logn)，雖然省去了一部分索引節(jié)點(diǎn)，但是似乎意義不大。

18講散列表（上）：Word文檔中的單詞拼寫檢查功能是如何實(shí)現(xiàn)的

• 散列即是哈希
• 散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特性，所以散列表其實(shí)就是數(shù)組的一種擴(kuò)展，由數(shù)組演化而來?？梢哉f，如果沒有數(shù)組，就沒有散列表。
• 假如我們用十個(gè)數(shù)字0到9要放到長度為10的數(shù)組里面，那我們只要把對應(yīng)數(shù)字放在相應(yīng)下標(biāo)上即可
• 但是如果我們同樣是存放十個(gè)數(shù)據(jù)，可它的值不是0到9，那就需要我們通過哈希函數(shù)去計(jì)算散列值

92c89a57e21f49d2f14f4424343a2773

散列函數(shù)

• 散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)

• 如果key1 = key2，那hash(key1) == hash(key2)

• 如果key1 ≠ key2，那hash(key1) ≠ hash(key2)

散列沖突

開放尋址法

• 線性探測（Linear Probing）通過散列函數(shù)求出的散列值如果上面已經(jīng)有數(shù)據(jù)了，就繼續(xù)往下搜索，直到找到空閑位置，進(jìn)行插入

5c31a3127cbc00f0c63409bbe1fbd0d5

• 查找時(shí)比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素，如果一直查找到空閑位置，還是沒找到該元素，說明它不在表里。這里我覺得你要分清楚，一般我們哈希表是用來進(jìn)行記錄的，查找是為了判斷該元素是否在表里，比如C++ map里面的find()函數(shù)，也就是說雖然我們已經(jīng)有這個(gè)數(shù)據(jù)了，還要去查找看起來很蠢，但這并不矛盾，我們在意的，僅僅是記錄本身而已

9126b0d33476777e7371b96e676e90ff

• 但這樣還是有個(gè)問題，由于我們會進(jìn)行線性探測，所以的當(dāng)我們刪除數(shù)據(jù)的時(shí)候，如果我們刪除的數(shù)據(jù)時(shí)通過線性探測得出來的，這樣就會出現(xiàn)數(shù)據(jù)本身應(yīng)該算在空閑位置那一塊
• 什么意思呢？就是說如果在刪除數(shù)據(jù)時(shí)，我們簡單的清空元素會導(dǎo)致后面進(jìn)行線性探測的時(shí)候，在查看到該位置時(shí)就認(rèn)做找不到該元素【因?yàn)橐呀?jīng)到空閑位置了】，所以我們要對后面刪除的位置設(shè)置deleted標(biāo)志位

fe7482ba09670cbe05a9dfe4dd49bd1d

• 我們可以將刪除的元素，特殊標(biāo)記為deleted。當(dāng)線性探測查找的時(shí)候，遇到標(biāo)記為deleted的空間，并不是停下來，而是繼續(xù)往下探測。
• 線性探測法其實(shí)存在很大問題。當(dāng)散列表中插入的數(shù)據(jù)越來越多時(shí)，散列沖突發(fā)生的可能性就會越來越大，空閑位置會越來越少，線性探測的時(shí)間就會越來越久。極端情況下，我們可能需要探測整個(gè)散列表，所以最壞情況下的時(shí)間復(fù)雜度為O(n)。同理，在刪除和查找時(shí)，也有可能會線性探測整張散列表，才能找到要查找或者刪除的數(shù)據(jù)
• 二次探測（Quadratic probing）：線性探測每次探測的步長是1，那它探測的下標(biāo)序列就是hash(key)+0，hash(key)+1，hash(key)+2……而二次探測探測的步長就變成了原來的“二次方”，也就是說，它探測的下標(biāo)序列就是hash(key)+0，hash(key)+12，hash(key)+22……
• 雙重散列（Double hashing）：僅要使用一個(gè)散列函數(shù)。我們使用一組散列函數(shù)hash1(key)，hash2(key)，hash3(key)……我們先用第一個(gè)散列函數(shù)，如果計(jì)算得到的存儲位置已經(jīng)被占用，再用第二個(gè)散列函數(shù)，依次類推，直到找到空閑的存儲位置
• 裝載因子（load factor）：表示空位的多少，填入表中的元素個(gè)數(shù)/散列表的長度，裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能會下降

鏈表法

• 每個(gè)“桶（bucket）”或者“槽（slot）”會對應(yīng)一條鏈表，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鏈表中。

a4b77d593e4cb76acb2b0689294ec17f

• 當(dāng)插入的時(shí)候，我們只需要通過散列函數(shù)計(jì)算出對應(yīng)的散列槽位，將其插入到對應(yīng)鏈表中即可，所以插入的時(shí)間復(fù)雜度是O(1)。當(dāng)查找、刪除一個(gè)元素時(shí)，我們同樣通過散列函數(shù)計(jì)算出對應(yīng)的槽，然后遍歷鏈表查找或者刪除
• 這兩個(gè)操作的時(shí)間復(fù)雜度跟鏈表的長度k成正比，也就是O(k)。對于散列比較均勻的散列函數(shù)來說，理論上講，k=n/m，其中n表示散列中數(shù)據(jù)的個(gè)數(shù)，m表示散列表中“槽”的個(gè)數(shù)

解答開篇：Word文檔中單詞拼寫檢查功能是如何實(shí)現(xiàn)的？

• 當(dāng)用戶輸入某個(gè)英文單詞時(shí)，我們拿用戶輸入的單詞去散列表中查找。如果查到，則說明拼寫正確；如果沒有查到，則說明拼寫可能有誤，給予提示。借助散列表這種數(shù)據(jù)結(jié)構(gòu)，我們就可以輕松實(shí)現(xiàn)快速判斷是否存在拼寫錯(cuò)誤

課后題

假設(shè)我們有10萬條URL訪問日志，如何按照訪問次數(shù)給URL排序？

• 遍歷 10 萬條數(shù)據(jù)，以 URL 為 key，訪問次數(shù)為 value，存入散列表，同時(shí)記錄下訪問次數(shù)的最大值 K，時(shí)間復(fù)雜度 O(N)
• 如果 K 不是很大，可以使用桶排序，時(shí)間復(fù)雜度 O(N)。如果 K 非常大（比如大于 10 萬），就使用快速排序，復(fù)雜度 O(NlogN)

有兩個(gè)字符串?dāng)?shù)組，每個(gè)數(shù)組大約有10萬條字符串，如何快速找出兩個(gè)數(shù)組中相同的字符串？

• 以第一個(gè)字符串?dāng)?shù)組構(gòu)建散列表，key 為字符串，value 為出現(xiàn)次數(shù)。再遍歷第二個(gè)字符串?dāng)?shù)組，以字符串為 key 在散列表中查找

19講散列表（中）：如何打造一個(gè)工業(yè)級水平的散列表

• 給力哦，全面邁向工業(yè)化，多快好省搞起來
• 在極端情況下，有些惡意的攻擊者，還有可能通過精心構(gòu)造的數(shù)據(jù)，使得所有的數(shù)據(jù)經(jīng)過散列函數(shù)之后，都散列到同一個(gè)槽里。如果我們使用的是基于鏈表的沖突解決方法，那這個(gè)時(shí)候，散列表就會退化為鏈表，查詢的時(shí)間復(fù)雜度就從O(1)急劇退化為O(n)
• 厲害，還有這樣的攻擊手段
• 這一節(jié)就當(dāng)開開眼吧

散列函數(shù)設(shè)計(jì)

• 散列函數(shù)的設(shè)計(jì)不能太復(fù)雜
• 散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布
• 直接尋址法、平方取中法、折疊法、隨機(jī)數(shù)法等

裝載因子過大

• 當(dāng)裝載因子過大，也就是說表里面基本裝滿的時(shí)候，我們就要考慮動(dòng)態(tài)擴(kuò)容的問題
• 申請一個(gè)更大的空間，把老數(shù)據(jù)搬進(jìn)來

67d12e07a7d673a9c1d14354ad029443

• 插入一個(gè)數(shù)據(jù)，最好情況下，不需要擴(kuò)容，最好時(shí)間復(fù)雜度是O(1)。最壞情況下，散列表裝載因子過高，啟動(dòng)擴(kuò)容，我們需要重新申請內(nèi)存空間，重新計(jì)算哈希位置，并且搬移數(shù)據(jù)，所以時(shí)間復(fù)雜度是O(n)。用攤還分析法，均攤情況下，時(shí)間復(fù)雜度接近最好情況，就是O(1)
• 但在擴(kuò)容時(shí)，不能一次完成，因?yàn)閷⒗蠑?shù)據(jù)搬入新的表需要耗費(fèi)大量時(shí)間，讓用戶等待顯然不合理，所以我們選擇每次執(zhí)行新的插入時(shí)，搬運(yùn)一次老數(shù)據(jù)，將操作均攤下去

6d6736f986ec4b75dabc5472965fb9cb

解決沖突的方法

• 當(dāng)數(shù)據(jù)量比較小、裝載因子小的時(shí)候，適合采用開放尋址法。這也是Java中的ThreadLocalMap使用開放尋址法解決散列沖突的原因
• 鏈表法最差的時(shí)間復(fù)雜度也就O(logn)，并且可以結(jié)合跳表，二叉樹這類數(shù)據(jù)結(jié)構(gòu)

103b84d7173277c5565607b413c40129

• 基于鏈表的散列沖突處理方法比較適合存儲大對象、大數(shù)據(jù)量的散列表，而且，比起開放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如用紅黑樹代替鏈表

以Java中的HashMap為例看工業(yè)級別的散列表實(shí)現(xiàn)

• HashMap默認(rèn)的初始大小是16，當(dāng)然這個(gè)默認(rèn)值是可以設(shè)置的，如果事先知道大概的數(shù)據(jù)量有多大，可以通過修改默認(rèn)初始大小，減少動(dòng)態(tài)擴(kuò)容的次數(shù)，這樣會大大提高HashMap的性能
• 最大裝載因子默認(rèn)是0.75，當(dāng)HashMap中元素個(gè)數(shù)超過0.75*capacity（capacity表示散列表的容量）的時(shí)候，就會啟動(dòng)擴(kuò)容，每次擴(kuò)容都會擴(kuò)容為原來的兩倍大小
• ashMap底層采用鏈表法來解決沖突。即使負(fù)載因子和散列函數(shù)設(shè)計(jì)得再合理，也免不了會出現(xiàn)拉鏈過長的情況，一旦出現(xiàn)拉鏈過長，則會嚴(yán)重影響HashMap的性能。
• 于是，在JDK1.8版本中，為了對HashMap做進(jìn)一步優(yōu)化，我們引入了紅黑樹。而當(dāng)鏈表長度太長（默認(rèn)超過8）時(shí)，鏈表就轉(zhuǎn)換為紅黑樹。我們可以利用紅黑樹快速增刪改查的特點(diǎn)，提高HashMap的性能。當(dāng)紅黑樹結(jié)點(diǎn)個(gè)數(shù)少于8個(gè)的時(shí)候，又會將紅黑樹轉(zhuǎn)化為鏈表。因?yàn)樵跀?shù)據(jù)量較小的情況下，紅黑樹要維護(hù)平衡，比起鏈表來，性能上的優(yōu)勢并不明顯

20講散列表（下）：為什么散列表和鏈表經(jīng)常會一起使用

LRU緩存淘汰算法

• LRU是在講鏈表那一節(jié)就提到的算法
  • 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個(gè)數(shù)據(jù)對應(yīng)的結(jié)點(diǎn)，并將其從原來的位置刪除，然后再插入到鏈表的頭部
  • .如果此數(shù)據(jù)沒有在緩存鏈表中
    • 如果此時(shí)緩存未滿，則將此結(jié)點(diǎn)直接插入到鏈表的頭部
    • 如果此時(shí)緩存已滿，則鏈表尾結(jié)點(diǎn)刪除，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部
• 我們使用散列表鏈表相結(jié)合的方式解決這個(gè)問題

eaefd5f4028cc7d4cfbb56b24ce8ae6e

• 這個(gè)問題其實(shí)翻譯過來就是：我雖然懂散列表是個(gè)什么東西，但我就是想要能有序輸出里面的東西，這就需要我們在散列表+雙向鏈表之外在加一個(gè)拉鏈【hnext】
• 當(dāng)我們查找數(shù)據(jù)的時(shí)候，我們是通過散列表，在順序查找，但當(dāng)我們是添加數(shù)據(jù)的時(shí)候，需要對鏈的頭尾進(jìn)行操作，所以要對鏈進(jìn)行操作
• 添加操作：我們需要先看這個(gè)數(shù)據(jù)是否已經(jīng)在緩存中。如果已經(jīng)在其中，需要將其移動(dòng)到雙向鏈表的尾部；如果不在其中，還要看緩存有沒有滿。如果滿了，則將雙向鏈表頭部的結(jié)點(diǎn)刪除，然后再將數(shù)據(jù)放到鏈表的尾部；如果沒有滿，就直接將數(shù)據(jù)放到鏈表的尾部

Redis有序集合

• 這一塊感覺么得意思，鴿了

Java LinkedHashMap

• 這一塊和上面的LRU算法一樣，同樣是通過雙向鏈表+散列來實(shí)現(xiàn)的
• 插入的2會出現(xiàn)在鏈表的末尾

17ac41d9dac454e454dcb289100bf198

• 此時(shí)如果我們要插入新的3數(shù)據(jù)，會把舊的刪除，新的放最后

fe313ed327bcf234c73ba738d975b18c

• 照訪問時(shí)間排序的LinkedHashMap本身就是一個(gè)支持LRU緩存淘汰策略的緩存系統(tǒng)
• LinkedHashMap是通過雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的。LinkedHashMap中的“Linked”實(shí)際上是指的是雙向鏈表，并非指用鏈表法解決散列沖突

課后題

今天講的幾個(gè)散列表和鏈表結(jié)合使用的例子里，我們用的都是雙向鏈表。如果把雙向鏈表改成單鏈表，還能否正常工作呢？為什么呢？

• 在刪除一個(gè)元素時(shí)，雖然能 O(1) 的找到目標(biāo)結(jié)點(diǎn)，但是要?jiǎng)h除該結(jié)點(diǎn)需要拿到前一個(gè)結(jié)點(diǎn)的指針，遍歷到前一個(gè)結(jié)點(diǎn)復(fù)雜度會變?yōu)?O(N），所以用雙鏈表實(shí)現(xiàn)比較合適。

獵頭系統(tǒng)設(shè)計(jì)

• 根據(jù)獵頭的ID快速查找、刪除、更新這個(gè)獵頭的積分信息
• 查找積分在某個(gè)區(qū)間的獵頭ID列表
• 查找按照積分從小到大排名在第x位到第y位之間的獵頭ID列表
• 解答：
  • ID 在散列表中所以可以 O(1) 查找到這個(gè)獵頭
  • 積分以跳表存儲，跳表支持區(qū)間查詢
  • 暫時(shí)無解