數(shù)據(jù)結(jié)構(gòu)-哈希

原文地址: https://blog.wangriyu.wang/2018/06-Tree.html

蛤~喜吧料扰！svg 圖片好像上傳不了晒杈，圖文去原文看吧...

索引

在 MySQL 中孔厉，主要有四種類型的索引撰豺，分別為：B-Tree 索引污桦，Hash 索引，F(xiàn)ulltext 索引和 R-Tree 索引捆憎。前一節(jié)已經(jīng)講了 B 類樹的結(jié)構(gòu)特點(diǎn)躲惰，這次講哈希索引础拨，至于后面的全文索引和 R 樹索引感興趣自己看吧诡宗。

之前講 B 樹時(shí)提到過哈希索引可以支持動(dòng)態(tài)長(zhǎng)度击儡，而且由于 Hash 索引結(jié)構(gòu)的特殊性阳谍，其檢索效率非常高矫夯，最好的情況可以一次定位，查詢效率遠(yuǎn)大于 B 樹制肮，但是實(shí)際運(yùn)用中主要還是用 B 樹做索引豺鼻，因?yàn)楣Ｋ饕幸韵戮窒扌?

（1）Hash 索引適合定值查詢儒飒，不能做范圍查詢

由于 Hash 索引比較的是進(jìn)行 Hash 運(yùn)算之后的 Hash 值约素，所以它只能用于等值的過濾，不能用于基于范圍的過濾士葫，因?yàn)榻?jīng)過相應(yīng)的 Hash 算法處理之后的 Hash 值的大小關(guān)系慢显，并不能保證和 Hash 運(yùn)算前完全一樣荚藻。

（2）Hash 索引無法用于排序操作

由于 Hash 索引中存放的是經(jīng)過 Hash 計(jì)算之后的 Hash 值应狱，而且 Hash 值的大小關(guān)系并不一定和 Hash 運(yùn)算前的鍵值完全一樣祠丝，所以數(shù)據(jù)庫無法利用索引的數(shù)據(jù)來進(jìn)行任何排序運(yùn)算写半；

（3）Hash 索引不能利用部分索引鍵查詢

比如 (a,b,c) 形式的組合索引叠蝇，查詢中只用到了 a 和 b 也是可以查詢的悔捶，如果使用 hash 表，組合索引會(huì)將幾個(gè)字段合并 hash枚冗，沒辦法支持部分索引

（4）Hash 索引遇到大量 Hash 值相等的情況后性能并不一定就會(huì)比 B-Tree 索引高

數(shù)據(jù)庫支持非唯一的 Hash 索引，如果遇到非唯一值淤齐，存儲(chǔ)引擎會(huì)將他們鏈接到同一個(gè) hash 鍵值下以一個(gè)鏈表的形式存在更啄，然后在取得實(shí)際鍵值的時(shí)候再過濾不符合的鍵

Hash 索引在 MySQL 中使用的并不是很多祭务，目前主要是 Memory 和 NDB 引擎會(huì)使用义锥；而常用的 Innodb 存儲(chǔ)引擎和 MyISAM 引擎使用的索引還是 B+ 樹為主

哈希表

哈希表 (Hash Table)，也叫散列表赂鲤，是根據(jù)鍵（Key）轉(zhuǎn)換而直接訪問在存儲(chǔ)地址的數(shù)據(jù)結(jié)構(gòu)数初。

定義

比如我們有關(guān)鍵字 k泡孩，則其值存放在 f(k) 的存儲(chǔ)位置上珍德，因此不需要比較就可以找到記錄锈候。這個(gè)映射關(guān)系 f(x) 稱為哈希函數(shù)(散列函數(shù))敞贡，以此建立的表就是哈希表誊役。

哈希表中存著的是包含存儲(chǔ)單元的數(shù)組蛔垢，這些存儲(chǔ)單元我們稱作槽 (slot) 或者桶 (bucket) 鹏漆，每個(gè)存儲(chǔ)單元可以容納一個(gè)或多個(gè)關(guān)鍵字信息。理想情況下鞠抑，完美的散列函數(shù)能為關(guān)鍵字找到唯一的獨(dú)占的桶搁拙，但大多數(shù)情況下用到的散列函數(shù)都是不完美的箕速，會(huì)存在沖突朋譬；

對(duì)不同的關(guān)鍵字可能得到同一散列地址此熬，即 k1 != k2犀忱，而 f(k1) == f(k2)阴汇，這種現(xiàn)象稱為沖突 (Collision)搀庶。具有相同函數(shù)值的關(guān)鍵字對(duì)該散列函數(shù)來說稱做同義詞。

若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字秸架，經(jīng)散列函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的东抹，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function）缭黔，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個(gè)“隨機(jī)的地址”馏谨，從而減少?zèng)_突

原理

