哈希表充分體現(xiàn)了算法設(shè)計領(lǐng)域的經(jīng)典思想：空間換時間
哈希函數(shù)
不管是散列還是哈希，這都是中文翻譯的差別重归，英文其實就是 “Hash” 米愿。所以，我們常聽到有人把 “散列表 ” 叫作 “哈希表”“Hash 表 ” 鼻吮，把 “哈希算法 ” 叫作 “Hash 算法” 或者 “散列算法 ”
鍵轉(zhuǎn)換成索引,同時鍵通過哈希函數(shù)得到的索引分布越均勻越好育苟。
原則
1一致性 如果a==b 則hash(a)==hash(b)
2 高效性 計算高效簡單
3 均勻性 哈希值均勻分布
hashcode
整型
小范圍正整數(shù)直接使用
小范圍負(fù)整數(shù)進(jìn)行偏移
大整數(shù)
通常做法取模，也就是取大整數(shù)的后幾位椎木，容易出現(xiàn)分布不均勻宙搬。模一個素數(shù)
字符串
轉(zhuǎn)換成整數(shù)處理
Hash 取模
余數(shù)總是在一個固定的范圍內(nèi)。
整數(shù)是沒有邊界的拓哺，它可能是正無窮勇垛，也可能是負(fù)無窮。但是余數(shù)卻可以通過某 一種關(guān)系士鸥，讓整數(shù)處于一個確定的邊界內(nèi)闲孤。
計算星期
2019年的6月3號是周一 那么30天之后的2019年7月3日是星期幾
拿 30 除以 7（因為一個星期有 7 天），然后余 2，最后在今天的基礎(chǔ)上加2天讼积，這樣你就能知道 30 天之后是星期三了肥照。
index = hash(key) % N
其中 hash 函數(shù)是一個將字符串轉(zhuǎn)換為正整數(shù)的哈希映射方法，N 就是節(jié)點的數(shù)量勤众。
同余定理
兩個整數(shù) a 和 b舆绎，如果它們除以正整數(shù) m 得到的余數(shù)相等，我們就可以說 a 和 b 對于模 m 同余们颜。
同余定理的用途：同余定理其實就是用來分類
安全加密與校驗
哈希算法是MD5（MD5 Message-Digest Algorithm吕朵，MD5 消息摘要算法）和 SHA （Secure Hash Algorithm，安全散列算法）窥突。
數(shù)據(jù)傳輸中的問題
A 向 B 發(fā)送的消息可能會在傳輸途中被 X 偷看(如右圖)努溃。這就是“竊聽”。
? 假冒
A 以為向 B 發(fā)送了消息,然而 B 有可能是 X 冒充的(如下頁上圖);反過來, B 以為從 A
那里收到了消息,然而 A 也有可能是 X 冒充的阻问。這種問題就叫作“假冒”梧税。
篡改
即便 B 確實收到了 A 發(fā)送的消息,該消息的內(nèi)容在途中就被 X 更改了。
這種行為就叫作“篡改”称近。除了被第三者篡改外,通信故障導(dǎo)致的數(shù)據(jù)損壞也可能會使消息內(nèi)容發(fā)生變化第队。
事后否認(rèn)
B 從 A 那里收到了消息,但作為消息發(fā)送者的 A 可能對 B 抱有惡意,并在事后聲稱“這不是我發(fā)送的消息”
這種情況會導(dǎo)致互聯(lián)網(wǎng)上的商業(yè)交易或合同簽署無法成立。這種行為便是“事后否認(rèn)”刨秆。
| 竊聽 | 加密 |
| 假冒 | 數(shù)字簽名/消息認(rèn)證碼 |
| 篡改 | 數(shù)字簽名/消息認(rèn)證碼 |
| 事后否認(rèn) | 數(shù)字簽名 |
3唯一標(biāo)示
我們可以從圖片的二進(jìn)制碼串開頭取 100 個字節(jié)斥铺，從中間取 100 個字節(jié)，從最后再取 100 個字 節(jié)坛善，然后將這 300 個字節(jié)放到一塊晾蜘，通過哈希算法（比如 MD5 ），得到一個哈希字符串眠屎，用它作為圖片的唯一標(biāo)識剔交。通過這個唯一標(biāo)識來判定圖片是否在圖庫 中，這樣就可以減少很多工作量改衩。
4負(fù)載均衡
會話粘滯（session sticky）岖常，在一次會話中的所有請求都路由到同一個服務(wù)器上。
通過哈希算法葫督，對客戶端IP地址或者會話ID計算哈希值竭鞍，將取得的哈希值與服務(wù)器列表的大小進(jìn) 行取模運算，最終得到的值就是應(yīng)該被路由到的服務(wù)器編號橄镜。 這樣偎快，我們就可以把同一個IP過來的所有請求，都路由到同一個后端服務(wù)器上洽胶。
分布式session管理實現(xiàn)方案
1Session復(fù)制
在支持Session復(fù)制的Web服務(wù)器上晒夹，通過修改Web服務(wù)器的配置，可以實現(xiàn)將Session同步到其它Web服務(wù)器上，達(dá)到每個Web服務(wù)器上都保存一致的Session丐怯。
優(yōu)點：代碼上不需要做支持和修改喷好。
缺點：需要依賴支持的Web服務(wù)器，一旦更換成不支持的Web服務(wù)器就不能使用了读跷，在數(shù)據(jù)量很大的情況下不僅占用網(wǎng)絡(luò)資源梗搅，而且會導(dǎo)致延遲。
適用場景：只適用于Web服務(wù)器比較少且Session數(shù)據(jù)量少的情況效览。
可用方案：開源方案tomcat-redis-session-manager魁莉，暫不支持Tomcat8擦俐。
2.Session粘滯
將用戶的每次請求都通過某種方法強(qiáng)制分發(fā)到某一個Web服務(wù)器上敛劝，只要這個Web服務(wù)器上存儲了對應(yīng)Session數(shù)據(jù)杆兵，就可以實現(xiàn)會話跟蹤始鱼。
優(yōu)點：使用簡單臀防，沒有額外開銷为流。
缺點：一旦某個Web服務(wù)器重啟或宕機(jī)酸茴，相對應(yīng)的Session數(shù)據(jù)將會丟失烫映，而且需要依賴負(fù)載均衡機(jī)制沼本。
適用場景：對穩(wěn)定性要求不是很高的業(yè)務(wù)情景。
.Session集中管理
在單獨的服務(wù)器或服務(wù)器集群上使用緩存技術(shù)锭沟，如Redis存儲Session數(shù)據(jù)抽兆，集中管理所有的Session，所有的Web服務(wù)器都從這個存儲介質(zhì)中存取對應(yīng)的Session族淮，實現(xiàn)Session共享辫红。
優(yōu)點：可靠性高，減少Web服務(wù)器的資源開銷祝辣。
缺點：實現(xiàn)上有些復(fù)雜贴妻，配置較多。
適用場景：Web服務(wù)器較多蝙斜、要求高可用性的情況名惩。
可用方案：開源方案Spring Session，也可以自己實現(xiàn)孕荠，主要是重寫HttpServletRequestWrapper中的getSession方法娩鹉，博主也動手寫了一個，github搜索joincat用戶稚伍，然后自取弯予。
基于Cookie管理
這種方式每次發(fā)起請求的時候都需要將Session數(shù)據(jù)放到Cookie中傳遞給服務(wù)端。
優(yōu)點：不需要依賴額外外部存儲个曙，不需要額外配置熙涤。
缺點：不安全，易被盜取或篡改；Cookie數(shù)量和長度有限制祠挫，需要消耗更多網(wǎng)絡(luò)帶寬那槽。
適用場景：數(shù)據(jù)不重要、不敏感且數(shù)據(jù)量小的情況等舔。
5數(shù)據(jù)分片
統(tǒng)計 “ 搜索關(guān)鍵詞 ” 出現(xiàn)的次數(shù)骚灸？
1搜索日志很大，沒辦法放到一臺機(jī)器的內(nèi)存中慌植。
2如果只用一臺機(jī)器來處理這么巨大的數(shù)據(jù)甚牲，處理時間會很長。
具體的思路是這樣的：為了提高處理的速度蝶柿，我們用n臺機(jī)器并 行處理丈钙。我們從搜索記錄的日志文件中，依次讀出每個搜索關(guān)鍵詞交汤，并且通過哈希函數(shù)計算哈希值雏赦，然后再跟 n 取模，最終得到的值芙扎，就是應(yīng)該被分配到的機(jī)器編號星岗。處理過程也是MapReduce 的基本設(shè)計思想。
給這1億張圖片構(gòu)建散列表大約需要多少臺機(jī)器戒洼。
散列表中每個數(shù)據(jù)單元包含兩個信息俏橘，哈希值和圖片文件的路徑。假設(shè)我們通過 MD5 來計算哈希值圈浇，那長度就是 128 比特寥掐，也就是 16 字節(jié)。文件路徑長度的上限 是 256 字節(jié)磷蜀，我們可以假設(shè)平均長度是 128 字節(jié)曹仗。如果我們用鏈表法來解決沖突，那還需要存儲指針蠕搜，指針只占用 8 字節(jié)怎茫。所以，散列表中每個數(shù)據(jù)單元就占 用 152 字節(jié)（這里只是估算妓灌，并不準(zhǔn)確）轨蛤。 假設(shè)一臺機(jī)器的內(nèi)存大小為 2GB ，散列表的裝載因子為 0.75 虫埂，那一臺機(jī)器可以給大約 1000 萬（ 2GB*0.75/152 ）張圖片構(gòu)建散列表祥山。所以，如果要對 1 億張圖片構(gòu)建 索引掉伏，需要大約十幾臺機(jī)器缝呕。在工程中澳窑，這種估算還是很重要的，能讓我們事先對需要投入的資源供常、資金有個大概的了解摊聋，能更好地評估解決方案的可行性。 實際上栈暇，針對這種海量數(shù)據(jù)的處理問題麻裁，我們都可以采用多機(jī)分布式處理。借助這種分片的思路源祈，可以突破單機(jī)內(nèi)存煎源、 CPU 等資源的限制。
6分布式存儲
一致 Hash 算法是將所有的哈希值構(gòu)成了一個環(huán)香缺，其范圍在 0 ~ 2^32-1手销。如下圖：
之后將各個節(jié)點散列到這個環(huán)上，可以用節(jié)點的 IP图张、hostname 這樣的唯一性字段作為 Key 進(jìn)行 hash(key)锋拖，散列之后如下：
之后需要將數(shù)據(jù)定位到對應(yīng)的節(jié)點上，使用同樣的 hash 函數(shù) 將 Key 也映射到這個環(huán)上埂淮。
這樣按照順時針方向就可以把 k1 定位到 N1節(jié)點姑隅，k2 定位到 N3節(jié)點写隶，k3 定位到 N2節(jié)點倔撞。
依然根據(jù)順時針方向，k2 和 k3 保持不變慕趴，只有 k1 被重新映射到了 N3痪蝇。這樣就很好的保證了容錯性，當(dāng)一個節(jié)點宕機(jī)時只會影響到少少部分的數(shù)據(jù)冕房。
拓展性當(dāng)新增一個節(jié)點時:
在 N2 和 N3 之間新增了一個節(jié)點 N4 躏啰，這時會發(fā)現(xiàn)受印象的數(shù)據(jù)只有 k3，其余數(shù)據(jù)也是保持不變耙册，所以這樣也很好的保證了拓展性给僵。
hash偏斜
當(dāng)節(jié)點較少時會出現(xiàn)數(shù)據(jù)分布不均勻的情況：
都在 N1 節(jié)點，只有少量的數(shù)據(jù)在 N2 節(jié)點详拙。
為了解決這個問題帝际，一致哈希算法引入了虛擬節(jié)點。將每一個節(jié)點都進(jìn)行多次 hash饶辙，生成多個節(jié)點放置在環(huán)上稱為虛擬節(jié)點:
一致性哈希算法
假設(shè)我們有k個機(jī)器蹲诀，數(shù)據(jù)的哈希值的范圍是 [0, MAX] 。我們將整個范圍劃分成 m 個小區(qū)間（ m 遠(yuǎn)大于 k ）弃揽，每個機(jī)器負(fù)責(zé) m/k 個小區(qū)間脯爪。當(dāng)有新機(jī)器加入的時候则北， 我們就將某幾個小區(qū)間的數(shù)據(jù)，從原來的機(jī)器中搬移到新的機(jī)器中痕慢。這樣尚揣，既不用全部重新哈希、搬移數(shù)據(jù)守屉，也保持了各個機(jī)器上數(shù)據(jù)數(shù)量的均衡惑艇。
參考文章
https://www.bilibili.com/video/av25184175?from=search&seid=10220130562591473572
https://zhuanlan.zhihu.com/p/57988082
