一文看懂一致性Hash算法

者：kylinkzhang，CSIG后臺(tái)開(kāi)發(fā)工程師

| 導(dǎo)語(yǔ) 一致性Hash算法是解決分布式緩存等問(wèn)題的一種算法；本文介紹了一致性Hash算法的原理，并給出了一種實(shí)現(xiàn)和實(shí)際運(yùn)用的案例；

一致性Hash算法背景

考慮這么一種場(chǎng)景：

我們有三臺(tái)緩存服務(wù)器編號(hào)node0、node1、node2，現(xiàn)在有3000萬(wàn)個(gè)key，希望可以將這些個(gè)key均勻的緩存到三臺(tái)機(jī)器上，你會(huì)想到什么方案呢？

我們可能首先想到的方案是：取模算法hash（key）% N，即：對(duì)key進(jìn)行hash運(yùn)算后取模，N是機(jī)器的數(shù)量；

這樣，對(duì)key進(jìn)行hash后的結(jié)果對(duì)3取模，得到的結(jié)果一定是0、1或者2，正好對(duì)應(yīng)服務(wù)器node0、node1、node2，存取數(shù)據(jù)直接找對(duì)應(yīng)的服務(wù)器即可，簡(jiǎn)單粗暴，完全可以解決上述的問(wèn)題；

取模算法雖然使用簡(jiǎn)單，但對(duì)機(jī)器數(shù)量取模，在集群擴(kuò)容和收縮時(shí)卻有一定的局限性：因?yàn)樵谏a(chǎn)環(huán)境中根據(jù)業(yè)務(wù)量的大小，調(diào)整服務(wù)器數(shù)量是常有的事；

而服務(wù)器數(shù)量N發(fā)生變化后hash（key）% N計(jì)算的結(jié)果也會(huì)隨之變化！

比如：一個(gè)服務(wù)器節(jié)點(diǎn)掛了，計(jì)算公式從hash（key）% 3變成了hash（key）% 2，結(jié)果會(huì)發(fā)生變化，此時(shí)想要訪問(wèn)一個(gè)key，這個(gè)key的緩存位置大概率會(huì)發(fā)生改變，那么之前緩存key的數(shù)據(jù)也會(huì)失去作用與意義；

大量緩存在同一時(shí)間失效，造成緩存的雪崩，進(jìn)而導(dǎo)致整個(gè)緩存系統(tǒng)的不可用，這基本上是不能接受的；

為了解決優(yōu)化上述情況，一致性hash算法應(yīng)運(yùn)而生~

一致性Hash算法詳述

算法原理

一致性哈希算法在 1997 年由麻省理工學(xué)院提出，是一種特殊的哈希算法，在移除或者添加一個(gè)服務(wù)器時(shí)，能夠盡可能小地改變已存在的服務(wù)請(qǐng)求與處理請(qǐng)求服務(wù)器之間的映射關(guān)系；
一致性哈希解決了簡(jiǎn)單哈希算法在分布式哈希表（Distributed Hash Table，DHT）中存在的動(dòng)態(tài)伸縮等問(wèn)題；

一致性hash算法本質(zhì)上也是一種取模算法；

不過(guò)，不同于上邊按服務(wù)器數(shù)量取模，一致性hash是對(duì)固定值2^32取模；

IPv4的地址是4組8位2進(jìn)制數(shù)組成，所以用2^32可以保證每個(gè)IP地址會(huì)有唯一的映射；

① hash環(huán)

我們可以將這2^32個(gè)值抽象成一個(gè)圓環(huán)??，圓環(huán)的正上方的點(diǎn)代表0，順時(shí)針排列，以此類(lèi)推：1、2、3…直到2^32-1，而這個(gè)由2的32次方個(gè)點(diǎn)組成的圓環(huán)統(tǒng)稱(chēng)為hash環(huán)；

② 服務(wù)器映射到hash環(huán)

在對(duì)服務(wù)器進(jìn)行映射時(shí)，使用hash（服務(wù)器ip）% 2^32，即：

使用服務(wù)器IP地址進(jìn)行hash計(jì)算，用哈希后的結(jié)果對(duì)2^32取模，結(jié)果一定是一個(gè)0到2^32-1之間的整數(shù)；

而這個(gè)整數(shù)映射在hash環(huán)上的位置代表了一個(gè)服務(wù)器，依次將node0、node1、node2三個(gè)緩存服務(wù)器映射到hash環(huán)上；

③ 對(duì)象key映射到服務(wù)器

在對(duì)對(duì)應(yīng)的Key映射到具體的服務(wù)器時(shí)，需要首先計(jì)算Key的Hash值：hash（key）% 2^32；

注：此處的Hash函數(shù)可以和之前計(jì)算服務(wù)器映射至Hash環(huán)的函數(shù)不同，只要保證取值范圍和Hash環(huán)的范圍相同即可（即：2^32）；

將Key映射至服務(wù)器遵循下面的邏輯：

從緩存對(duì)象key的位置開(kāi)始，沿順時(shí)針?lè)较蛴龅降牡谝粋€(gè)服務(wù)器，便是當(dāng)前對(duì)象將要緩存到的服務(wù)器；

假設(shè)我們有 "semlinker"、"kakuqo"、"lolo"、"fer" 四個(gè)對(duì)象，分別簡(jiǎn)寫(xiě)為 o1、o2、o3 和 o4；

首先，使用哈希函數(shù)計(jì)算這個(gè)對(duì)象的 hash 值，值的范圍是 [0, 2^32-1]：

圖中對(duì)象的映射關(guān)系如下：

hash(o1)=k1; hash(o2)=k2;
hash(o3)=k3; hash(o4)=k4;

同時(shí) 3 臺(tái)緩存服務(wù)器，分別為 CS1、CS2 和 CS3：

則可知，各對(duì)象和服務(wù)器的映射關(guān)系如下：

K1=> CS1
K4=> CS3
K2=> CS2
K3=> CS1

即：

以上便是一致性Hash的工作原理；

可以看到，一致性Hash就是：將原本單個(gè)點(diǎn)的Hash映射，轉(zhuǎn)變?yōu)榱嗽谝粋€(gè)環(huán)上的某個(gè)片段上的映射！

下面我們來(lái)看幾種服務(wù)器擴(kuò)縮容的場(chǎng)景；

服務(wù)器擴(kuò)縮容場(chǎng)景

① 服務(wù)器減少

假設(shè) CS3 服務(wù)器出現(xiàn)故障導(dǎo)致服務(wù)下線，這時(shí)原本存儲(chǔ)于 CS3 服務(wù)器的對(duì)象 o4，需要被重新分配至 CS2 服務(wù)器，其它對(duì)象仍存儲(chǔ)在原有的機(jī)器上：

此時(shí)受影響的數(shù)據(jù)只有 CS2 和 CS3 服務(wù)器之間的部分?jǐn)?shù)據(jù)！

② 服務(wù)器增加

假如業(yè)務(wù)量激增，我們需要增加一臺(tái)服務(wù)器 CS4，經(jīng)過(guò)同樣的 hash 運(yùn)算，該服務(wù)器最終落于 t1 和 t2 服務(wù)器之間，具體如下圖所示：

此時(shí)，只有 t1 和 t2 服務(wù)器之間的部分對(duì)象需要重新分配；

在以上示例中只有 o3 對(duì)象需要重新分配，即它被重新到 CS4 服務(wù)器；

在前面我們已經(jīng)說(shuō)過(guò)：如果使用簡(jiǎn)單的取模方法，當(dāng)新添加服務(wù)器時(shí)可能會(huì)導(dǎo)致大部分緩存失效，而使用一致性哈希算法后，這種情況得到了較大的改善，因?yàn)橹挥猩俨糠謱?duì)象需要重新分配！

數(shù)據(jù)偏斜&服務(wù)器性能平衡問(wèn)題

引出問(wèn)題

在上面給出的例子中，各個(gè)服務(wù)器幾乎是平均被均攤到Hash環(huán)上；

但是在實(shí)際場(chǎng)景中很難選取到一個(gè)Hash函數(shù)這么完美的將各個(gè)服務(wù)器散列到Hash環(huán)上；

此時(shí)，在服務(wù)器節(jié)點(diǎn)數(shù)量太少的情況下，很容易因?yàn)?/span>節(jié)點(diǎn)分布不均勻而造成數(shù)據(jù)傾斜問(wèn)題；

