哈希表

理想

哈希表，又叫散列表。它是计算机科学里空间复杂度和时间复杂度的折中取舍。

如果所有的键都是小整数，我们可以用一个数组来实现无序的符号表。将键（key）作为数组的索引，而数组中键i处储存它对应的值（value）。

概览

整体过程
- 任意类型的键 -> 正整数 -> 数组索引 (hashCode + 取余) -> 解决碰撞
散列函数：将键转化为数组的一个索引
- 优秀的三列方法需要满足三个条件
  - 一致性：等价的键必然产生相等的散列值
  - 高效性：计算简便
  - 均匀性：均匀地散列所有的键
处理碰撞冲突
- 拉链法：每个数组存储指向一个单向链表的指针。英文 separate chaining。
- 开放地址法
  - 英文 open addressing
  - 实现
    - 使用大小为M的数组保存N个键值对，其中M>N
    - 使用两个长度为M的数组分别保存所有键和所有值
    - 探测时有以下三种情况
      - 未命中，键为空：放置
      - 命中，键相同：更新
      - 键和被查找的键不同：产生碰撞，继续探测
        
        线性探测法：数组索引加1，继续判断
        
        平方探测：数组索引加 j 的平方，继续判断，j为探测次数
  - 均摊分析：在动态调整数组大小时，需要找出均摊成本的上限。
    - 每次数组长度加倍之后，累计平均值都会增加约1，因为表中的每个键都需要重新计算散列值。
    - 然后随着新键的加入，平均成本慢慢降低。
      - 随着表中的键的增加，每次调整后，均摊成本的下降速度慢慢降低。
  - 聚集
    - Cluster，也翻译做“堆积”
    - 意思是在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。
    - 对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。
      - 单独链表法，即上面的拉链法
      - 再散列：再次其它散列函数产生新的数组索引。不易产生聚集，但增加了计算时间。
概率论：概率论是数学分析的重大成果。
- 利用概率论的经典结论来帮助我们选择适当的参数，来在时间和空间的权衡上作出选择。
- 指标
  - 散列表的使用率 N/M
  - 当使用率在 1/8 ~ 1/2 时，探测次数的期望在 1.5 到 2.5 之间。

一致性哈希

哈希表中的每一个代表分布式系统中一个节点，在系统添加或删除节点只需要移动 K/n 项。其中 K 是关键字的数量，n 是槽位数量。

该算法主要解决的问题是：当slot数发生变化时，能够尽量少的移动数据。一致性哈希可应用于负载均衡、分布式缓存(缓存分片)等场景中。

一致性哈希算法的理解与实践

普通哈希算法
- 比较好地实现了均匀分布，依赖的是哈希函数的均匀性
- 增加节点的时候，数据移动率非常大
一致性哈希
- 解决了节点变化导致的数据迁移问题
- 分配的很不均匀
  - 引入虚节点
- 将虚节点数量扩大到一个很大的值，比如说 2^32
  - 首先求出节点的哈希值，并将其配置到0～2^32的圆（continuum）上。
  - 然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
  - 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个节点上。如果超过2^32仍然找不到服务器，就会保存到第一个节点上。
参考
- https://juejin.im/post/5ae1476ef265da0b8d419ef2

普通哈希

from hashlib import md5
from struct import unpack_from

ITEMS = 1000000
NODES = 100

node_stat = [0 for i in range(NODES)]

for item in range(ITEMS):
    k = md5(str(item).encode()).digest()
    h = unpack_from(">I", k)[0]
    n = h % NODES
    node_stat[n] += 1

_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)

print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))

一致性哈希

from hashlib import md5
from struct import unpack_from
from bisect import bisect_left

ITEMS = 1000000
NODES = 100
node_stat = [0 for i in range(NODES)]


def _hash(value):
    k = md5(str(value).encode()).digest()
    ha = unpack_from(">I", k)[0]
    return ha

ring = []
hash2node = {}

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 = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)

print("Ave: %d" % _ave)
print("Max: %d\t(%0.2f%%)" % (_max, (_max - _ave) * 100.0 / _ave))
print("Min: %d\t(%0.2f%%)" % (_min, (_ave - _min) * 100.0 / _ave))

微博的计数服务设计演进

微博计数器的设计(下) · Cydu’s Blog
keys 数量
- 1000亿 = 100GB
- 要存储的数据量真实大小 32位 x *100GB = 400 GB，利用率 5.3%
- 每秒100W次的查询
大小变化
- 一个key(即微博id) 最长64位数字(Eg: 5612814510546515491)
- 76B x 1000亿 = 7.6 TB
- 不存储0值数据，减少3/5到400亿个
- 自定义结构并且使用 int，一个int使用4字节：16B x 400亿 = 640 GB
- 使用 unsigned short 类型：12B x 400亿 = 480 GB
- 最后方案
  - 把两个value放到两个数组里，使用类似utf8的变长编码来压缩
  - 把固定个数的value放到一个 mini block 里，再直接用 LZF 压缩空间
  - 分开存储的好处是可以随时加列
  - 对8字节的微博ID的16进制形式，每个字节的前4比特的信息放到预定义的内存位置，只存后4比特组成的字符序列，只用 int 类型即可
  - 8B x 400亿 = 320 GB
冷热数据
- 排序、分块、索引、dump到磁盘
- unsored dump + WAL (write ahead log)
分布式化
- 使用主从节点分离读写
- 主节点的单点问题：从节点接替
通用服务：向"weibo"这个计数器中增加一列，列名是 weibo_id, 最长为64位，一般也是64位，默认值为0
对于工程类的问题，其实永远不会有标准的答案，一千个架构师能给出一万个设计方案来，而且没有一个是标准的答案，只有最适合你的那一个！

哈希表

发布于 2017-12-18 12:05:37

理想

概览

一致性哈希

微博的计数服务设计演进