使用mod对id进行分区的好散列函数

Question

我有一批id，我想用良好的线性扩展函数对它们进行分区
ID不包含时间戳，并且传播非常严重。我只限于一些愚蠢的xpath运算符。

你能提出更好的功能来在10个桶之间分配id吗？

public static void main(String[] args) {
int[] buckets = new int[10];
for (int i = 0; i < 10; i++)
buckets[i] = 0;
for (int i = 0; i < 1000; i++) {
String id = format("130770%s0020", i);
long l = parseLong(id);
int partition = (int) f(l);
buckets[partition] = buckets[partition] + 1;
}
for (int i = 0; i < 10; i++)
out.println(buckets[i]);
}

目前我的最佳成绩是

private static long f(long l) {
return l % 31 % 10;
}

它给出

130 96 97 96 97 97 97 96 98 97 96

你能提出更好的实施方案吗？

---

这就是我正在编辑的代码看起来像的样子

<rule id="trade_to_backet_4">
<forall var="trade_identifier" in="/eMxML/msml/trade/systemReference[1]/@reference">
<equal op1="translate($trade_identifier, translate($trade_identifier,'0123456789',''), '') mod 813 mod 10" op2="4"/>
</forall>
</rule>

Answer 1

我建议选择已应用于HashMap类的相同解决方案。

/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower.  Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.)  So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对于您的代码，这意味着：

return (l ^ (l >>> 16)) % 10;

对于您的测试数据，这会产生以下的扩散：

109 102 103 94 91 95 93 100 104 109

---

来自评论：

我没有移位

表达式l >>> 16也可以写成l / 65536，但除法比移位慢得多，所以这就是为什么通常使用l >>> 16的原因。

---

更新来自另一条评论：

我没有XOR运算符

使用+而不是^。虽然没有那么好，但在这里似乎已经足够好了：

return (l + (l / 65536)) % 10;

结果排列：

101 92 92 99 105 104 105 99 97 106

Answer 2

如果你的目标是让东西在桶中平均分配，这似乎是可行的：

return ((l / 10000) % 1000) % 10;

