前言

僅記錄學(xué)習(xí)筆記，如有錯(cuò)誤歡迎指正。

建網(wǎng)站原本是網(wǎng)站策劃師、網(wǎng)絡(luò)程序員、網(wǎng)頁(yè)設(shè)計(jì)師等，應(yīng)用各種網(wǎng)絡(luò)程序開發(fā)技術(shù)和網(wǎng)頁(yè)設(shè)計(jì)技術(shù)配合操作的協(xié)同工作。成都創(chuàng)新互聯(lián)專業(yè)提供做網(wǎng)站、網(wǎng)站制作,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站制作(企業(yè)站、響應(yīng)式網(wǎng)站設(shè)計(jì)、電商門戶網(wǎng)站)等服務(wù),從網(wǎng)站深度策劃、搜索引擎友好度優(yōu)化到用戶體驗(yàn)的提升,我們力求做到極致!一、哈希函數(shù)和哈希表：

hash()：
(1) 輸入是無(wú)限的，輸出有限！
(2)相同的輸入，相同的輸出（無(wú)隨機(jī)因子）
(3)不同的輸入，也可能相同的輸出 (hash碰撞，概率極低)
(4)不同的輸入，但是分布具有均勻性

一致性哈希原理：

key的選擇：盡量種類多

因?yàn)橐恢滦訦ash算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，只有部分緩存會(huì)失效，不至于將所有壓力都在同一時(shí)間集中到后端服務(wù)器上，具有較好的容錯(cuò)性和可擴(kuò)展性。（增減機(jī)器數(shù)據(jù)遷移工作量大大減少）

問(wèn)題1：如果機(jī)器數(shù)據(jù)少，怎么把環(huán)均分？ 問(wèn)題2：增減機(jī)器怎么負(fù)載均衡？ 解決方案：虛擬節(jié)點(diǎn)

一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)，一個(gè)實(shí)際物理節(jié)點(diǎn)可以對(duì)應(yīng)多個(gè)虛擬節(jié)點(diǎn)，虛擬節(jié)點(diǎn)越多，hash環(huán)上的節(jié)點(diǎn)就越多，緩存被均勻分布的概率就越大，hash環(huán)傾斜所帶來(lái)的影響就越小，同時(shí)數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射。

題目：

一個(gè)大文件，文件中都是無(wú)符號(hào)的整數(shù)（0-2^32），40億個(gè)數(shù)字，
1g內(nèi)存，返回出現(xiàn)次數(shù)最多的數(shù)字！

思路：

對(duì)于每一個(gè)數(shù)做hash運(yùn)算，取模100，得到100個(gè)文件夾分別存模后的數(shù)據(jù)，
因?yàn)榫鶆蛐?，所以文件中的?shù)字?jǐn)?shù)量基本一致，相同的數(shù)字肯定都在一個(gè)文件中，
之后在對(duì)每個(gè)文件找出現(xiàn)次數(shù)最多數(shù)字，100個(gè)文件找出100個(gè)數(shù)字，再取出現(xiàn)最多的數(shù)字！

布隆過(guò)濾器:（通過(guò)hash計(jì)算值的） 就是bitmap實(shí)現(xiàn)的！

布隆過(guò)濾器優(yōu)缺點(diǎn) :
下圖hash1(key)=1，那么在第2個(gè)格子將0變?yōu)?(數(shù)組是從0開始計(jì)數(shù)的)，hash2(key)=7，那么將第8個(gè)格子置位1，依次類推。

怎么判斷數(shù)據(jù)是否存在？

只要把這個(gè)數(shù)據(jù)的hash值找出來(lái)，去看value是不是1，不是1就肯定不存在，是1就可能存在，還有可能是其他數(shù)據(jù)。

優(yōu)點(diǎn)：優(yōu)點(diǎn)很明顯，二進(jìn)制組成的數(shù)組，占用內(nèi)存極少，并且插入和查詢速度都足夠快。
缺點(diǎn)：隨著數(shù)據(jù)的增加，誤判率會(huì)增加；還有無(wú)法判斷數(shù)據(jù)一定存在；另外還有一個(gè)重要缺點(diǎn)，無(wú)法刪除數(shù)據(jù)。