如下圖被緩存的對(duì)象大部分緩存在node-4服務(wù)器上，導(dǎo)致其他節(jié)點(diǎn)資源浪費(fèi)，系統(tǒng)壓力大部分集中在node-4節(jié)點(diǎn)上，這樣的集群是非常不健康的：

同時(shí)，還有另一個(gè)問(wèn)題：

在上面新增服務(wù)器 CS4 時(shí)，CS4 只分擔(dān)了 CS1 服務(wù)器的負(fù)載，服務(wù)器 CS2 和 CS3 并沒(méi)有因?yàn)?CS4 服務(wù)器的加入而減少負(fù)載壓力；如果 CS4 服務(wù)器的性能與原有服務(wù)器的性能一致甚至可能更高，那么這種結(jié)果并不是我們所期望的；

虛擬節(jié)點(diǎn)

針對(duì)上面的問(wèn)題，我們可以通過(guò)：引入虛擬節(jié)點(diǎn)來(lái)解決負(fù)載不均衡的問(wèn)題：

即將每臺(tái)物理服務(wù)器虛擬為一組虛擬服務(wù)器，將虛擬服務(wù)器放置到哈希環(huán)上，如果要確定對(duì)象的服務(wù)器，需先確定對(duì)象的虛擬服務(wù)器，再由虛擬服務(wù)器確定物理服務(wù)器；

如下圖所示：

在圖中：o1 和 o2 表示對(duì)象，v1 ~ v6 表示虛擬服務(wù)器，s1 ~ s3 表示實(shí)際的物理服務(wù)器；

虛擬節(jié)點(diǎn)的計(jì)算

虛擬節(jié)點(diǎn)的hash計(jì)算通常可以采用：對(duì)應(yīng)節(jié)點(diǎn)的IP地址加數(shù)字編號(hào)后綴 hash（10.24.23.227#1) 的方式；

舉個(gè)例子，node-1節(jié)點(diǎn)IP為10.24.23.227，正常計(jì)算node-1的hash值：

hash（10.24.23.227#1）% 2^32

假設(shè)我們給node-1設(shè)置三個(gè)虛擬節(jié)點(diǎn)，node-1#1、node-1#2、node-1#3，對(duì)它們進(jìn)行hash后取模：

hash（10.24.23.227#1）% 2^32
hash（10.24.23.227#2）% 2^32
hash（10.24.23.227#3）% 2^32

注意：
分配的虛擬節(jié)點(diǎn)個(gè)數(shù)越多，映射在hash環(huán)上才會(huì)越趨于均勻，節(jié)點(diǎn)太少的話很難看出效果；
引入虛擬節(jié)點(diǎn)的同時(shí)也增加了新的問(wèn)題，要做虛擬節(jié)點(diǎn)和真實(shí)節(jié)點(diǎn)間的映射，對(duì)象key->虛擬節(jié)點(diǎn)->實(shí)際節(jié)點(diǎn)之間的轉(zhuǎn)換；

使用場(chǎng)景

一致性hash在分布式系統(tǒng)中應(yīng)該是實(shí)現(xiàn)負(fù)載均衡的首選算法，它的實(shí)現(xiàn)比較靈活，既可以在客戶端實(shí)現(xiàn)，也可以在中間件上實(shí)現(xiàn)，比如日常使用較多的緩存中間件memcached和redis集群都有用到它；

memcached的集群比較特殊，嚴(yán)格來(lái)說(shuō)它只能算是偽集群，因?yàn)樗姆?wù)器之間不能通信，請(qǐng)求的分發(fā)路由完全靠客戶端來(lái)的計(jì)算出緩存對(duì)象應(yīng)該落在哪個(gè)服務(wù)器上，而它的路由算法用的就是一致性hash；

還有redis集群中hash槽的概念，雖然實(shí)現(xiàn)不盡相同，但思想萬(wàn)變不離其宗，看完本篇的一致性hash，你再去理解redis槽位就輕松多了；

其它的應(yīng)用場(chǎng)景還有很多：

RPC框架Dubbo用來(lái)選擇服務(wù)提供者
分布式關(guān)系數(shù)據(jù)庫(kù)分庫(kù)分表：數(shù)據(jù)與節(jié)點(diǎn)的映射關(guān)系
LVS負(fù)載均衡調(diào)度器
……

一致性Hash算法實(shí)現(xiàn)

下面我們根據(jù)上面的講述，使用Golang實(shí)現(xiàn)一個(gè)一致性Hash算法，這個(gè)算法具有一些下面的功能特性：

一致性Hash核心算法；
支持自定義Hash算法；
支持自定義虛擬節(jié)點(diǎn)個(gè)數(shù)；

具體源代碼見(jiàn)：
https://github.com/JasonkayZK/consistent-hashing-demo

下面開(kāi)始實(shí)現(xiàn)吧！

結(jié)構(gòu)體、錯(cuò)誤以及常量定義

① 結(jié)構(gòu)體定義

首先定義每一臺(tái)緩存服務(wù)器的數(shù)據(jù)結(jié)構(gòu)：

core/host.go

type Host struct {
 // the host id: ip:port
 Name string

 // the load bound of the host
 LoadBound int64
}

其中：

Name：緩存服務(wù)器的Ip地址 + 端口，如：127.0.0.1:8000
LoadBound：緩存服務(wù)器當(dāng)前處理的“請(qǐng)求”緩存數(shù)，這個(gè)字段在后文含有負(fù)載邊界值的一致性Hash中會(huì)用到；

其次，定義一致性Hash的結(jié)構(gòu)：

core/algorithm.go

// Consistent is an implementation of consistent-hashing-algorithm
type Consistent struct {
 // the number of replicas
 replicaNum int

 // the total loads of all replicas
 totalLoad int64

 // the hash function for keys
 hashFunc func(key string) uint64

 // the map of virtual nodes to hosts
 hostMap map[string]*Host

 // the map of hashed virtual nodes to host name
 replicaHostMap map[uint64]string

 // the hash ring
 sortedHostsHashSet []uint64

 // the hash ring lock
 sync.RWMutex
}

其中：

replicaNum：表示每個(gè)真實(shí)的緩存服務(wù)器在Hash環(huán)中存在的虛擬節(jié)點(diǎn)數(shù)；
totalLoad：所有物理服務(wù)器對(duì)應(yīng)的總緩存“請(qǐng)求”數(shù)（這個(gè)字段在后文含有負(fù)載邊界值的一致性Hash中會(huì)用到）；
hashFunc：計(jì)算Hash環(huán)映射以及Key映射的散列函數(shù)；
hostMap：物理服務(wù)器名稱(chēng)對(duì)應(yīng)的Host結(jié)構(gòu)體映射；
replicaHostMap：Hash環(huán)中虛擬節(jié)點(diǎn)對(duì)應(yīng)真實(shí)緩存服務(wù)器名稱(chēng)的映射；
sortedHostsHashSet：Hash環(huán)；
sync.RWMutex：操作Hash環(huán)時(shí)用到的讀寫(xiě)鎖；

大概的結(jié)構(gòu)如上所示，下面我們來(lái)看一些常量和錯(cuò)誤的定義；

② 常量和錯(cuò)誤定義

常量的定義如下：

core/algorithm.go

const (
 // The format of the host replica name
 hostReplicaFormat=`%s%d`
)

var (
 // the default number of replicas
 defaultReplicaNum=10

 // the load bound factor
 // ref: https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
 loadBoundFactor=0.25

 // the default Hash function for keys
 defaultHashFunc=func(key string) uint64 {
  out :=sha512.Sum512([]byte(key))
  return binary.LittleEndian.Uint64(out[:])
 }
)

分別表示：

defaultReplicaNum：默認(rèn)情況下，每個(gè)真實(shí)的物理服務(wù)器在Hash環(huán)中虛擬節(jié)點(diǎn)的個(gè)數(shù)；
loadBoundFactor：負(fù)載邊界因數(shù)（這個(gè)字段在后文含有負(fù)載邊界值的一致性Hash中會(huì)用到）；
defaultHashFunc：默認(rèn)的散列函數(shù)，這里用到的是SHA512算法，并取的是unsigned int64，這一點(diǎn)和上面介紹的0~2^32-1有所區(qū)別！
hostReplicaFormat：虛擬節(jié)點(diǎn)名稱(chēng)格式，這里的虛擬節(jié)點(diǎn)的格式為：%s%d，和上文提到的10.24.23.227#1的格式有所區(qū)別，但是道理是一樣的！