(这只是从数字中提取i(

Ideone演示。

输出：

100 100 100 100 100 100 100 100 100 100 

一个似乎给出相同结果的替代方案：

// NB: abs(int) isn't always non-negative. Should really handle Integer.MIN_VALUE.
return Math.abs(Long.toString(l).hashCode()) % 10;

Ideone演示

输出：

100 100 100 100 100 100 100 100 100 100 

Answer 3

您是否正在寻找一个与特定批次的id、任何批次的id或具有某些特定特征的批次(如所有形式为130770%s020(配合良好的解决方案？

我认为，在一些最坏的情况下，仅使用整数运算的解决方案总是会表现不佳，例如，所有ID都是31的倍数。您确实需要进行一些位处理，这在XPath1.0中无法有效实现。

话虽如此，我想我尝试如下：选择3个素数p、Q和R，并返回(N mod P + N mod Q + N mod R) mod 10。

同样值得记住的是，一个完美的算法不会在每个桶中提供相同数量的物品；相反，结果最多只能反映一个随机分布，也就是说，它将是二项式的。你需要对大量的输入进行一些相当聪明的测试，看看你是否做到了。

在这个阶段，我倾向于退一步问：你到底在做什么，需要这个散列函数？有没有其他方法可以解决不需要这个散列函数的问题？你能告诉我们你想解决的真正问题吗？

Answer 4

813是一个非常出色的数字

101 101 100 100 99 99 99 100
101 101 100 100 100 99 99.br>101 100 100 100 100 100100
101 01 101 100 10010099 99 100
101 101 100 100100 10099 99
1101 101 101 10010010010099 99
102 101 101 100100 1009999 99
101 101 100100999999
101 101 100 100 100 99 99
101 101 100 100 00 99 99
101 101 101 100 10 100 99 99
101 01 100 100 100 9999 99
101 101 101 100 10099 99 99
101 01 101 100 1009999 9999
101 101 100 100 100 99 99
101 101 100 100 00 99 99
101 101 101 100 10 100 99 99
101 01 100 100 100 9999 99
101 101 101 100 10099 99 99
101 01 101 100 1009999 9999
101 101 100 100 100 99 99
101 101 100 100 00 99 99
101 101 101 100 10 100 99 99
101 01 100 100 100 9999 99
101 101 101 100 10099 99 99
101 01 101 100 1009999 9999

private static final int GROUP_SIZE = 1000;
private static final int BUCKET_SIZE = 10;
private static final double MAX_DEVIATION = BUCKET_SIZE * 1.0;
private static final int NUMBER_TO_TEST = 813;
public static void main(String[] args) {
List<Long> list = LongStream.range(1, 1000).boxed().parallel()
.filter(l -> filter("005001307700020%s", l))
.filter(l -> filter("0050013077%s00020", l))
.filter(l -> filter("00500%s1307700020", l))
.filter(l -> filter("%s005001307700020", l))
.filter(l -> filter("111111111111111%s", l))
.filter(l -> filter("1111111111%s11111", l))
.filter(l -> filter("11111%s1111111111", l))
.filter(l -> filter("%s111111111111111", l))
.filter(l -> filter("222222222222222%s", l))
.filter(l -> filter("2222222222%s22222", l))
.filter(l -> filter("22222%s2222222222", l))
.filter(l -> filter("%s222222222222222", l))
.filter(l -> filter("333333333333333%s", l))
.filter(l -> filter("3333333333%s33333", l))
.filter(l -> filter("33333%s3333333333", l))
.filter(l -> filter("%s333333333333333", l))
.filter(l -> filter("444444444444444%s", l))
.filter(l -> filter("4444444444%s44444", l))
.filter(l -> filter("44444%s4444444444", l))
.filter(l -> filter("%s444444444444444", l))
.filter(l -> filter("555555555555555%s", l))
.filter(l -> filter("5555555555%s55555", l))
.filter(l -> filter("55555%s5555555555", l))
.filter(l -> filter("%s555555555555555", l))
.filter(l -> filter("666666666666666%s", l))
.filter(l -> filter("6666666666%s66666", l))
.filter(l -> filter("66666%s6666666666", l))
.filter(l -> filter("%s666666666666666", l))
.filter(l -> filter("777777777777777%s", l))
.filter(l -> filter("7777777777%s77777", l))
.filter(l -> filter("77777%s7777777777", l))
.filter(l -> filter("%s777777777777777", l))
.filter(l -> filter("888888888888888%s", l))
.filter(l -> filter("8888888888%s88888", l))
.filter(l -> filter("88888%s8888888888", l))
.filter(l -> filter("%s888888888888888", l))
.filter(l -> filter("999999999999999%s", l))
.filter(l -> filter("9999999999%s99999", l))
.filter(l -> filter("99999%s9999999999", l))
.filter(l -> filter("%s999999999999999", l))
.collect(toList());
System.err.println(list);
}
public static boolean filter(String format, long number) {
int[] buckets = new int[BUCKET_SIZE];
for (int i = 0; i < BUCKET_SIZE; i++)
buckets[i] = 0;
for (int i = 0; i < GROUP_SIZE; i++) {
String id = format(format, i);
long l = parseLong(id);
int partition = (int) (l % number % BUCKET_SIZE);
buckets[partition] = buckets[partition] + 1;
}
int sum = 0;
for (int i = 0; i < BUCKET_SIZE; i++)
sum += buckets[i];
int deviation = 0;
for (int i = 0; i < BUCKET_SIZE; i++)
deviation += abs(buckets[i] - sum / BUCKET_SIZE);
if (number == NUMBER_TO_TEST) {
for (int i = 0; i < BUCKET_SIZE; i++)
System.out.println(buckets[i]);
System.out.println("----------------------");
}
return deviation < MAX_DEVIATION;
}