BitMap：

占用空間1B，很小
用int類型表示bit類型

二、大數(shù)據(jù)類型題目：

題目1.

思路：

法一：
利用磁頻統(tǒng)計(jì)數(shù)量來(lái)定位沒出現(xiàn)的數(shù)字，如果只有3kb，約等于512B,用40億除512=x
然后遍歷40億數(shù)字，用每個(gè)數(shù)字/x 出來(lái)的范圍++，肯定有某個(gè)范圍小于x的數(shù)量。
然后在當(dāng)前范圍內(nèi)用bitmap，存在置為1，再次遍歷 為0的數(shù)字就是不存在的數(shù)據(jù)
法二：
或者利用0~40億二分，最多遍歷32次，把數(shù)字所在區(qū)間找出來(lái)、
然后在當(dāng)前范圍內(nèi)用bitmap，存在置為1，再次遍歷 為0的數(shù)字就是不存在的數(shù)據(jù)

題目2：

法一：把大文件hash后取模為小文件，之后去小文件中統(tǒng)計(jì)重復(fù)的url，匯總
法二：利用布隆過(guò)濾器，每次插入的數(shù)據(jù)的時(shí)候先去查詢是否已經(jīng)存在，存在則保存。（有一定誤判率）

補(bǔ)充問(wèn)題：（利用小根堆）

hash為小文件之后，把各個(gè)文件的內(nèi)容以出現(xiàn)次數(shù)作大根堆處理，然后新增一個(gè)總的大根堆用來(lái)存放各個(gè)小文件的堆頂，此時(shí)彈出總堆的堆頂；
這個(gè)值為所有搜索內(nèi)容的top1，然后看top1來(lái)自于哪個(gè)小文件中，刪除該小文件中的堆頂，重復(fù)以上過(guò)程找出top2，top3.。

題目三：

思路：

可以用位圖，兩位來(lái)表示狀態(tài)，00表示沒出現(xiàn)過(guò)，01表示出現(xiàn)一次，10表示2次，11表示出現(xiàn)2次以上
補(bǔ)充思路：按照題目1的法一，累加前n個(gè)文件的數(shù)量，看第20億左右數(shù)字出現(xiàn)在哪個(gè)文件，然后繼續(xù)分割該文件的內(nèi)容，直到精確找出第20億個(gè)數(shù)字就是中位數(shù)。

題目四：

10g的文件，內(nèi)容為無(wú)序的正整數(shù)，給你5g內(nèi)存，怎么生成一個(gè)新文件，文件內(nèi)容為有序的數(shù)字。(2021Goggle面試題)

建立一個(gè)大根堆去遍歷文件，找出大值小于y的數(shù)字和頻率，寫入另一個(gè)文件，然后y變大，
找出大于之前y，小于當(dāng)前y的數(shù)字，重復(fù)此過(guò)程

三、位運(yùn)算題目：

思路：利用位運(yùn)算，獲取符號(hào)位，判斷a的符號(hào)，b的符號(hào)，a-b的符號(hào)
通過(guò)符號(hào)來(lái)判斷a，b的大小

getMax1方法a-b可能會(huì)有溢出，所以有了getMax2（）
為什么能用+來(lái)表示if的意思，因?yàn)閐ifSab和SameSab是互斥關(guān)系！

在這里插入圖片描述

位運(yùn)算題目二：

判斷一個(gè)32位數(shù)是不是2的冪或者4的冪

思路：

如果是2的冪，那么32位只能有一個(gè)1，如000000…001就是2的0次方
x &（x-1）==0 可以判斷是否只有一個(gè)1
判斷4的冪的前提：首先是2的冪，其次1的位置是在0,2,4,8…位上

題目三：

除法建議自行百度。比較難理解。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：左（6）hash，大數(shù)據(jù)，位運(yùn)算-創(chuàng)新互聯(lián)
文章地址：http://weahome.cn/article/iigdp.html