# 强哈希

## 核心计算如下

for item in range(ITEMS):
k = md5(str(item)).digest()
h = unpack_from(">I", k)[0]
# 通过取余的方式进行映射
n = h % NODES
node_stat[n] += 1


Ave: 100000
Max: 100695 (0.69%)
Min: 99073 (0.93%)


## 缺点

for item in range(ITEMS):
k = md5(str(item)).digest()
h = unpack_from(">I", k)[0]
# 原映射结果
n = h % NODES
# 现映射结果
n_new = h % NEW_NODES
if n_new != n:
change += 1


Change: 9900989 (99.01%)


• 好处

• 缺点

# 代码实现

## 实现代码

consitent-hashing

## 核心代码

for n in range(NODES):
h = _hash(n)
ring.append(h)
ring.sort()
hash2node[h] = n
for item in range(ITEMS):
h = _hash(item)
n = bisect_left(ring, h) % NODES
node_stat[hash2node[ring[n]]] += 1



## 均匀性

Ave: 100000
Max: 596413 (496.41%)
Min: 103 (99.90%)


# 改进-虚节点

## 实现代码

for n in range(NODES):
for v in range(VNODES):
h = _hash(str(n) + str(v))
# 构造ring
ring.append(h)
# 记录hash所对应节点
hash2node[h] = n
ring.sort()
for item in range(ITEMS):
h = _hash(str(item))
# 搜索ring上最近的hash
n = bisect_left(ring, h) % (NODES*VNODES)
node_stat[hash2node[ring[n]]] += 1


## 增加节点

for item in range(ITEMS):
h = _hash(str(item))
n = bisect_left(ring, h) % (NODES*VNODES)
n2 = bisect_left(ring2, h) % (NODES2*VNODES)
if hash2node[ring[n]] != hash2node2[ring2[n2]]:
change += 1


# 另一种改进

## 核心代码

for part in range(2 ** LOG_NODE):
ring.append(part)
part2node[part] = part % NODES
for item in range(ITEMS):
h = _hash(item) >> PARTITION
part = bisect_left(ring, h)
n = part % NODES
node_stat[n] += 1


## 增加节点

for part in range(2 ** LOG_NODE):
ring.append(part)
part2node[part] = part % NODES
part2node2[part] = part % NODES2
change = 0
for item in range(ITEMS):
h = _hash(item) >> PARTITION
p = bisect_left(ring, h)
p2 = bisect_left(ring, h)
n = part2node[p] % NODES
n2 = part2node2[p] % NODES2
if n2 != n:
change += 1


# 参考资料

https://blog.csdn.net/lihao21/article/details/54193868

https://yikun.github.io/2016/06/09/%E4%B8%80%E8%87%B4%E6%80%A7%E5%93%88%E5%B8%8C%E7%AE%97%E6%B3%95%E7%9A%84%E7%90%86%E8%A7%A3%E4%B8%8E%E5%AE%9E%E8%B7%B5/

http://afghl.github.io/2016/07/04/consistent-hashing.html

https://zh.wikipedia.org/wiki/%E4%B8%80%E8%87%B4%E5%93%88%E5%B8%8C

https://blog.csdn.net/sunxinhere/article/details/7981093

http://blog.huanghao.me/?p=14

• 代码实现

Consistent-hashing C 语言实现

• chord

http://101.96.10.64/db.cs.duke.edu/courses/cps212/spring15/15-744/S07/papers/chord.pdf

https://github.com/ChuanXia/Chord

https://en.wikipedia.org/wiki/Chord_(peer-to-peer)

http://www.yeolar.com/note/2010/04/06/p2p-chord/

https://github.com/ChuanXia/Chord

https://github.com/netharis/Chord-Implementation/blob/master/Chord/Chord.java

https://github.com/TitasNandi/Chord-JAVA