[圖片上傳失敗...(image-7b7d03-1545274194865)]

輸入一個(gè)關(guān)鍵字 "lies"惧互，經(jīng)過散列得到值 9壹哺，對(duì)應(yīng)哈希表得到我們要的地址 20

從關(guān)鍵字到索引值的轉(zhuǎn)換過程使用的就是散列函數(shù)抄伍，散列函數(shù)有很多種艘刚，比如一種簡(jiǎn)單的散列方式如下:

[圖片上傳失敗...(image-67dd46-1545274194865)]

取關(guān)鍵字每個(gè)字符的 ASCII 碼管宵，相加，即 lies -> 108+105+101+115 -> 429

但是我們的表只有 30 項(xiàng)攀甚，那么可以再把上面的值模 30: 429 mod 30 = 9

一個(gè)散列就完成了

但是繼續(xù)輸入發(fā)現(xiàn):

[圖片上傳失敗...(image-82ab61-1545274194865)]

關(guān)鍵字 "foes" 散列后也對(duì)應(yīng)表下標(biāo) 9箩朴，這就是沖突，"lies" 和 "foes" 是同義詞

每種哈希表實(shí)現(xiàn)都要有處理沖突的方法炸庞，處理沖突也有很多方式，比如這里可以用簡(jiǎn)單的鏈表來處理:

[站外圖片上傳中...(image-798d87-1545274194865)]

之前哈希表中索引對(duì)應(yīng)的就是具體的地址荚斯，而現(xiàn)在改成一個(gè)指向鏈表的指針埠居，所有同義詞都存在相應(yīng)鏈表中

但是我們?cè)趺粗钡芥湵砟膫€(gè)是 "lies" 哪個(gè)是 "foes" 呢，可以在鏈表每個(gè)節(jié)點(diǎn)中添加關(guān)鍵字信息:

[圖片上傳失敗...(image-284431-1545274194865)]

這樣沖突就算處理了事期，但是這種哈希表結(jié)構(gòu)的最壞情況是 O(n)滥壕，不同于之前 O(1)。因?yàn)榧偃绱蟛糠株P(guān)鍵字都是沖突的兽泣，那么這些關(guān)鍵字就變?yōu)殒湵聿樵兞恕?/p>

因此一個(gè)均勻的散列函數(shù)和一個(gè)高效的處理沖突的方法對(duì)哈希表來說至關(guān)重要

下面會(huì)介紹一些常見的哈希函數(shù)和處理沖突的方法

哈希函數(shù)

  1. 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址绎橘。即 hash(k) = k 或 hash(k) = a * k + b，其中 a, b 為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）
  2. 數(shù)字分析法：假設(shè)關(guān)鍵字是以 r 為基的數(shù)唠倦，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的称鳞，則可取關(guān)鍵字的若干數(shù)位組成哈希地址
  3. 平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況稠鼻，取其中的哪幾位也不一定合適冈止，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的候齿。取的位數(shù)由表長(zhǎng)決定靶瘸。比如 {421，423毛肋，436}怨咪，平方之后的結(jié)果為{177241，178929润匙，190096}诗眨，那么可以取中間的兩位數(shù){72，89孕讳，00}作為 Hash 地址
  4. 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同）匠楚，然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址巍膘。比如圖書的 ISBN 號(hào)為 8903-241-23，可以將 address(key)=89+03+24+12+3 作為 Hash 地址芋簿。
  5. 隨機(jī)數(shù)法
  6. 除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為散列地址峡懈。即 hash(k) = k mod p, p <= m。不僅可以對(duì)關(guān)鍵字直接取模与斤，也可在折疊法肪康、平方取中法等運(yùn)算之后取模。對(duì) p 的選擇很重要撩穿，一般取素?cái)?shù)或 m磷支，若 p 選擇不好，也容易產(chǎn)生沖突

沖突

影響因素

影響產(chǎn)生沖突多少有以下三個(gè)因素：

  • 散列函數(shù)是否均勻
  • 處理沖突的方法
  • 散列表的負(fù)載因子

散列表的負(fù)載因子定義為：α = 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度食寡。α 是散列表裝滿程度的標(biāo)志因子雾狈。
由于表長(zhǎng)是定值，α 與“填入表中的元素個(gè)數(shù)”成正比抵皱，所以 α 越大善榛，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大呻畸。

處理方法

1移盆、開放尋址 (open addressing/closed hashing): 一旦發(fā)生了沖突，通過探測(cè)尋找其他空的位置擂错，然后插入味滞。

hash_i = (hash(k) + d_i) mod m, i = 1, 2, 3...m-1, 其中 hash(k) 為散列函數(shù)，d_i 是增量序列钮呀，m 為哈希表長(zhǎng)剑鞍，i 為已發(fā)生沖突的次數(shù)。