還有一些錯(cuò)誤的定義：

core/error.go

var (
 ErrHostAlreadyExists=errors.New("host already exists")

 ErrHostNotFound=errors.New("host not found")
)

分別表示服務(wù)器已經(jīng)注冊(cè)，以及緩存服務(wù)器未找到；

下面來(lái)看具體的方法實(shí)現(xiàn)！

注冊(cè)/注銷(xiāo)緩存服務(wù)器

① 注冊(cè)緩存服務(wù)器

注冊(cè)緩存服務(wù)器的代碼如下：

core/algorithm.go

func (c *Consistent) RegisterHost(hostName string) error {
 c.Lock()
 defer c.Unlock()

 if _, ok :=c.hostMap[hostName]; ok {
  return ErrHostAlreadyExists
 }

 c.hostMap[hostName]=&Host{
  Name:      hostName,
  LoadBound: 0,
 }

 for i :=0; i < c.replicaNum; i++ {
  hashedIdx :=c.hashFunc(fmt.Sprintf(hostReplicaFormat, hostName, i))
  c.replicaHostMap[hashedIdx]=hostName
  c.sortedHostsHashSet=append(c.sortedHostsHashSet, hashedIdx)
 }

 // sort hashes in ascending order
 sort.Slice(c.sortedHostsHashSet, func(i int, j int) bool {
  if c.sortedHostsHashSet[i] < c.sortedHostsHashSet[j] {
   return true
  }
  return false
 })

 return nil
}

代碼比較簡(jiǎn)單，簡(jiǎn)單說(shuō)一下；

首先，檢查服務(wù)器是否已經(jīng)注冊(cè)，如果已經(jīng)注冊(cè)，則直接返回已經(jīng)注冊(cè)的錯(cuò)誤；

隨后，創(chuàng)建一個(gè)Host對(duì)象，并且在 for 循環(huán)中創(chuàng)建多個(gè)虛擬節(jié)點(diǎn)：

根據(jù) hashFunc 計(jì)算服務(wù)器散列值【注：此處計(jì)算的散列值可能和之前的值存在沖突，本實(shí)現(xiàn)中暫不考慮這種場(chǎng)景】；
將散列值加入 replicaHostMap 中；
將散列值加入 sortedHostsHashSet 中；

最后，對(duì)Hash環(huán)進(jìn)行排序；

這里使用數(shù)組作為Hash環(huán)只是為了便于說(shuō)明，在實(shí)際實(shí)現(xiàn)中建議選用其他數(shù)據(jù)結(jié)構(gòu)進(jìn)行實(shí)現(xiàn)，以獲取更好的性能；

當(dāng)緩存服務(wù)器信息寫(xiě)入 replicaHostMap 映射以及 Hash 環(huán)后，即完成了緩存服務(wù)器的注冊(cè)；

② 注銷(xiāo)緩存服務(wù)器

注銷(xiāo)緩存服務(wù)器的代碼如下：

core/algorithm.go

func (c *Consistent) UnregisterHost(hostName string) error {
 c.Lock()
 defer c.Unlock()

 if _, ok :=c.hostMap[hostName]; !ok {
  return ErrHostNotFound
 }

 delete(c.hostMap, hostName)

 for i :=0; i < c.replicaNum; i++ {
  hashedIdx :=c.hashFunc(fmt.Sprintf(hostReplicaFormat, hostName, i))
  delete(c.replicaHostMap, hashedIdx)
  c.delHashIndex(hashedIdx)
 }

 return nil
}

// Remove hashed host index from the hash ring
func (c *Consistent) delHashIndex(val uint64) {
 idx :=-1
 l :=0
 r :=len(c.sortedHostsHashSet) - 1
 for l <=r {
  m :=(l + r) / 2
  if c.sortedHostsHashSet[m]==val {
   idx=m
   break
  } else if c.sortedHostsHashSet[m] < val {
   l=m + 1
  } else if c.sortedHostsHashSet[m] > val {
   r=m - 1
  }
 }
 if idx !=-1 {
  c.sortedHostsHashSet=append(c.sortedHostsHashSet[:idx], c.sortedHostsHashSet[idx+1:]...)
 }
}

和注冊(cè)緩存服務(wù)器相反，將服務(wù)器在 Map 映射以及 Hash 環(huán)中去除即完成了注銷(xiāo)；

這里的邏輯和上面注冊(cè)的邏輯極為類(lèi)似，這里不再贅述！

查詢Key（核心）

查詢 Key 是整個(gè)一致性 Hash 算法的核心，但是實(shí)現(xiàn)起來(lái)也并不復(fù)雜；

代碼如下：

core/algorithm.go

func (c *Consistent) GetKey(key string) (string, error) {
 hashedKey :=c.hashFunc(key)
 idx :=c.searchKey(hashedKey)
 return c.replicaHostMap[c.sortedHostsHashSet[idx]], nil
}

func (c *Consistent) searchKey(key uint64) int {
 idx :=sort.Search(len(c.sortedHostsHashSet), func(i int) bool {
  return c.sortedHostsHashSet[i] >=key
 })

 if idx >=len(c.sortedHostsHashSet) {
  // make search as a ring
  idx=0
 }

 return idx
}

代碼首先計(jì)算 key 的散列值；

隨后，在Hash環(huán)上“順時(shí)針”尋找可以緩存的第一臺(tái)緩存服務(wù)器：

idx :=sort.Search(len(c.sortedHostsHashSet), func(i int) bool {
    return c.sortedHostsHashSet[i] >=key
})

注意到，如果 key 比當(dāng)前Hash環(huán)中最大的虛擬節(jié)點(diǎn)的 hash 值還大，則選擇當(dāng)前 Hash環(huán) 中 hash 值最小的一個(gè)節(jié)點(diǎn)（即“環(huán)形”的邏輯）：

if idx >=len(c.sortedHostsHashSet) {
    // make search as a ring
    idx=0
}

searchKey 返回了虛擬節(jié)點(diǎn)在 Hash 環(huán)數(shù)組中的 index；

隨后，我們使用 map 返回 index 對(duì)應(yīng)的緩存服務(wù)器的名稱(chēng)即可；

至此，一致性 Hash 算法基本實(shí)現(xiàn)，接下來(lái)我們來(lái)驗(yàn)證一下；

一致性Hash算法實(shí)踐與檢驗(yàn)

算法驗(yàn)證前準(zhǔn)備

① 緩存服務(wù)器準(zhǔn)備

在驗(yàn)證算法之前，我們還需要準(zhǔn)備幾臺(tái)緩存服務(wù)器；

為了簡(jiǎn)單起見(jiàn)，這里使用了 HTTP 服務(wù)器作為緩存服務(wù)器，具體代碼如下所示：

server/main.go

package main

import (
 "flag"
 "fmt"
 "net/http"
 "sync"
 "time"
)

type CachedMap struct {
 KvMap sync.Map
 Lock  sync.RWMutex
}

var (
 cache=CachedMap{KvMap: sync.Map{}}

 port=flag.String("p", "8080", "port")

 regHost="http://localhost:18888"

 expireTime=10
)

func main() {
 flag.Parse()

 stopChan :=make(chan interface{})
 startServer(*port)
 <-stopChan
}

func startServer(port string) {
 hostName :=fmt.Sprintf("localhost:%s", port)

 fmt.Printf("start server: %s\n", port)

 err :=registerHost(hostName)
 if err !=nil {
  panic(err)
 }

 http.HandleFunc("/", kvHandle)
 err=http.ListenAndServe(":"+port, nil)
 if err !=nil {
  err=unregisterHost(hostName)
  if err !=nil {
   panic(err)
  }
  panic(err)
 }
}

func kvHandle(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 if _, ok :=cache.KvMap.Load(r.Form["key"][0]); !ok {
  val :=fmt.Sprintf("hello: %s", r.Form["key"][0])
  cache.KvMap.Store(r.Form["key"][0], val)
  fmt.Printf("cached key: {%s: %s}\n", r.Form["key"][0], val)

  time.AfterFunc(time.Duration(expireTime)*time.Second, func() {
   cache.KvMap.Delete(r.Form["key"][0])
   fmt.Printf("removed cached key after 3s: {%s: %s}\n", r.Form["key"][0], val)
  })
 }

 val, _ :=cache.KvMap.Load(r.Form["key"][0])

 _, err :=fmt.Fprintf(w, val.(string))
 if err !=nil {
  panic(err)
 }
}

