Hashlib哈希分桶

介绍

哈希加密算法应用非常广泛，包括数字签名，身份验证，操作检测，指纹，校验和（消息完整性检查），哈希表，密码存储等。

在密码学中，好的哈希算法应该满足以下两个条件：一是无法从哈希值解密原始消息；二是，更改原始消息的一个字节，哈希消息会发生非常大的变化。

哈希函数以可变长度的字节序列的作为输入，并将其转换为固定长度的序列。Hash算法特别的地方在于它是一种单向算法，用户可以通过Hash算法对目标信息生成一段特定长度的唯一的Hash值，却不能通过这个Hash值重新获得目标信息。

hash分桶操作

通常有两种常用的分桶方式：

  • 1.基于用户的分桶（User-based bucket）：这样的桶，是一个随机选定用户的集合。一种简单的方式是，使用一个hash函数，为每个user id生成一个hash值，选择一个特定的范围指向一个桶。例如：Ron Rivest设计的md5。
  • 2.基于请求的分桶（Request-based bucket）：这样的桶，是一个随机选择的请求的集合。常用的做法是，为每个请求生成一个随机数，然后将对应指定范围的请求随机数指定到某个桶内。注意，在这样的桶中，在实验期间，同一个用户不同的访问，有可能属于不同的分桶。

hashlib的md5算法作为实践级别的算法有一个很大的特点那就是输出的位数长度是固定的，这样很方面进行下一步的输出再分桶操作：

  1. import random
  2. import string
  3. import hashlib
  4. from operator import add
  5. from functools import reduce
  6. from collections import defaultdict
  9. def md5(key):
  10.     xx = hashlib.md5()  # 导入md5算法
  11.     xx.update(key.encode('utf8')
  12.     return xx.hexdigest()
  14. def mapping(hashkey, n=10):
  15.     return reduce(add, [ord(i) for i in hashkey]) % n
  17. # 进行分桶实现分流，制定不同的实验策略
  18. def mapping2(hashkey, n=10):
  19.     return hashkey[:1] % n

各个位数相加参考了 这个网站 ，但具体各个位数相加是否保证了分桶的均匀性，老实说我是不大确切的，如下做了一个简单的测试：

  1. data = defaultdict(lambda: 0)
  4. def random_string_generator():
  5.     data = []
  6.     random_length = random.randint(1, 100)
  7.     for i in range(random_length):
  8.         x = random.choice(string.ascii_lowercase + string.digits + ' ')
  9.         data.append(x)
  10.     return ''.join(data)
  13. for i in range(100000):
  14.     s = random_string_generator()
  16.     c = mapping(md5(s))
  17.     print(f'"{s}" mapping to bukket {c}')
  19.     data[c] += 1
  21. print(data)

初步看来随机生成的各种各样的字符串最终分桶基本上是均匀的。虽然我知道md5算法是能够保证每个位数上的随机，但进行ord处理得到数字，相加再取模，是否也是保证均匀性的，我只能说这是猜的，需要严格的数学证明。

参考

https://a358003542.github.io/articles/hashfen-tong-cao-zuo.html