hash(k) 是初始的探測(cè)位置爽醋，之后的探測(cè)位置 hash _1, hash_2, hash_3...hash _{m-1} 形成一個(gè)探測(cè)序列蚁署。

如果 d_i = i = 1, 2, 3...m-1，則為線性探測(cè)蚂四，相當(dāng)于逐一往下找表空閑位置

如果 d_i = \pm1^2, \pm2^2, \pm3^2...\pm k^2光戈，則為二次探測(cè)(或者叫平方探測(cè))，相當(dāng)于探測(cè)間隔為 \pm i^2

如果 d_i = i * rehash(k)遂赠，rehash 是另一個(gè)哈希函數(shù)久妆，則為雙散列探測(cè)

如果 d_i = 偽隨機(jī)數(shù)序列，則為偽隨機(jī)探測(cè)

對(duì)開放尋址散列表性能的關(guān)鍵影響是載荷因子跷睦。隨著載荷系數(shù)增加到 100％筷弦，可能需要查找或插入給定關(guān)鍵字的探針數(shù)量急劇增加。一旦表格變滿，探測(cè)算法甚至可能無法終止烂琴。即使具有良好的散列函數(shù)爹殊，也應(yīng)嚴(yán)格限制載荷因子在 0.7-0.8 以下，比如 Java 的系統(tǒng)庫限制了荷載因子為 0.75奸绷，超過此值將動(dòng)態(tài)調(diào)整散列表大小梗夸。

2、單獨(dú)鏈表法号醉。即上述原理用到的方法反症，也叫拉鏈法，鏈表的使用方式可以分很多種扣癣，可以見 WikiPedia 的事例惰帽，另外算法導(dǎo)論里提到一種完全散列的方式憨降，相當(dāng)于二維哈希表父虑，每個(gè)槽對(duì)應(yīng)的是另一個(gè)哈希列表，也值得借鑒

3授药、再散列: hash_i = rehash_i(k), i = 1, 2, 3...k, 在發(fā)生沖突時(shí)士嚎，使用其他散列函數(shù)計(jì)算哈希值，直到?jīng)_突不再發(fā)生悔叽。這種方法不易產(chǎn)生“聚集”莱衩，但增加了計(jì)算時(shí)間。

4娇澎、建立一個(gè)公共溢出區(qū)

動(dòng)態(tài)哈希

前面的問題都是以哈希表定長(zhǎng)為基礎(chǔ)的笨蚁，但是當(dāng)關(guān)鍵字較多時(shí)，哈希表出現(xiàn)聚集時(shí)趟庄，性能會(huì)急劇下降括细。

即散列表的載荷因子較大時(shí)需要考慮擴(kuò)充哈希表大小，如果是靜態(tài) hash戚啥，則需要新建一張更大的表奋单，然后將所有關(guān)鍵字重新散列到新的表中，之后刪除舊表

而動(dòng)態(tài)散列可以在哈希表元素增長(zhǎng)的同時(shí)猫十，動(dòng)態(tài)的調(diào)整 hash 桶的數(shù)目览濒，動(dòng)態(tài) hash 不需要對(duì)原有元素進(jìn)行重新插入(重組)，而是在原基礎(chǔ)上拖云，進(jìn)行動(dòng)態(tài)的桶擴(kuò)展贷笛。

有以下三種方法可以實(shí)現(xiàn)動(dòng)態(tài) hash:

  • 多 hash 表
  • 可擴(kuò)展的動(dòng)態(tài)散列
  • 線性散列

多 hash 表

多 hash 表就是采用多張哈希表來擴(kuò)充原哈希表。

[站外圖片上傳中...(image-18747c-1545274194865)]

如圖宙项，哈希函數(shù)為 hash(k) = k % 5乏苦，每個(gè)桶最多含 4 個(gè)關(guān)鍵字

當(dāng)我們要插入關(guān)鍵字 5 時(shí)，hash 值為 0杉允，應(yīng)該插入 Bucket 1 中邑贴，而且 Bucket 1 有空閑位置席里，直接插入即可；

當(dāng)我們要插入關(guān)鍵字 3 時(shí)拢驾，hash 值為 3奖磁，應(yīng)該插入 Bucket 3 中，但是 Bucket 3 已經(jīng)滿了繁疤，此時(shí)新建一張 hash 表來完成插入

[圖片上傳失敗...(image-7bae98-1545274194865)]