func registerHost(host string) error {
 resp, err :=http.Get(fmt.Sprintf("%s/register?host=%s", regHost, host))
 if err !=nil {
  return err
 }
 defer resp.Body.Close()

 return nil
}

func unregisterHost(host string) error {
 resp, err :=http.Get(fmt.Sprintf("%s/unregister?host=%s", regHost, host))
 if err !=nil {
  return err
 }
 defer resp.Body.Close()

 return nil
}

代碼接受由命令行指定的 -p 參數(shù)指定服務(wù)器端口號(hào)；

代碼執(zhí)行后，會(huì)調(diào)用 startServer 函數(shù)啟動(dòng)一個(gè)http服務(wù)器；

在 startServer 函數(shù)中，首先調(diào)用 registerHost 在代理服務(wù)器上進(jìn)行注冊(cè)（下文會(huì)講），并監(jiān)聽(tīng) /路徑，具體代碼如下：

func startServer(port string) {
 hostName :=fmt.Sprintf("localhost:%s", port)

 fmt.Printf("start server: %s\n", port)

 err :=registerHost(hostName)
 if err !=nil {
  panic(err)
 }

 http.HandleFunc("/", kvHandle)
 err=http.ListenAndServe(":"+port, nil)
 if err !=nil {
  err=unregisterHost(hostName)
  if err !=nil {
   panic(err)
  }
  panic(err)
 }
}

kvHandle 函數(shù)對(duì)請(qǐng)求進(jìn)行處理：

func kvHandle(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 if _, ok :=cache.KvMap.Load(r.Form["key"][0]); !ok {
  val :=fmt.Sprintf("hello: %s", r.Form["key"][0])
  cache.KvMap.Store(r.Form["key"][0], val)
  fmt.Printf("cached key: {%s: %s}\n", r.Form["key"][0], val)

  time.AfterFunc(time.Duration(expireTime)*time.Second, func() {
   cache.KvMap.Delete(r.Form["key"][0])
   fmt.Printf("removed cached key after 3s: {%s: %s}\n", r.Form["key"][0], val)
  })
 }

 val, _ :=cache.KvMap.Load(r.Form["key"][0])

 _, err :=fmt.Fprintf(w, val.(string))
 if err !=nil {
  panic(err)
 }
}

首先，解析來(lái)自路徑的參數(shù)：?key=xxx；

隨后，查詢服務(wù)器中的緩存（為了簡(jiǎn)單起見(jiàn)，這里使用 sync.Map 來(lái)模擬緩存）：

如果緩存不存在，則寫(xiě)入緩存，并通過(guò) time.AfterFunc 設(shè)置緩存過(guò)期時(shí)間（expireTime）；

最后，返回緩存；

② 緩存代理服務(wù)器準(zhǔn)備

有了緩存服務(wù)器之后，我們還需要一個(gè)代理服務(wù)器來(lái)選擇具體選擇哪個(gè)緩存服務(wù)器來(lái)請(qǐng)求；

代碼如下：

proxy/proxy.go

package proxy

import (
 "fmt"
 "github.com/jasonkayzk/consistent-hashing-demo/core"
 "io/ioutil"
 "net/http"
 "time"
)

type Proxy struct {
 consistent *core.Consistent
}

// NewProxy creates a new Proxy
func NewProxy(consistent *core.Consistent) *Proxy {
 proxy :=&Proxy{
  consistent: consistent,
 }
 return proxy
}

func (p *Proxy) GetKey(key string) (string, error) {

 host, err :=p.consistent.GetKey(key)
 if err !=nil {
  return "", err
 }

 resp, err :=http.Get(fmt.Sprintf("http://%s?key=%s", host, key))
 if err !=nil {
  return "", err
 }
 defer resp.Body.Close()

 body, _ :=ioutil.ReadAll(resp.Body)

 fmt.Printf("Response from host %s: %s\n", host, string(body))

 return string(body), nil
}

func (p *Proxy) RegisterHost(host string) error {

 err :=p.consistent.RegisterHost(host)
 if err !=nil {
  return err
 }

 fmt.Println(fmt.Sprintf("register host: %s success", host))
 return nil
}

func (p *Proxy) UnregisterHost(host string) error {
 err :=p.consistent.UnregisterHost(host)
 if err !=nil {
  return err
 }

 fmt.Println(fmt.Sprintf("unregister host: %s success", host))
 return nil
}

代理服務(wù)器的邏輯很簡(jiǎn)單，就是創(chuàng)建一個(gè)一致性Hash結(jié)構(gòu)： Consistent，把 Consistent 和請(qǐng)求緩存服務(wù)器的邏輯進(jìn)行了一層封裝；

算法驗(yàn)證

啟動(dòng)代理服務(wù)器

啟動(dòng)代理服務(wù)器的代碼如下：

package main

import (
 "fmt"
 "github.com/jasonkayzk/consistent-hashing-demo/core"
 "github.com/jasonkayzk/consistent-hashing-demo/proxy"
 "net/http"
)

var (
 port="18888"

 p=proxy.NewProxy(core.NewConsistent(10, nil))
)

func main() {
 stopChan :=make(chan interface{})
 startServer(port)
 <-stopChan
}

func startServer(port string) {
 http.HandleFunc("/register", registerHost)
 http.HandleFunc("/unregister", unregisterHost)
 http.HandleFunc("/key", getKey)

 fmt.Printf("start proxy server: %s\n", port)

 err :=http.ListenAndServe(":"+port, nil)
 if err !=nil {
  panic(err)
 }
}

func registerHost(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 err :=p.RegisterHost(r.Form["host"][0])
 if err !=nil {
  w.WriteHeader(http.StatusInternalServerError)
  _, _=fmt.Fprintf(w, err.Error())
  return
 }

 _, _=fmt.Fprintf(w, fmt.Sprintf("register host: %s success", r.Form["host"][0]))
}

func unregisterHost(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 err :=p.UnregisterHost(r.Form["host"][0])
 if err !=nil {
  w.WriteHeader(http.StatusInternalServerError)
  _, _=fmt.Fprintf(w, err.Error())
  return
 }

 _, _=fmt.Fprintf(w, fmt.Sprintf("unregister host: %s success", r.Form["host"][0]))
}

func getKey(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 val, err :=p.GetKey(r.Form["key"][0])
 if err !=nil {
  w.WriteHeader(http.StatusInternalServerError)
  _, _=fmt.Fprintf(w, err.Error())
  return
 }

 _, _=fmt.Fprintf(w, fmt.Sprintf("key: %s, val: %s", r.Form["key"][0], val))
}

和緩存服務(wù)器類(lèi)似，這里采用 HTTP 服務(wù)器來(lái)模擬；

代理服務(wù)器監(jiān)聽(tīng) 18888 端口的幾個(gè)路由：

/register：注冊(cè)緩存服務(wù)器；
/unregister：注銷(xiāo)緩存服務(wù)器；
/key：查詢緩存Key；

這里為了簡(jiǎn)單起見(jiàn)，使用了這種方式進(jìn)行服務(wù)注冊(cè)，實(shí)際使用時(shí)請(qǐng)使用其他組件進(jìn)行實(shí)現(xiàn)！

接下來(lái)啟動(dòng)緩存服務(wù)器：

start proxy server: 18888

啟動(dòng)緩存服務(wù)器

分別啟動(dòng)三個(gè)緩存服務(wù)器：

$ go run server/main.go -p 8080
start server: 8080

$ go run server/main.go -p 8081
start server: 8081

$ go run server/main.go -p 8082
start server: 8082

同時(shí)，代理服務(wù)器輸出：

register host: localhost:8080 success
register host: localhost:8081 success
register host: localhost:8082 success

可以看到緩存服務(wù)器已經(jīng)成功注冊(cè)；

請(qǐng)求代理服務(wù)器獲取Key

可以使用 curl 命令請(qǐng)求代理服務(wù)器獲取緩存 key：

$ curl localhost:18888/key?key=123
key: 123, val: hello: 123

此時(shí)，代理服務(wù)器輸出：

Response from host localhost:8080: hello: 123

同時(shí)，8000端口的緩存服務(wù)器輸出：

cached key: {123: hello: 123}
removed cached key after 10s: {123: hello: 123}

可以看到，8000端口的服務(wù)器對(duì)key值進(jìn)行了緩存，并在10秒后清除了緩存；

嘗試多次獲取Key

