5.3　散列算法

我们都知道，随机分流的随机性是通过散列算法来实现的。如何选择散列算法呢？不同的散列算法是否会对分流结果有影响呢？一般在工程实践中，对散列算法的评估主要考虑3个方面——计算性能、均匀性、相关性。

计算性能主要是指开始分流时散列算法的速度，如果速度不够快，可能会影响线上的响应速度。

均匀性是指在同层之中分为不同实验组的时候，每个组分到的参与用户的数量尽量一致。我们可以用组间差异（Hash_diff）来表示不同实验组之间参与用户数量的差异。Hash_diff越小，均匀性越好。

相关性是指在不同层的组之间的混合尽量均匀，可以用层间差异（Layer_diff）来表示，Layer_diff越小，相关性越低。

比如有1000万个用户，分为20层，每层100组。

均匀性是在理想的情况下，每个层每个组都有100000个用户，这样同层不同组的实验组数量的标准差为0，Hash_diff=0。

相关性是在理想的情况下，每个层每个组和其他层某个组的交集的数量都是1000，这样不同层间不同组实验参与数量交集的标准差为0，Layer_diff=0。

常见的散列算法有MD、SHA、JDB、Murmur等。其中最为常用的是MD和Murmur，Murmur的运算性能更好，抗碰撞性更强，表现出的均匀性、相关性也是最好的，在工程实践中也是运用最多的。

虽然散列算法能从理论上保证分流的均匀性，但是在实际情况中，由于各种复杂的原因，用户的分布可能不是完全均匀的，就有可能导致随机分流的实验组之间出现不均匀的情况。分流不均的一个重要观察指标就是，两组策略完全一致的用户的实验指标数据出现显著的不一致。

这里需要特别强调的是显著的不一致。如果只观察数据绝对值，两组均值通常是不相等的，这是因为存在天然的波动，而且用户量级越小，波动越大，如果是在满足了一定用户量的情况下出现了显著差异，这时大概率是出现了分流不均的情况。分流不均的原因很多，可能是系统出错，也可能是随机过程用户不同质，例如有一小部分特别活跃的用户，因为占比低，所以容易出现各个组之间的不均匀分配，或者受到遗留实验的影响等。为了防止这个问题的出现，一般在实验开始前需要进行检验（如SRM校验、AA实验），以确保实验的基础没有偏差。