對(duì)于此種方式咖为，執(zhí)行插入、查找稠腊、刪除操作時(shí)躁染，均需先求得 hash 值 x。

  • 插入時(shí)架忌，得到當(dāng)前的 hash 表的個(gè)數(shù)吞彤，并分別取得各個(gè) hash 表的 x 位置上的索引項(xiàng)，若其中某個(gè)項(xiàng)指向的桶存在空閑位置叹放，則插入之饰恕。同時(shí)，在插入時(shí)井仰，可保持多個(gè) hash 表在某個(gè)索引項(xiàng)上桶中元素的個(gè)數(shù)近似相等埋嵌。若不存在空閑位置，則簡(jiǎn)單的進(jìn)行表擴(kuò)充俱恶，即新建一個(gè) hash 表雹嗦，如上所示
  • 查找時(shí)，由于某個(gè)記錄值可能存在當(dāng)前 hash 結(jié)構(gòu)的多個(gè)表中合是，因此需同時(shí)在多個(gè) hash 表的同一位置上進(jìn)行查找操作了罪，等待所有的查找結(jié)束后，方可判定該元素是否存在端仰。由于該種結(jié)構(gòu)需進(jìn)行多次查找捶惜，當(dāng)表元素非常多時(shí)，為提高效率荔烧，在多處理器上可采用多線程吱七，并發(fā)執(zhí)行查找操作
  • 刪除操作，與上述過程基本類似鹤竭。需要注意的是踊餐，若刪除操作導(dǎo)致某個(gè) hash 表元素為空，這時(shí)可將該表從結(jié)構(gòu)中剔除

這種方式的優(yōu)點(diǎn)是設(shè)計(jì)和實(shí)現(xiàn)比較簡(jiǎn)單的臀稚。缺點(diǎn)是占用空間大吝岭，而且關(guān)鍵字較密集時(shí)空間利用率低。

可擴(kuò)展的動(dòng)態(tài)散列

引入一個(gè)僅存儲(chǔ)桶指針的索引數(shù)組，用翻倍的索引項(xiàng)數(shù)來取代翻倍的桶的數(shù)目窜管，且每次只分裂有溢出的桶散劫，從而減小翻倍的代價(jià)。

[圖片上傳失敗...(image-46bb14-1545274194865)]

如圖所示哈希表有一個(gè)標(biāo)識(shí)表示全局位深度 (Global Depth)幕帆，全局位深度表示取哈希值的低幾位作為索引获搏，比如 hash(k4) = 0100，全局位深度為 2失乾，則取低兩位 00 歸屬到 00 索引的桶中常熙，而且哈希表索引項(xiàng)數(shù)始終等于 2 ^ Global Depth；桶中有一個(gè)本地位深度 (Local Depth)碱茁，本地位深度表示當(dāng)前桶中元素的低幾位是一樣的裸卫；圖中給出的桶中元素表示哈希后的值，比如桶 1 中 4 表示哈希值為 0100 的關(guān)鍵字 k4

  • 插入時(shí)纽竣，計(jì)算出哈希值再根據(jù)全局位深度匹配索引項(xiàng)墓贿，如果找到的桶未滿，則直接插入即可退个；如果桶已滿募壕，則判斷當(dāng)前桶的本地位深度 L 與全局位深度 G 的大小關(guān)系: 如果 L = G调炬，此時(shí)只有一個(gè)指針指向當(dāng)前桶语盈，則擴(kuò)展索引，本地位深度和全局位深度均加一缰泡，索引項(xiàng)翻倍刀荒，重組當(dāng)前桶的元素；如果 L < G棘钞，此時(shí)不止一個(gè)指針指向當(dāng)前桶缠借，故不需要翻倍索引項(xiàng)，只需分裂出一個(gè)桶宜猜，將本地位深度加一然后重組當(dāng)前桶元素即可
  • 查找時(shí)泼返，對(duì)于需要查找的關(guān)鍵字 x，hash(x) = y姨拥，根據(jù)當(dāng)前 hash 表的全局位深度绅喉，決定對(duì) y 取其后 G 位，位數(shù)不夠用 0 填充叫乌，找到對(duì)應(yīng)的索引項(xiàng)柴罐，從而找到對(duì)應(yīng)的桶，在桶中逐一進(jìn)行比較
  • 刪除時(shí)憨奸，和查找操作類似革屠，先定位元素贸弥，刪除之绣张。若刪除時(shí)發(fā)現(xiàn)桶為空，則可以考慮將該桶與其兄弟桶進(jìn)行合并，并使局部位深度減一

插入實(shí)例:

當(dāng)我們插入某個(gè)關(guān)鍵字 k13婿奔，hash(k13) = 1101，對(duì)應(yīng)索引 01 的桶 Bucket 2嚼松，桶未滿直接插入即可又憨；

再插入某個(gè)關(guān)鍵字 k20，hash(k20) = 10100麻诀，對(duì)應(yīng)索引 00 的桶 Bucket 1痕寓，桶已滿而且本地位深度等于全局位深度，需要擴(kuò)展索引蝇闭，全局位深度和本地位深度均加一呻率，并重組當(dāng)前桶的元素，變?yōu)橄聢D:

[圖片上傳失敗...(image-8912ad-1545274194865)]