嘗試獲取多個(gè)Key：

Response from host localhost:8082: hello: 45363456
Response from host localhost:8080: hello: 4
Response from host localhost:8082: hello: 1
Response from host localhost:8080: hello: 2
Response from host localhost:8082: hello: 3
Response from host localhost:8080: hello: 4
Response from host localhost:8082: hello: 5
Response from host localhost:8080: hello: 6
Response from host localhost:8082: hello: sdkbnfoerwtnbre
Response from host localhost:8082: hello: sd45555254tg423i5gvj4v5
Response from host localhost:8081: hello: 0
Response from host localhost:8082: hello: 032452345

可以看到不同的key被散列到了不同的緩存服務(wù)器；

接下來(lái)我們通過(guò)debug查看具體的變量來(lái)一探究竟；

通過(guò)Debug查看注冊(cè)和Hash環(huán)

開(kāi)啟debug，并注冊(cè)單個(gè)緩存服務(wù)器后，查看 Consistent 中的值：

注冊(cè)三個(gè)緩存服務(wù)器后，查看 Consistent 中的值：

從debug中的變量，我們就可以很清楚的看到注冊(cè)不同數(shù)量的服務(wù)器時(shí)，一致性Hash上服務(wù)器的動(dòng)態(tài)變化！

以上就是基本的一致性Hash算法的實(shí)現(xiàn)了！

但是很多時(shí)候，我們的緩存服務(wù)器需要同時(shí)處理大量的緩存請(qǐng)求，而通過(guò)上面的算法，我們總是會(huì)去同一臺(tái)緩存服務(wù)器去獲取緩存數(shù)據(jù)；

如果很多的熱點(diǎn)數(shù)據(jù)都落在了同一臺(tái)緩存服務(wù)器上，則可能會(huì)出現(xiàn)性能瓶頸；

Google 在2017年提出了： 含有負(fù)載邊界值的一致性Hash算法；

下面我們?cè)诨镜囊恢滦訦ash算法的基礎(chǔ)上，實(shí)現(xiàn)含有負(fù)載邊界值的一致性Hash！

含有負(fù)載邊界值的一致性Hash

算法描述

17年時(shí)，Google 提出了含有負(fù)載邊界值的一致性Hash算法，此算法主要應(yīng)用于在實(shí)現(xiàn)一致性的同時(shí)，實(shí)現(xiàn)負(fù)載的平均性；

此算法最初由 Vimeo 的 Andrew Rodland 在 haproxy 中實(shí)現(xiàn)并開(kāi)源；
參考：
https://ai.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html
arvix論文地址：
https://arxiv.org/abs/1608.01350

這個(gè)算法將緩存服務(wù)器視為一個(gè)含有一定容量的桶（可以簡(jiǎn)單理解為Hash桶），將客戶端視為球，則平均性目標(biāo)表示為：所有約等于平均密度（球的數(shù)量除以桶的數(shù)量）：

實(shí)際使用時(shí)，可以設(shè)定一個(gè)平均密度的參數(shù) ε，將每個(gè)桶的容量設(shè)置為平均加載時(shí)間的下上限 (1+ε)；

具體的計(jì)算過(guò)程如下：

首先，計(jì)算 key 的 Hash 值；
隨后，沿著 Hash 環(huán)順時(shí)針尋找第一臺(tái)滿足條件（平均容量限制）的服務(wù)器；
獲取緩存；

例如下面的圖：

使用哈希函數(shù)將 6 個(gè)球和 3 個(gè)桶分配給 Hash環(huán) 上的隨機(jī)位置，假設(shè)每個(gè)桶的容量設(shè)置為 2，按 ID 值的遞增順序分配球；

1號(hào)球順時(shí)針移動(dòng)，進(jìn)入C桶；
2號(hào)球進(jìn)入A桶；
3號(hào)和4號(hào)球進(jìn)入B桶；
5號(hào)球進(jìn)入C桶；
然后6號(hào)球順時(shí)針移動(dòng)，首先擊中B桶；但是桶 B 的容量為 2，并且已經(jīng)包含球 3 和 4，所以球 6 繼續(xù)移動(dòng)到達(dá)桶 C，但該桶也已滿；最后，球 6 最終進(jìn)入具有備用插槽的桶 A；

算法實(shí)現(xiàn)

在上面基本一致性 Hash 算法實(shí)現(xiàn)的基礎(chǔ)上，我們繼續(xù)實(shí)現(xiàn)含有負(fù)載邊界值的一致性Hash算法；

在核心算法中添加根據(jù)負(fù)載情況查詢Key的函數(shù)，以及增加/釋放負(fù)載值的函數(shù)；

根據(jù)負(fù)載情況查詢 Key 的函數(shù)：

core/algorithm.go

func (c *Consistent) GetKeyLeast(key string) (string, error) {
 c.RLock()
 defer c.RUnlock()

 if len(c.replicaHostMap)==0 {
  return "", ErrHostNotFound
 }

 hashedKey :=c.hashFunc(key)
 idx :=c.searchKey(hashedKey) // Find the first host that may serve the key

 i :=idx
 for {
  host :=c.replicaHostMap[c.sortedHostsHashSet[i]]
  loadChecked, err :=c.checkLoadCapacity(host)
  if err !=nil {
   return "", err
  }
  if loadChecked {
   return host, nil
  }
  i++

  // if idx goes to the end of the ring, start from the beginning
  if i >=len(c.replicaHostMap) {
   i=0
  }
 }
}

func (c *Consistent) checkLoadCapacity(host string) (bool, error) {

 // a safety check if someone performed c.Done more than needed
 if c.totalLoad < 0 {
  c.totalLoad=0
 }

 var avgLoadPerNode float64
 avgLoadPerNode=float64((c.totalLoad + 1) / int64(len(c.hostMap)))
 if avgLoadPerNode==0 {
  avgLoadPerNode=1
 }
 avgLoadPerNode=math.Ceil(avgLoadPerNode * (1 + loadBoundFactor))

 candidateHost, ok :=c.hostMap[host]
 if !ok {
  return false, ErrHostNotFound
 }

 if float64(candidateHost.LoadBound)+1 <=avgLoadPerNode {
  return true, nil
 }

 return false, nil
}

在 GetKeyLeast 函數(shù)中，首先根據(jù) searchKey 函數(shù)，順時(shí)針獲取可能滿足條件的第一個(gè)虛擬節(jié)點(diǎn)；

隨后調(diào)用 checkLoadCapacity 校驗(yàn)當(dāng)前緩存服務(wù)器的負(fù)載數(shù)是否滿足條件：

candidateHost.LoadBound+1 <=(c.totalLoad + 1) / len(hosts) * (1 + loadBoundFactor)

如果不滿足條件，則沿著 Hash 環(huán)走到下一個(gè)虛擬節(jié)點(diǎn)，繼續(xù)判斷是否滿足條件，直到滿足條件；

這里使用的是無(wú)條件的 for 循環(huán)，因?yàn)橐欢ù嬖诘陀?平均負(fù)載(1 + loadBoundFactor) 的虛擬節(jié)點(diǎn)！*

增加/釋放負(fù)載值的函數(shù)：

core/algorithm.go

func (c *Consistent) Inc(hostName string) {
 c.Lock()
 defer c.Unlock()

 atomic.AddInt64(&c.hostMap[hostName].LoadBound, 1)
 atomic.AddInt64(&c.totalLoad, 1)
}

func (c *Consistent) Done(host string) {
 c.Lock()
 defer c.Unlock()

 if _, ok :=c.hostMap[host]; !ok {
  return
 }
 atomic.AddInt64(&c.hostMap[host].LoadBound, -1)
 atomic.AddInt64(&c.totalLoad, -1)
}

邏輯比較簡(jiǎn)單，就是原子的對(duì)對(duì)應(yīng)緩存服務(wù)器進(jìn)行負(fù)載加減一操作；

算法測(cè)試

修改代理服務(wù)器代碼

在代理服務(wù)器中增加路由：

proxy/proxy.go

func (p *Proxy) GetKeyLeast(key string) (string, error) {

 host, err :=p.consistent.GetKeyLeast(key)
 if err !=nil {
  return "", err
 }
 p.consistent.Inc(host)

 time.AfterFunc(time.Second*10, func() { // drop the host after 10 seconds(for testing)!
  fmt.Printf("dropping host: %s after 10 second\n", host)
  p.consistent.Done(host)
 })

 resp, err :=http.Get(fmt.Sprintf("http://%s?key=%s", host, key))
 if err !=nil {
  return "", err
 }
 defer resp.Body.Close()

 body, _ :=ioutil.ReadAll(resp.Body)

 fmt.Printf("Response from host %s: %s\n", host, string(body))

 return string(body), nil
}

