TVP

# 一致性哈希算法那点事

fromhashlibimportmd5

fromstructimportunpack_from

frombisectimportbisect_left

ITEMS =10000000

NODES =100

NEW_NODES =101

def_hash(value):

k = md5(str(value)).digest()

ha = unpack_from(">I",k)[]

returnha

ring = []

new_ring = []

forninrange(NODES):

ring.append(_hash(n))

ring.sort()

forninrange(NEW_NODES):

new_ring.append(_hash(n))

new_ring.sort()

change =

foriteminrange(ITEMS):

h = _hash(item)

n = bisect_left(ring,h) % NODES

new_n = bisect_left(new_ring,h) % NEW_NODES

ifnew_n != n:

change +=1

print("Change: %d(%0.2f%%)"% (change,change *100.0/ ITEMS))

Change: 235603(2.36%)

fromhashlibimportmd5

fromstructimportunpack_from

frombisectimportbisect_left

ITEMS =10000000

NODES =100

node_stat = [foriinrange(NODES)]

def_hash(value):

k = md5(str(value)).digest()

ha = unpack_from(">I",k)[]

returnha

ring = []

hash2node = {}

forninrange(NODES):

h = _hash(n)

ring.append(h)

ring.sort()

hash2node[h] = n

foriteminrange(ITEMS):

h = _hash(item)

n = bisect_left(ring,h) % NODES

node_stat[hash2node[ring[n]]] +=1

_ave = ITEMS / NODES

_max =max(node_stat)

_min =min(node_stat)

print("Ave: %d"% _ave)

print("Max: %d(%0.2f%%)"% (_max,(_max - _ave) *100.0/ _ave))

print("Min: %d(%0.2f%%)"% (_min,(_ave - _min) *100.0/ _ave))

Ave: 100000

Max: 596413(496.41%)

Min: 103(99.90%)

fromhashlibimportmd5

fromstructimportunpack_from

frombisectimportbisect_left

ITEMS =10000000

NODES =100

VNODES =1000

node_stat = [foriinrange(NODES)]

def_hash(value):

k = md5(str(value)).digest()

ha = unpack_from(">I",k)[]

returnha

ring = []

hash2node = {}

forninrange(NODES):

forvinrange(VNODES):

h = _hash(str(n) +str(v))

ring.append(h)

hash2node[h] = n

ring.sort()

foriteminrange(ITEMS):

h = _hash(str(item))

n = bisect_left(ring,h) % (NODES*VNODES)

node_stat[hash2node[ring[n]]] +=1

_ave = ITEMS / NODES

_max =max(node_stat)

_min =min(node_stat)

print("Ave: %d"% _ave)

print("Max: %d(%0.2f%%)"% (_max,(_max - _ave) *100.0/ _ave))

print("Min: %d(%0.2f%%)"% (_min,(_ave - _min) *100.0/ _ave))

Ave: 100000

Max: 116902(16.90%)

Min: 9492(90.51%)

fromhashlibimportmd5

fromstructimportunpack_from

frombisectimportbisect_left

ITEMS =10000000

NODES =100

NODES2 =101

VNODES =1000

def_hash(value):

k = md5(str(value)).digest()

ha = unpack_from(">I",k)[]

returnha

ring = []

hash2node = {}

ring2 = []

hash2node2 = {}

forninrange(NODES):

forvinrange(VNODES):

h = _hash(str(n) +str(v))

ring.append(h)

hash2node[h] = n

ring.sort()

forninrange(NODES2):

forvinrange(VNODES):

h = _hash(str(n) +str(v))

ring2.append(h)

hash2node2[h] = n

ring2.sort()

change =

foriteminrange(ITEMS):

h = _hash(str(item))

n = bisect_left(ring,h) % (NODES*VNODES)

n2 = bisect_left(ring2,h) % (NODES2*VNODES)

ifhash2node[ring[n]] != hash2node2[ring2[n2]]:

change +=1

print("Change: %d(%0.2f%%)"% (change,change *100.0/ ITEMS))

Change: 104871(1.05%)

• 发表于:
• 原文链接https://kuaibao.qq.com/s/20180526B19VPS00?refer=cp_1026
• 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
• 如有侵权，请联系 cloudcommunity@tencent.com 删除。

2018-06-05

2018-03-24

2018-07-05

2018-06-19

2018-10-28

2018-12-07

2019-02-21

2018-10-25

2018-09-01

2018-11-10

2021-10-16

2018-10-27

2018-01-27

2018-12-25

2018-06-14

2018-01-26

2019-12-26

2019-10-21

2019-12-26

2019-10-25