繼續(xù)插入某個(gè)關(guān)鍵字 k25呻引，hash(k25) = 11001礼仗，對(duì)應(yīng)索引 001 的桶 Bucket 2，桶已滿而且本地位深度小于全局位深度逻悠，當(dāng)前桶存在兩個(gè)指針元践，只需要分裂出一個(gè)桶即可并將桶的本地位深度加一，如圖:

[圖片上傳失敗...(image-b61400-1545274194865)]

這種方式的優(yōu)點(diǎn)是可以可動(dòng)態(tài)進(jìn)行桶的增長(zhǎng)童谒，且增長(zhǎng)的同時(shí)单旁，用索引項(xiàng)的翻倍代替桶數(shù)翻倍的傳統(tǒng)做法，可用性更好饥伊。缺點(diǎn)是當(dāng)散列的數(shù)據(jù)分布不均或偏斜較大時(shí)象浑，會(huì)使得索引項(xiàng)的數(shù)目很大，數(shù)據(jù)桶的利用率很低琅豆；還有索引的增長(zhǎng)速度愉豺，是指數(shù)級(jí)增長(zhǎng)，擴(kuò)展較快

線性散列

線性散列能隨數(shù)據(jù)的插入和刪除茫因，適當(dāng)?shù)膶?duì) hash 桶數(shù)進(jìn)行調(diào)整蚪拦，一次只分裂一個(gè)桶，線性散列不需要存放數(shù)據(jù)桶指針的專門索引項(xiàng)冻押。

定義:

標(biāo)識(shí)符 描述
h_0,h_1,h_2... 一系列哈希函數(shù)驰贷，后者的范圍總是前者的兩倍，i 為下標(biāo)翼雀，h_i(key) = hash(key) mod (N*2^i)
N 桶的初始個(gè)數(shù)饱苟，必須是 2 的冪次方
d_i 多少比特位用于表示 N，N = 2^{d_i}
Level 當(dāng)前輪數(shù)狼渊，每輪的初始桶數(shù)等于 N*2^{Level}
Next 一個(gè)指針指向需要分裂的桶箱熬，每次發(fā)生分裂的桶總是由 Next 決定类垦，與當(dāng)前值被插入的桶已滿或溢出無關(guān)
Load Factor 負(fù)載因子，當(dāng)桶中記錄數(shù)達(dá)到該值時(shí)進(jìn)行分裂城须；也可選擇當(dāng)桶滿時(shí)才進(jìn)行分裂

當(dāng)某個(gè)桶發(fā)生溢出時(shí)蚤认，可以將溢出元素以鏈表的形式鏈在桶后；
可以監(jiān)控整張哈希表或者桶的負(fù)載因子糕伐，視情況選擇是否分裂砰琢，比如全表的負(fù)載達(dá)到 0.75 可以對(duì)當(dāng)前桶進(jìn)行分裂，也可以選擇只有桶滿了才分裂良瞧；

實(shí)例:

初始狀態(tài) N = 4, Level = 0, Next 指向第一個(gè)桶

[圖片上傳失敗...(image-1b1bde-1545274194865)]

插入某個(gè)關(guān)鍵字 k37陪汽，hash(k37) = 37 = 100101，h_0(k37) = 01(取低兩位)褥蚯，對(duì)應(yīng)編號(hào) 1 的桶挚冤，此時(shí)桶未滿直接插入即可:

[圖片上傳失敗...(image-319b4f-1545274194865)]

插入某個(gè)關(guān)鍵字 k43，hash(k43) = 43 = 101011赞庶，h_0(k43) = 11(取低兩位)训挡，對(duì)應(yīng)編號(hào) 3 的桶，此時(shí)桶已滿需要分裂:
首先把 43 鏈在桶 3 后面歧强，然后分裂 Next 指向的桶 0澜薄，產(chǎn)生一個(gè)新桶，新桶編號(hào) = N + Next = 4 + 0 = 100摊册，Next 指向下一個(gè)桶肤京；最后把桶 0 的元素按 h1 散列重組

[圖片上傳失敗...(image-de0609-1545274194865)]

繼續(xù)插入某個(gè)關(guān)鍵字 k29，hash(k29) = 29 = 11101丧靡，h_0(k29) = 01蟆沫，對(duì)應(yīng)編號(hào) 1 的桶，此時(shí)桶已滿需要分裂:
也是按剛才的步驟處理温治，不過這次 Next 指向的桶就是當(dāng)前桶

[圖片上傳失敗...(image-a98b30-1545274194865)]

向桶 1 中連續(xù)插入 17，33戒悠，41熬荆，引起分裂:

[圖片上傳失敗...(image-3b690a-1545274194865)]

繼續(xù)向桶 1 插入 57，引起分裂绸狐，需要注意的是這時(shí) Next 指針已經(jīng)遍歷過初始的四個(gè)桶卤恳，第一輪已結(jié)束，Level 加一寒矿，Next 指向第一個(gè)桶突琳，第二輪初始為八個(gè)桶(即 N = 8):