注意：這里模擬的是單個(gè)key請(qǐng)求可能會(huì)持續(xù)10s鐘；

啟動(dòng)代理服務(wù)器時(shí)增加路由：

main.go

func startServer(port string) {
 
    // ......
    
 http.HandleFunc("/key_least", getKeyLeast)

 // ......
}

func getKeyLeast(w http.ResponseWriter, r *http.Request) {
 _=r.ParseForm()

 val, err :=p.GetKeyLeast(r.Form["key"][0])
 if err !=nil {
  w.WriteHeader(http.StatusInternalServerError)
  _, _=fmt.Fprintf(w, err.Error())
  return
 }

 _, _=fmt.Fprintf(w, fmt.Sprintf("key: %s, val: %s", r.Form["key"][0], val))
}

測(cè)試

啟動(dòng)代理服務(wù)器，并開(kāi)啟三臺(tái)緩存服務(wù)器；

通過(guò)下面的命令獲取含有負(fù)載邊界的Key：

$ curl localhost:18888/key_least?key=123
key: 123, val: hello: 123

多次請(qǐng)求后的結(jié)果如下：

```
start proxy server: 18888
register host: localhost:8080 success
register host: localhost:8081 success
register host: localhost:8082 success

Response from host localhost:8080: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8081: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8081: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8081: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8081: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8080: hello: 123
Response from host localhost:8082: hello: 123
Response from host localhost:8082: hello: 123
```

可以看到，緩存被均攤到了其他服務(wù)器（這是由于一個(gè)緩存請(qǐng)求會(huì)持續(xù)10s導(dǎo)致的）！

總結(jié)

本文拋磚引玉的講解了一致性Hash算法的原理，并提供了Go的實(shí)現(xiàn)；

在此基礎(chǔ)之上，根據(jù) Google 的論文實(shí)現(xiàn)了帶有負(fù)載邊界的一致性Hash算法；

當(dāng)然上面的代碼在實(shí)際生產(chǎn)環(huán)境下仍然需要部分改進(jìn)，如：

服務(wù)注冊(cè)；
緩存服務(wù)器實(shí)現(xiàn)；
心跳檢測(cè)；
……

大家在實(shí)際使用時(shí)，可以根據(jù)需要，搭配實(shí)際的組件！

希表和哈希函數(shù)

在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間是建立一個(gè)確定的對(duì)應(yīng)關(guān)系（映射函數(shù)），使每個(gè)關(guān)鍵字和一個(gè)存儲(chǔ)位置能唯一對(duì)應(yīng)。

這個(gè)映射函數(shù)稱(chēng)為哈希函數(shù)，根據(jù)這個(gè)原則建立的表稱(chēng)為哈希表(Hash Table)，也叫散列表。

以上描述，如果通過(guò)數(shù)學(xué)形式來(lái)描述就是：

若查找關(guān)鍵字為 key，則其值存放在 f(key) 的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。

注：哈希查找與線性表查找和樹(shù)表查找最大的區(qū)別在于，不用數(shù)值比較。

沖突

若 key1 ≠ key2 ，而 f(key1)=f(key2)，這種情況稱(chēng)為沖突(Collision)。

根據(jù)哈希函數(shù)f(key)和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這一映射過(guò)程稱(chēng)為構(gòu)造哈希表。

構(gòu)造哈希表這個(gè)場(chǎng)景就像汽車(chē)找停車(chē)位，如果車(chē)位被人占了，只能找空的地方停。

構(gòu)造哈希表

由以上內(nèi)容可知，哈希查找本身其實(shí)不費(fèi)吹灰之力，問(wèn)題的關(guān)鍵在于如何構(gòu)造哈希表和處理沖突。

常見(jiàn)的構(gòu)造哈希表的方法有 5 種：

（1）直接定址法

說(shuō)白了，就是小學(xué)時(shí)學(xué)過(guò)的一元一次方程。

即 f(key)=a * key + b。其中，a和b 是常數(shù)。

（2）數(shù)字分析法

假設(shè)關(guān)鍵字是R進(jìn)制數(shù)（如十進(jìn)制）。并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可選取關(guān)鍵字的若干數(shù)位組成哈希地址。

選取的原則是使得到的哈希地址盡量避免沖突，即所選數(shù)位上的數(shù)字盡可能是隨機(jī)的。

（3）平方取中法

取關(guān)鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，僅取其中的幾位為地址不一定合適；

而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此得到的哈希地址隨機(jī)性更大。取的位數(shù)由表長(zhǎng)決定。

（4）除留余數(shù)法

取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為哈希地址。

即 f(key)=key % p (p ≤ m)

這是一種最簡(jiǎn)單、最常用的方法，它不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。

注意：p的選擇很重要，如果選的不好，容易產(chǎn)生沖突。根據(jù)經(jīng)驗(yàn)，一般情況下可以選p為素?cái)?shù)。

（5）隨機(jī)數(shù)法

選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 f(key)=random(key)。

通常，在關(guān)鍵字長(zhǎng)度不等時(shí)采用此法構(gòu)造哈希函數(shù)較為恰當(dāng)。

解決沖突

設(shè)計(jì)合理的哈希函數(shù)可以減少?zèng)_突，但不能完全避免沖突。

所以需要有解決沖突的方法，常見(jiàn)有兩類(lèi)

（1）開(kāi)放定址法

如果兩個(gè)數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)。

當(dāng)程序查找哈希表時(shí)，如果沒(méi)有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素，程序就會(huì)繼續(xù)往后查找，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)。

例子

若要將一組關(guān)鍵字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。

采用除留余數(shù)法構(gòu)造哈希表；采用開(kāi)放定址法處理沖突。

不妨設(shè)選取的p和m為13，由 f(key)=key % 13 可以得到下表。

需要注意的是，在上圖中有兩個(gè)關(guān)鍵字的探查次數(shù)為 2 ，其他都是1。

這個(gè)過(guò)程是這樣的：

a. 12 % 13 結(jié)果是12，而它的前面有個(gè) 25 ，25 % 13 也是12，存在沖突。

我們使用開(kāi)放定址法 (12 + 1) % 13=0，沒(méi)有沖突，完成。

b. 35 % 13 結(jié)果是 9，而它的前面有個(gè) 9，9 % 13也是 9，存在沖突。

我們使用開(kāi)放定址法 (9 + 1) % 13=10，沒(méi)有沖突，完成。

（2）拉鏈法

將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過(guò)程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線性查找方法。

在這種方法中，哈希表中每個(gè)單元存放的不再是記錄本身，而是相應(yīng)同義詞單鏈表的頭指針。

例子

如果對(duì)開(kāi)放定址法例子中提到的序列使用拉鏈法，得到的結(jié)果如下圖所示：

實(shí)現(xiàn)一個(gè)哈希表

假設(shè)要實(shí)現(xiàn)一個(gè)哈希表，要求

a. 哈希函數(shù)采用除留余數(shù)法，即 f(key)=key % p (p ≤ m)

b. 解決沖突采用開(kāi)放定址法，即 f2(key)=(f(key)+i) % size (p ≤ m)

（1）定義哈希表的數(shù)據(jù)結(jié)構(gòu)

class HashTable {
public int key=0; // 關(guān)鍵字
public int data=0; // 數(shù)值
public int count=0; // 探查次數(shù)
}

（2）在哈希表中查找關(guān)鍵字key

根據(jù)設(shè)定的哈希函數(shù)，計(jì)算哈希地址。如果出現(xiàn)地址沖突，則按設(shè)定的處理沖突的方法尋找下一個(gè)地址。

如此反復(fù)，直到不沖突為止（查找成功）或某個(gè)地址為空（查找失敗）。

