假设我有很多字符串(比如100亿字符串,每行约50个字符).我想将字符串分配到10个桶中.每个桶应该容纳大约10%的琴弦.使用哈希函数h(),我可以这样做:
int bucket_for_s = h(s) % 10
然而,这并不能保证分布的均匀性.假设我对所有字符串执行上述操作,并发现30%转到存储桶1,5%转到存储桶2,依此类推.我的问题是:
给定h()分布,有没有办法生成一个新的哈希函数h2(),它将更均匀地分配字符串？
或者,是否有一个进程可以生成一系列哈希函数h2(),h3()...这样1:每个哈希函数都优于前一个和2:我只需要生成一个合理数量的哈希功能？
我还应该提一下,不幸的是我不能简单地将输入分成10个部分,因为我的输入分布在几台机器上.我正在寻找一种确定性的解决方案,我可以单独应用于每台机器并获得相同的结果(因此最终"hello"将转到bucket x,无论它存储在哪台机器上).
我正在考虑实现一个无锁的圆形数组.一个问题是以无锁的方式保持头部和尾部指针.我想到的代码是:
int circularIncrementAndGet(AtomicInteger i) {
i.compareAndSet(array.length - 1, -1);
return i.incrementAndGet();
}
然后我会做类似的事情:
void add(double value) {
int idx = circularIncrementAndGet(tail);
array[idx] = value;
}
(注意,如果数组是完整的旧值将被覆盖,我很好).
有没有人发现这个设计有问题？我怀疑可能存在我没有看到的竞争状况.