[圖片上傳失敗...(image-140c01-1545274194865)]

插入就是如上形式進(jìn)行，接下來看怎么查找:

假如要查找某個(gè)關(guān)鍵字 key 對(duì)應(yīng)的位置符相，如果 Next \leq h _{Level}(key) \leq N-1拆融，則查詢 h _{Level} 列的與低 d_i 位對(duì)應(yīng)的桶蠢琳，否則查詢 h _{Level+1} 列的與低 d_i +1 位對(duì)應(yīng)的桶。

[圖片上傳失敗...(image-66a06e-1545274194865)]

在此圖中 N = 4镜豹，Level = 0傲须，Next = 2，d_0 = 2

比如查詢 k44趟脂，h_0(k44) = 00泰讽，00(= 0) 不在 2 和 3 之間，則查詢 h1 列與 k44 低三位 (100) 對(duì)應(yīng)的桶昔期，找到編號(hào)為 4 的桶已卸，再從桶找到對(duì)應(yīng)位置；

假如查詢的是 k7硼一，h_0(k7) = 11咬最，11(= 3) 在 2 和 3 之間，則查詢 h0 列與 k7 低兩位 (11) 對(duì)應(yīng)的桶欠动，找到編號(hào)為 3 的桶永乌，再從桶中找到對(duì)應(yīng)位置

[圖片上傳失敗...(image-a2342f-1545274194865)]

在此圖中 N = 8，Level = 1具伍，Next = 0翅雏，d_1 = 3

假如查詢 k44，h_1(k44) = 100人芽，100(= 4) 在 0 和 7 之間望几，所以查詢 h1 列與 100 對(duì)應(yīng)的桶，即編號(hào)為 4 的桶萤厅；

其他關(guān)鍵字的 h1 值都是在范圍 [Next, N] 內(nèi)的橄抹，所以都是找 h1 列的

線性散列的刪除操作是插入操作的逆操作，若溢出塊為空惕味，則可釋放楼誓。若刪除導(dǎo)致某個(gè)桶元素變空，則 Next 指向上一個(gè)桶名挥。當(dāng) Next 減少到 0疟羹，且最后一個(gè)桶也是空時(shí)，則 Next 指向 N/2 - 1 的位置禀倔，同時(shí) Level 值減 1榄融。

線性散列比可擴(kuò)展動(dòng)態(tài)散列更靈活，且不需要存放數(shù)據(jù)桶指針的專門索引項(xiàng)救湖，節(jié)省了空間愧杯；但如果數(shù)據(jù)散列后分布不均勻，導(dǎo)致的問題可能會(huì)比可擴(kuò)展散列還嚴(yán)重

分布式哈希

分布式哈希表 - DHT增加或移除節(jié)點(diǎn)只改變鄰近節(jié)點(diǎn)所擁有的關(guān)鍵值集合鞋既，而其他節(jié)點(diǎn)的則不會(huì)被改變力九。傳統(tǒng)的散列表耍铜，若增加或移除一個(gè)位置，則整個(gè)關(guān)鍵值空間必須重新散列畏邢。

其中一致性哈希算法非常適用于分布式哈希表业扒，一致性哈希允許任意順序插入或刪除存儲(chǔ)桶，不同于線性散列那樣需要順序處理舒萎。

一致性哈希

應(yīng)用場(chǎng)景

有 N 臺(tái)服務(wù)器提供緩存服務(wù)程储，需要對(duì)服務(wù)器進(jìn)行負(fù)載均衡，將請(qǐng)求平均分發(fā)到每臺(tái)服務(wù)器上臂寝，每臺(tái)機(jī)器負(fù)責(zé) 1/N 的服務(wù)章鲤。

常用的算法是對(duì) hash 結(jié)果模 N 取余，比如 N = 5咆贬，hash = 103败徊，余數(shù)為 3 則分發(fā)到編號(hào)為 3 的服務(wù)器上。但是這樣的算法存在嚴(yán)重問題掏缎，如果有某臺(tái)機(jī)器宕機(jī)或者新添加服務(wù)器皱蹦，都會(huì)造成大量緩存請(qǐng)求失效或者需要轉(zhuǎn)移重組數(shù)據(jù)。

而使用一致性哈希后眷蜈，同樣增加或者刪除服務(wù)器節(jié)點(diǎn)只會(huì)對(duì)少量數(shù)據(jù)產(chǎn)生影響沪哺，不需要大規(guī)模遷移數(shù)據(jù)。比如分布式緩存系統(tǒng)節(jié)點(diǎn)數(shù)多酌儒，而且容易變動(dòng)辜妓，非常適合使用一致性哈希

原理

