求个尽量均匀的分区算法

[Rocketer]

由于数据量庞大，打算分区存储，希望有个高效且尽量均匀的分区算法。

比如有 1 亿条数据，100 个区，那最好每个区都能分到 100 万条左右的数据，越接近越好。

数据的主键是长度为 12 的字符串，我试过把每个字符的 ASCII 码加起来再取模，结果发现均匀度很差，热区能比冷区多 50 倍。

求各位大神推荐个算法，不胜感谢

[linvon]

找一个固定 key，把 key+字符串做 MD5 或者 hash，然后取固定位数模，基本差不多了

[bugmakerxs]

@Rocketer md5 速度贼快，不然不会运用这么广泛

[securityCoding]

核心在于哈希均衡
1.hashMap 的 hash 算法: 先让高低位异或 & n-1
2.哈希算法 md5 再取模
3.一致性哈希,专门解决这个问题...

[macttt]

哈希环分片的区尽量多，把这些区视为逻辑分区，多个逻辑分区对应一个物理分区。

[learningman]

MD5 不是可以硬件加速吗，问题不大吧

[wowboy]

建议 hash 环分片，openstack 项目就是这么做得。

[hejw19970413]

其实没有办法做到完全的平均。我记得 google sre 那本书上好像有这样的例子

[telnetning]

@wowboy 嗯？求教，OpenStack 在哪里用的这个环分片啊，我想看看代码学习下

[scemsjyd]

一致性哈希+murmur

[xuanbg]

自增取模即可

[AItsuki]

B 树不适用吗……

[kaflash]

unsigned int seed = 131;
unsigned int hash = 0;

while (*str)
{
hash = hash * seed + (*str++);
}

return (hash & 0x7FFFFFFF);

[Rocketer]

@FakNoCNName 后 9 位不是严格递增的，还有一些规则在里面，所以分布并不均匀。

这个 hash 要求速度极快，所以还是要在基本算法上做文章。最后采取了反向活跃加权再取模的办法，目前测试效果还不错。

思路说起来也很简单，对字符串中的每一位，越常变化的权重越低，比如最活跃的权重是 C，第二活跃的权重是 C*C……各字符加权求和后再%100，就行了。权重常数 C 从 2 到 100 用真实数据测一遍，就能找到最适合的了。现在各区都在正负 10%内，很满意了。