雜湊函式與分流演算法
摘要：
雜湊函式
雜湊函式（hash function）對一種對任意輸入，都返回一個固定長度輸出的函式。常被用來檢測資訊的完整性，常用的函式有MD5,SHA1等。下載軟體時，有的網站會提供一個md5值，下載完成後可以計算軟體的md5值，對比是否與網站上的一致。如果不一致，可能是沒下完整，也可以是被...
雜湊函式
雜湊函式（hash function）對一種對任意輸入，都返回一個固定長度輸出的函式。常被用來檢測資訊的完整性，常用的函式有MD5,SHA1等。下載軟體時，有的網站會提供一個md5值，下載完成後可以計算軟體的md5值，對比是否與網站上的一致。如果不一致，可能是沒下完整，也可以是被黑客”改造後”的軟體，儘量不要安裝。
雜湊函式應該有以下特點:
-
同樣的輸入，保證會有同樣的輸出。
-
很難找到其他的輸入，使得它的輸出與指定的輸出相等。保證如果輸入的資訊被篡改，那輸出的雜湊值變化的概率幾乎為1。
第二個特點被稱做“弱抗碰撞性”。碰撞 就是說兩條不同的資訊，雜湊值相等。理論上碰撞當然是不可避免的，比如MD5函式固定地返回32位字母和數字的組合。 這個組合有(26 + 10)^32種，但輸入的資訊是無窮多個可能。所以雜湊函式無法保證不碰撞，只能儘量讓輸出保持隨機性，降低碰撞的概率。
分流演算法
分流演算法是公司做AB測試系統時，將不同的使用者分配到不同實驗時使用的演算法。分流演算法需要做到的效果是：
-
隨機性，保證每個實驗的使用者群體結構類似
-
指定時間內，同一個使用者被分配到的實驗id不會變
這兩個特點剛好是雜湊函式的特長。只要把時間因素加入雜湊函式，就可以保證在指定時間內，輸出的不變性，同時隨機性也完全有保證。
實戰
import time
import random
from hashlib import md5
SALT = 'add some random salt in hash function'
EXPID_CONF = {'A': 30, 'B': 20, 'C': 50}
def split_stream(uid, expid_conf=None, unchange_time=7 * 24 * 3600):
"""
@param uid: 使用者id
@param expid_conf: 實驗ID和流量配置，預設使用 EXPID_CONF 的配置
@param unchange_time: 多長時間內保持分流結果不變，預設7天
"""
expid_conf = expid_conf or EXPID_CONF
for val in expid_conf.values():
assert val >= 0
# 計算隨機的hash值
time_factor = int(time.time() / unchange_time)
msg = '{uid}+{salt}+{t}'.format(uid=uid, salt=SALT, t=time_factor)
hash_bytes = md5(msg.encode()).digest()
# hash值轉為數字, 對總流量取模, 保證0 <= rand_int <= stream_sum
stream_sum = sum(expid_conf.values())
rand_int = int.from_bytes(hash_bytes, byteorder='big') % stream_sum
# 計算分流結果，判斷rand_int的取值落在哪個實驗區間即可
stream_seq = sorted(expid_conf.items(), key=operator.itemgetter(1))
for expid, stream_count in stream_seq:
if rand_int < stream_count:
return expid
rand_int -= stream_count
if __name__ == '__main__':
# 隨便測試
from collections import Counter
res = []
for i in range(0, 10000):
uid = random.randint(0, 100000)
res.append(split_stream(uid))
print(Counter(res))