假設(shè)一致性哈希算法的結(jié)果是 32 位的 Key 值，將這 2^32 個(gè)數(shù)值映射在一個(gè)環(huán)形空間上忌怎，則對(duì)應(yīng)有 2^32 個(gè)緩存區(qū)籍滴。比如下圖中五個(gè) Key 值分布在環(huán)形空間上

[圖片上傳失敗...(image-7239b9-1545274194865)]

每一個(gè)緩存節(jié)點(diǎn)（Shard）也遵循同樣的 Hash 算法，比如利用 IP 做 Hash榴啸，映射到環(huán)形空間當(dāng)中

[圖片上傳失敗...(image-48415f-1545274194865)]

然后按順時(shí)針將 Key 歸屬到最近的節(jié)點(diǎn)上孽惰，比如 K5、K1 歸屬為節(jié)點(diǎn) N1 上

[圖片上傳失敗...(image-e8aab7-1545274194865)]

增加節(jié)點(diǎn) N4 時(shí)插掂，我們只需要改變 K5 的歸屬即可灰瞻，不會(huì)對(duì)其他節(jié)點(diǎn)和數(shù)據(jù)造成影響

[圖片上傳失敗...(image-76f375-1545274194865)]

刪除節(jié)點(diǎn) N1 時(shí)，我們只需要將 K1 歸屬到 N2 上就行

[圖片上傳失敗...(image-957dac-1545274194865)]

但是仍會(huì)有分布不均的情況辅甥，特別是服務(wù)器節(jié)點(diǎn)較少時(shí)，比如下圖大部分鍵值都流向某個(gè)單一節(jié)點(diǎn)

[圖片上傳失敗...(image-2cae67-1545274194865)]

為了應(yīng)對(duì)這種情況燎竖，引入了虛擬節(jié)點(diǎn)的概念璃弄，將原來的一個(gè)物理節(jié)點(diǎn)映射出多個(gè)子節(jié)點(diǎn)，讓子節(jié)點(diǎn)代替物理節(jié)點(diǎn)放置在環(huán)形空間中

[圖片上傳失敗...(image-5c376f-1545274194865)]

比如原本的物理節(jié)點(diǎn) N1 使用的關(guān)鍵字是自己的 IP 192.168.1.109构回，其位置是 hash("192.168.1.109")∠目椋現(xiàn)在為其創(chuàng)建兩個(gè)虛擬節(jié)點(diǎn) N1_1 和 N1_2疏咐，兩個(gè)子節(jié)點(diǎn)可以使用 IP + 編號(hào) 的方式計(jì)算哈希，比如 hash("192.168.1.109#1") 和 hash("192.168.1.109#2")脐供，同理為 N2 也創(chuàng)建了兩個(gè)虛擬節(jié)點(diǎn)浑塞，

創(chuàng)建虛擬節(jié)點(diǎn)的好處是分布更均勻

其他常見散列函數(shù)

MD5

Message-Digest Algorithm 5 - 消息摘要算法，一種被廣泛使用的密碼散列函數(shù)政己，可以產(chǎn)生出一個(gè) 128 位的散列值

可以應(yīng)用于文件校驗(yàn)酌壕，例如，服務(wù)器預(yù)先提供一個(gè) MD5 校驗(yàn)和歇由，用戶下載完文件以后卵牍，用 MD5 算法計(jì)算下載文件的 MD5 校驗(yàn)和，然后通過檢查這兩個(gè)校驗(yàn)和是否一致沦泌，就能判斷下載的文件是否出錯(cuò)

MD5 是輸入不定長(zhǎng)度信息糊昙，輸出固定長(zhǎng)度 128 位的算法。經(jīng)過程序流程谢谦，生成四個(gè) 32 位數(shù)據(jù)释牺，最后聯(lián)合起來成為一個(gè) 128 位散列』赝欤基本方式為没咙，求余、取余厅各、調(diào)整長(zhǎng)度镜撩、與鏈接變量進(jìn)行循環(huán)運(yùn)算，得出結(jié)果队塘。

但是 MD5 可以被破解袁梗，不適合高度安全性的場(chǎng)景，比如不能用于密鑰認(rèn)證和數(shù)字簽名

SHA

Secure Hash Algorithm - 安全散列算法是一個(gè)密碼散列函數(shù)家族憔古，也能計(jì)算出一個(gè)數(shù)字消息所對(duì)應(yīng)到的遮怜，長(zhǎng)度固定的字符串（又稱消息摘要）的算法。安全性高于 MD5鸿市，比如數(shù)字簽名常用的就是 SHA-256锯梁。