/**
* 查找哈希表
* 構(gòu)造哈希表采用除留取余法，即f(key)=key mod p (p ≤ size)
* 解決沖突采用開(kāi)放定址法，即f2(key)=(f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關(guān)鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr=key % p; // 采用除留取余法找哈希地址
// 若發(fā)生沖突，用開(kāi)放定址法找下一個(gè)哈希地址
while (ha[addr].key !=KEY && ha[addr].key !=key) {
addr=(addr + 1) % size;
}
if (ha[addr].key==key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}

（3）刪除關(guān)鍵字為key的記錄

在采用開(kāi)放定址法處理沖突的哈希表上執(zhí)行刪除操作，只能在被刪記錄上做刪除標(biāo)記，而不能真正刪除記錄。

找到要?jiǎng)h除的記錄，將關(guān)鍵字置為刪除標(biāo)記DELKEY。

public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
int addr=0;
addr=searchHashTable(ha, p, size, key);
if (FAILED !=addr) { // 找到記錄
ha[addr].key=DELKEY; // 將該位置的關(guān)鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}

（4）插入關(guān)鍵字為key的記錄

將待插入的關(guān)鍵字key插入哈希表

先調(diào)用查找算法，若在表中找到待插入的關(guān)鍵字，則插入失敗；

若在表中找到一個(gè)開(kāi)放地址，則將待插入的結(jié)點(diǎn)插入到其中，則插入成功。

public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i=1;
int addr=0;
addr=key % p; // 通過(guò)哈希函數(shù)獲取哈希地址
if (ha[addr].key==KEY || ha[addr].key==DELKEY) { // 如果沒(méi)有沖突，直接插入
ha[addr].key=key;
ha[addr].count=1;
} else { // 如果有沖突，使用開(kāi)放定址法處理沖突
do {
addr=(addr + 1) % size; // 尋找下一個(gè)哈希地址
i++;
} while (ha[addr].key !=KEY && ha[addr].key !=DELKEY);
ha[addr].key=key;
ha[addr].count=i;
}
}

（5）建立哈希表

先將哈希表中各關(guān)鍵字清空，使其地址為開(kāi)放的，然后調(diào)用插入算法將給定的關(guān)鍵字序列依次插入。

public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i=0;
// 將哈希表中的所有關(guān)鍵字清空
for (i=0; i < ha.length; i++) {
ha[i].key=KEY;
ha[i].count=0;
}
// 將關(guān)鍵字序列依次插入哈希表中
for (i=0; i < list.length; i++) {
this.insertHashTable(ha, p, size, list[i]);
}
}

完整代碼

class HashTable {
public int key=0; // 關(guān)鍵字
public int data=0; // 數(shù)值
public int count=0; // 探查次數(shù)
}
public class HashSearch {
private final static int MAXSIZE=20;
private final static int KEY=1;
private final static int DELKEY=2;
private final static int SUCCESS=0;
private final static int FAILED=0xFFFFFFFF;
/**
* 查找哈希表
* 構(gòu)造哈希表采用除留取余法，即f(key)=key mod p (p ≤ size)
* 解決沖突采用開(kāi)放定址法，即f2(key)=(f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關(guān)鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr=key % p; // 采用除留取余法找哈希地址
// 若發(fā)生沖突，用開(kāi)放定址法找下一個(gè)哈希地址
while (ha[addr].key !=KEY && ha[addr].key !=key) {
addr=(addr + 1) % size;
}
if (ha[addr].key==key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}
/**
* 刪除哈希表中關(guān)鍵字為key的記錄
* 找到要?jiǎng)h除的記錄，將關(guān)鍵字置為刪除標(biāo)記DELKEY
*/
public int deleteHashTable(HashTable[] ha, int p, int size, int key) {
int addr=0;
addr=searchHashTable(ha, p, size, key);
if (FAILED !=addr) { // 找到記錄
ha[addr].key=DELKEY; // 將該位置的關(guān)鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}
/**
* 將待插入的關(guān)鍵字key插入哈希表
* 先調(diào)用查找算法，若在表中找到待插入的關(guān)鍵字，則插入失敗；
* 若在表中找到一個(gè)開(kāi)放地址，則將待插入的結(jié)點(diǎn)插入到其中，則插入成功。
*/
public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i=1;
int addr=0;
addr=key % p; // 通過(guò)哈希函數(shù)獲取哈希地址
if (ha[addr].key==KEY || ha[addr].key==DELKEY) { // 如果沒(méi)有沖突，直接插入
ha[addr].key=key;
ha[addr].count=1;
} else { // 如果有沖突，使用開(kāi)放定址法處理沖突
do {
addr=(addr + 1) % size; // 尋找下一個(gè)哈希地址
i++;
} while (ha[addr].key !=KEY && ha[addr].key !=DELKEY);
ha[addr].key=key;
ha[addr].count=i;
}
}
/**
* 創(chuàng)建哈希表
* 先將哈希表中各關(guān)鍵字清空，使其地址為開(kāi)放的，然后調(diào)用插入算法將給定的關(guān)鍵字序列依次插入。
*/
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i=0
// 將哈希表中的所有關(guān)鍵字清空
for (i=0; i < ha.length; i++) {
ha[i].key=KEY;
ha[i].count=0;
}
// 將關(guān)鍵字序列依次插入哈希表中
for (i=0; i < list.length; i++) {
this.insertHashTable(ha, p, size, list[i]);
}
}
/**
* 輸出哈希表
*/
public void displayHashTable(HashTable[] ha) {
int i=0;
System.out.format("pos:\t", "pos");
for (i=0; i < ha.length; i++) {
System.out.format("%4d", i);
}
System.out.println;
System.out.format("key:\t");
for (i=0; i < ha.length; i++) {
if (ha[i].key !=KEY) {
System.out.format("%4d", ha[i].key);
} else {
System.out.format(" ");
}
}
System.out.println;
System.out.format("count:\t");
for (i=0; i < ha.length; i++) {
if (0 !=ha[i].count) {
System.out.format("%4d", ha[i].count);
} else {
System.out.format(" ");
}
}
System.out.println;
}
public static void main(String[] args) {
int list={ 3, 112, 245, 27, 44, 19, 76, 29, 90 };
HashTable ha=new HashTable[MAXSIZE];
for (int i=0; i < ha.length; i++) {
ha[i]=new HashTable;
}
HashSearch search=new HashSearch;
search.createHashTable(ha, list, 19, MAXSIZE);
search.displayHashTable(ha);
}
}

參考資料

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》（B級(jí)第3版）

轉(zhuǎn)自：靜默虛空
http://www.cnblogs.com/jingmoxukong/p/4332252.html

-----這里是數(shù)學(xué)思維的聚集地------

“超級(jí)數(shù)學(xué)建模”（微信號(hào)supermodeling），每天學(xué)一點(diǎn)小知識(shí)，輕松了解各種思維，做個(gè)好玩的理性派。50萬(wàn)數(shù)學(xué)精英都在關(guān)注！

篇文章給大家?guī)?lái)的內(nèi)容是關(guān)于JavaScript中散列表(哈希表)的詳細(xì)介紹（代碼示例），有一定的參考價(jià)值，有需要的朋友可以參考一下，希望對(duì)你有所幫助。

散列表

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這加快了查找速度。這個(gè)映射函數(shù)稱(chēng)做散列函數(shù)，存放記錄的數(shù)組稱(chēng)做散列表。

我們從上圖開(kāi)始分析

有一個(gè)集合U，里面分別是1000，10，152，9733，1555，997，1168
右側(cè)是一個(gè)10個(gè)插槽的列表（散列表），我們需要把集合U中的整數(shù)存放到這個(gè)列表中
怎么存放，分別存在哪個(gè)槽里？這個(gè)問(wèn)題就是需要通過(guò)一個(gè)散列函數(shù)來(lái)解決了。我的存放方式是取10的余數(shù)，我們對(duì)應(yīng)這圖來(lái)看
1000%10=0，10%10=0 那么1000和10這兩個(gè)整數(shù)就會(huì)被存儲(chǔ)到編號(hào)為0的這個(gè)槽中
152%10=2那么就存放到2的槽中
9733%10=3 存放在編號(hào)為3的槽中

通過(guò)上面簡(jiǎn)單的例子，應(yīng)該會(huì)有一下幾點(diǎn)一個(gè)大致的理解

集合U，就是可能會(huì)出現(xiàn)在散列表中的鍵
散列函數(shù)，就是你自己設(shè)計(jì)的一種如何將集合U中的鍵值通過(guò)某種計(jì)算存放到散列表中，如例子中的取余數(shù)
散列表，存放著通過(guò)計(jì)算后的鍵

那么我們?cè)诮又匆话阄覀儠?huì)怎么去取值呢？

比如我們存儲(chǔ)一個(gè)key為1000，value為'張三' ---> {key:1000,value:'張三'}

