前言

僅記錄學習筆記，如有錯誤歡迎指正。

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

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

一致性哈希原理：

key的選擇：盡量種類多

因為一致性Hash算法對于節(jié)點的增減都只需重定位環(huán)空間中的一小部分數(shù)據(jù)，只有部分緩存會失效，不至于將所有壓力都在同一時間集中到后端服務器上，具有較好的容錯性和可擴展性。（增減機器數(shù)據(jù)遷移工作量大大減少）

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

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

題目：

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

思路：

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

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

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

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

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

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

BitMap：

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

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

題目1.

思路：

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

題目2：

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

補充問題：（利用小根堆）

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

題目三：

思路：

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

題目四：

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

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

三、位運算題目：

思路：利用位運算，獲取符號位，判斷a的符號，b的符號，a-b的符號
通過符號來判斷a，b的大小

getMax1方法a-b可能會有溢出，所以有了getMax2（）
為什么能用+來表示if的意思，因為difSab和SameSab是互斥關系！

在這里插入圖片描述

位運算題目二：

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

思路：

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

題目三：

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

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

新聞名稱：左（6）hash，大數(shù)據(jù)，位運算-創(chuàng)新互聯(lián)
標題來源：http://vcdvsql.cn/article18/iigdp.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、品牌網(wǎng)站建設、微信小程序、App設計、虛擬主機、面包屑導航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)