SHA 分為 SHA-0、SHA-1焰情、SHA-2陌凳、SHA-3 四個(gè)大版本，其中 SHA-0 和 SHA-1 輸出的散列值為 160 位内舟；SHA-2 細(xì)分為多種合敦，比如 SHA-256 輸出的是 256 位散列值，另外還有 SHA-224验游、SHA-384充岛、SHA-512 等等保檐；SHA-3 是 2015 年正式發(fā)布的，SHA-3 并不是要取代 SHA-2崔梗，因?yàn)?SHA-2 目前并沒有出現(xiàn)明顯的弱點(diǎn)夜只，由于對(duì) MD5 出現(xiàn)成功的破解，以及對(duì) SHA-0 和 SHA-1 出現(xiàn)理論上破解的方法蒜魄，NIST 感覺需要一個(gè)與之前算法不同的扔亥，可替換的加密散列算法，也就是現(xiàn)在的 SHA-3

CRC

Cyclic redundancy check - 循環(huán)冗余校驗(yàn)是一種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)包或計(jì)算機(jī)文件等數(shù)據(jù)產(chǎn)生簡(jiǎn)短固定位數(shù)校驗(yàn)碼的一種散列函數(shù)权悟，主要用來檢測(cè)或校驗(yàn)數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯(cuò)誤砸王。一般來說，循環(huán)冗余校驗(yàn)的值都是 32 位的整數(shù)峦阁。

CRC 的計(jì)算過程網(wǎng)絡(luò)課程便講過谦铃，不算復(fù)雜，這里不深入榔昔。WikiPedia 上提供了一些 CRC 變體的描述驹闰，感興趣可以了解一下。

盡管在錯(cuò)誤檢測(cè)中非常有用撒会，CRC 并不能可靠地校驗(yàn)數(shù)據(jù)完整性嘹朗，因?yàn)?CRC 多項(xiàng)式是線性結(jié)構(gòu)，可以非常容易地故意改變量據(jù)而維持 CRC 不變诵肛。一般使用Message authentication code校驗(yàn)數(shù)據(jù)完整性

Reference

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市怔檩，隨后出現(xiàn)的幾起案子褪秀，更是在濱河造成了極大的恐慌，老刑警劉巖薛训，帶你破解...
    沈念sama閱讀 221,548評(píng)論 6贊 515
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件媒吗，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡乙埃，警方通過查閱死者的電腦和手機(jī)闸英，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,497評(píng)論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來介袜，“玉大人甫何，你說我怎么就攤上這事∮錾。” “怎么了沛豌？”我有些...
    開封第一講書人閱讀 167,990評(píng)論 0贊 360
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)赃额。 經(jīng)常有香客問我加派，道長(zhǎng)，這世上最難降的妖魔是什么跳芳？ 我笑而不...
    開封第一講書人閱讀 59,618評(píng)論 1贊 296
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任芍锦，我火速辦了婚禮，結(jié)果婚禮上飞盆，老公的妹妹穿的比我還像新娘娄琉。我一直安慰自己，他們只是感情好吓歇，可當(dāng)我...
    茶點(diǎn)故事閱讀 68,618評(píng)論 6贊 397
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布孽水。 她就那樣靜靜地躺著，像睡著了一般城看。 火紅的嫁衣襯著肌膚如雪女气。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 52,246評(píng)論 1贊 308
  • 城市分裂傳說
    那天测柠，我揣著相機(jī)與錄音炼鞠，去河邊找鬼。 笑死轰胁，一個(gè)胖子當(dāng)著我的面吹牛谒主，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播赃阀，決...
    沈念sama閱讀 40,819評(píng)論 3贊 421
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼霎肯，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了榛斯？” 一聲冷哼從身側(cè)響起观游，我...
    開封第一講書人閱讀 39,725評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎肖抱，沒想到半個(gè)月后备典，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 46,268評(píng)論 1贊 320
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡意述，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,356評(píng)論 3贊 340
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年提佣，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片荤崇。...
    茶點(diǎn)故事閱讀 40,488評(píng)論 1贊 352
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡拌屏，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出术荤，到底是詐尸還是另有隱情倚喂，我是刑警寧澤，帶...
    沈念sama閱讀 36,181評(píng)論 5贊 350
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站端圈，受9級(jí)特大地震影響焦读，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜舱权，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,862評(píng)論 3贊 333
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一矗晃、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧宴倍，春花似錦张症、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,331評(píng)論 0贊 24
  • 一樁弒父案俗他，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至阔逼，卻和暖如春兆衅，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背颜价。 一陣腳步聲響...
    開封第一講書人閱讀 33,445評(píng)論 1贊 272
  • 情欲美人皮
    我被黑心中介騙來泰國打工涯保， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人周伦。 一個(gè)月前我還...
    沈念sama閱讀 48,897評(píng)論 3贊 376
  • 代替公主和親
    正文 我出身青樓夕春，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國和親专挪。 傳聞我的和親對(duì)象是個(gè)殘疾皇子及志，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,500評(píng)論 2贊 359

推薦閱讀更多精彩內(nèi)容