從我們上述的解釋?zhuān)遣皇菓?yīng)該存放在1000%10的這個(gè)插槽里。

當(dāng)我們通過(guò)key想要找到value張三，是不是到key%10這個(gè)插槽里找就可以了呢？到了這里你可以停下來(lái)思考一下。

散列的一些術(shù)語(yǔ)（可以簡(jiǎn)單的看一下）

散列表中所有可能出現(xiàn)的鍵稱(chēng)作全集U
用M表示槽的數(shù)量
給定一個(gè)鍵，由散列函數(shù)計(jì)算它應(yīng)該出現(xiàn)在哪個(gè)槽中，上面例子的散列函數(shù)h=k%M,散列函數(shù)h就是鍵k到槽的一個(gè)映射。
1000和10都被存到了編號(hào)0的這個(gè)槽中，這種情況稱(chēng)之為碰撞。

看到這里不知道你是否大致理解了散列函數(shù)是什么了沒(méi)。通過(guò)例子，再通過(guò)你的思考，你可以回頭在讀一遍文章頭部關(guān)于散列表的定義。如果你能讀懂了，那么我估計(jì)你應(yīng)該是懂了。

常用的散列函數(shù)

處理整數(shù) h=>k%M （也就是我們上面所舉的例子）

處理字符串：

function h_str(str,M){

return [...str].reduce((hash,c)=>{

hash=(31*hash + c.charCodeAt(0)) % M

},0)

}

hash算法不是這里的重點(diǎn)，我也沒(méi)有很深入的去研究，這里主要還是去理解散列表是個(gè)怎樣的數(shù)據(jù)結(jié)構(gòu)，它有哪些優(yōu)點(diǎn)，它具體做了怎樣一件事。

而hash函數(shù)它只是通過(guò)某種算法把key映射到列表中。

構(gòu)建散列表

通過(guò)上面的解釋?zhuān)覀冞@里做一個(gè)簡(jiǎn)單的散列表

散列表的組成

M個(gè)槽
有個(gè)hash函數(shù)
有一個(gè)add方法去把鍵值添加到散列表中
有一個(gè)delete方法去做刪除
有一個(gè)search方法，根據(jù)key去找到對(duì)應(yīng)的值

初始化

- 初始化散列表有多少個(gè)槽

- 用一個(gè)數(shù)組來(lái)創(chuàng)建M個(gè)槽

class HashTable {

constructor(num=1000){

this.M=num;

this.slots=new Array(num);

}

散列函數(shù)

處理字符串的散列函數(shù)，這里使用字符串是因?yàn)椋瑪?shù)值也可以傳換成字符串比較通用一些

先將傳遞過(guò)來(lái)的key值轉(zhuǎn)為字符串，為了能夠嚴(yán)謹(jǐn)一些

將字符串轉(zhuǎn)換為數(shù)組, 例如'abc'=> [...'abc']=> ['a','b','c']

分別對(duì)每個(gè)字符的charCodeAt進(jìn)行計(jì)算，取M余數(shù)是為了剛好對(duì)應(yīng)插槽的數(shù)量，你總共就10個(gè)槽,你的數(shù)值%10 肯定會(huì)落到 0-9的槽里

h(str){

str=str + '';

return [...str].reduce((hash,c)=>{

hash=(331 * hash + c.charCodeAt()) % this.M;

return hash;

},0)

}

添加

調(diào)用hash函數(shù)得到對(duì)應(yīng)的存儲(chǔ)地址(就是我們之間類(lèi)比的槽)

因?yàn)橐粋€(gè)槽中可能會(huì)存多個(gè)值，所以需要用一個(gè)二維數(shù)組去表示，比如我們計(jì)算得來(lái)的槽的編號(hào)是0，也就是slot[0]，那么我們應(yīng)該往slot[0] [0]里存，后面進(jìn)來(lái)的同樣是編號(hào)為0的槽的話就接著往slot[0] [1]里存

add(key,value) {

const h=this.h(key);

// 判斷這個(gè)槽是否是一個(gè)二維數(shù)組, 不是則創(chuàng)建二維數(shù)組

if(!this.slots[h]){

this.slots[h]=[];

}

// 將值添加到對(duì)應(yīng)的槽中

this.slots[h].push(value);

}

刪除

通過(guò)hash算法,找到所在的槽

通過(guò)過(guò)濾來(lái)刪除

delete(key){

const h=this.h(key);

this.slots[h]=this.slots[h].filter(item=>item.key!==key);

}

查找

通過(guò)hash算法找到對(duì)應(yīng)的槽

用find函數(shù)去找同一個(gè)key的值

返回對(duì)應(yīng)的值

search(key){

const h=this.h(key);

const list=this.slots[h];

const data=list.find(x=> x.key===key);

return data ? data.value : null;

}

總結(jié)

講到這里，散列表的數(shù)據(jù)結(jié)構(gòu)已經(jīng)講完了，其實(shí)我們每學(xué)一種數(shù)據(jù)結(jié)構(gòu)或算法的時(shí)候，不是去照搬實(shí)現(xiàn)的代碼，我們要學(xué)到的是思想，比如說(shuō)散列表它究竟做了什么，它是一種存儲(chǔ)方式，可以快速的通過(guò)鍵去查找到對(duì)應(yīng)的值。那么我們會(huì)思考，如果我們?cè)O(shè)計(jì)的槽少了，在同一個(gè)槽里存放了大量的數(shù)據(jù)，那么這個(gè)散列表它的搜索速度肯定是會(huì)大打折扣的，這種情況又應(yīng)該用什么方式去解決，又或者是否用其他的數(shù)據(jù)結(jié)構(gòu)的代替它。

補(bǔ)充一個(gè)小知識(shí)點(diǎn)

v8引擎中的數(shù)組 arr=[1,2,3,4,5] 或 new Array(100) 我們都知道它是開(kāi)辟了一塊連續(xù)的空間去存儲(chǔ)，而arr=[] , arr[100000]=10 這樣的操作它是使用的散列，因?yàn)檫@種操作如果連續(xù)開(kāi)辟100萬(wàn)個(gè)空間去存儲(chǔ)一個(gè)值，那么顯然是在浪費(fèi)空間。

以上就是JavaScript中散列表(哈希表)的詳細(xì)介紹（代碼示例）的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注其它相關(guān)文章！

更多技巧請(qǐng)《轉(zhuǎn)發(fā) + 關(guān)注》哦！

在線咨詢

上一篇：頭條HTML內(nèi)容提取失敗背后的故事與啟示在信息爆炸的
下一篇：對(duì)比神器Beyond Compare

您的項(xiàng)目需求

*請(qǐng)認(rèn)真填寫(xiě)需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。

整合營(yíng)銷(xiāo)服務(wù)商

一文看懂一致性Hash算法

一致性Hash算法背景

一致性Hash算法詳述

算法原理

① hash環(huán)

② 服務(wù)器映射到hash環(huán)

③ 對(duì)象key映射到服務(wù)器

服務(wù)器擴(kuò)縮容場(chǎng)景

① 服務(wù)器減少

② 服務(wù)器增加

數(shù)據(jù)偏斜&服務(wù)器性能平衡問(wèn)題

引出問(wèn)題

虛擬節(jié)點(diǎn)

虛擬節(jié)點(diǎn)的計(jì)算

使用場(chǎng)景

一致性Hash算法實(shí)現(xiàn)

結(jié)構(gòu)體、錯(cuò)誤以及常量定義

① 結(jié)構(gòu)體定義

② 常量和錯(cuò)誤定義

注冊(cè)/注銷(xiāo)緩存服務(wù)器

① 注冊(cè)緩存服務(wù)器

② 注銷(xiāo)緩存服務(wù)器

查詢Key（核心）

一致性Hash算法實(shí)踐與檢驗(yàn)

算法驗(yàn)證前準(zhǔn)備

① 緩存服務(wù)器準(zhǔn)備

② 緩存代理服務(wù)器準(zhǔn)備

算法驗(yàn)證

啟動(dòng)代理服務(wù)器

啟動(dòng)緩存服務(wù)器

請(qǐng)求代理服務(wù)器獲取Key

嘗試多次獲取Key

通過(guò)Debug查看注冊(cè)和Hash環(huán)

含有負(fù)載邊界值的一致性Hash

算法描述

算法實(shí)現(xiàn)

算法測(cè)試

修改代理服務(wù)器代碼

測(cè)試

總結(jié)

您的項(xiàng)目需求