8

我有一个整数类型，比如说long，它的值在Long.MIN_VALUE = 0x80...0(-2^63) 和Long.MAX_VALUE = 0x7f...f(2^63 - 1) 之间。Long.MAX_VALUE我想以干净有效的方式将它与〜50％的冲突散列到相同类型的正整数（即在 1 和 之间）。

我的第一次尝试是这样的：

  • Math.abs(x) + 1
  • (x & Long.MAX_VALUE) + 1

但是那些和类似的方法总是在某些值上存在问题，即 when xis 0// Long.MIN_VALUE。Long.MAX_VALUE当然，天真的解决方案是使用 2 个 if 语句，但我正在寻找更清洁/更短/更快的东西。有任何想法吗？

注意：假设我在 Java 中工作，其中没有定义到布尔和移位语义的隐式转换。

4

9 回答 9

10

最简单的方法是将符号位归零，然后将零映射到其他值：

Long y = x & Long.MAX_VALUE;
return (y == 0)? 42: y;

这很简单，只使用一个 if/ternary 运算符，平均碰撞率约为 50%。有一个缺点：它将 4 个不同的值（0、42、MIN_VALUE、MIN_VALUE+42）映射到一个值（42）。所以对于这个值，我们有 75% 的碰撞，而对于其他值 - 正好是 50%。

更均匀地分布冲突可能更可取：

return (x == 0)? 42: (x == Long.MIN_VALUE) ? 142: x & Long.MAX_VALUE;

此代码为 2 个值提供 67% 的冲突，为其他值提供 50% 的冲突。您不能更均匀地分布碰撞，但可以选择这 2 个最碰撞的值。缺点是这段代码使用了两个 if/三元运算符。

仅使用一个 if/三元运算符时，可以避免 75% 的单个值冲突：

Long y = x & Long.MAX_VALUE;
return (y == 0)? 42 - (x >> 7): y;

此代码为 2 个值提供 67% 的冲突，为其他值提供 50% 的冲突。选择这些最冲突的值的自由度较低：0 映射到 42（您几乎可以选择任何值）；MIN_VALUE 映射到42 - (MIN_VALUE >> 7)（您可以将 MIN_VALUE 移动 1 到 63 之间的任何值，只需确保A - (MIN_VALUE >> B)不会溢出）。

没有条件运算符（但代码更复杂）也可以获得相同的结果（2 个值的冲突为 67%，其他值的冲突为 50%）：

Long y = x - 1 - ((x >> 63) << 1);
Long z = y + 1 + (y >> 63);
return z & Long.MAX_VALUE;

这为值“1”和“MAX_VALUE”提供了 67% 的冲突。如果更方便地获取其他一些值的大多数冲突，只需将此算法应用于x + A，其中 'A' 是任意数字。

此解决方案的改进变体：

Long y = x + 1 + ((x >> 63) << 1);
Long z = y - (y >> 63);
return z & Long.MAX_VALUE;
于 2012-07-22T11:57:51.403 回答
3

假设您想将所有值折叠到正空间中，为什么不将符号位归零呢？

您可以利用 MAX_VALUE 只是一个零符号位，后跟一个，例如

int positive = value & Integer.MAX_VALUE;

或长期：

long positive = value & Long.MAX_VALUE;

如果您想要具有伪随机质量的“更好”散列，您可能希望首先通过另一个散列函数 pss 值。我最喜欢的快速哈希是 George Marsaglia 的XORshift系列。它们具有很好的特性，它们将整个 int / long 数字空间完美地映射到自身，因此在将符号位归零后，您仍然会得到 50% 的冲突。

这是 Java 中的一个快速 XORshift 实现：

public static final long xorShift64(long a) {
    a ^= (a << 21);
    a ^= (a >>> 35);
    a ^= (a << 4);
    return a;
}

public static final int xorShift32(int a) {
    a ^= (a << 13);
    a ^= (a >>> 17);
    a ^= (a << 5);
    return a;
}
于 2012-07-19T04:38:44.850 回答
1

您可以在没有任何条件的情况下使用无符号移位运算符在单个表达式中执行此操作：

public static int makePositive(int x) {
  return (x >>> 1) + (~x >>> 31);
}
于 2012-07-25T04:14:00.957 回答
1

我会选择最简单但不完全浪费时间的版本：

public static long postiveHash(final long hash) {
    final long result = hash & Long.MAX_VALUE;
    return (result != 0) ? result : (hash == 0 ? 1 : 2);
}

此实现为除两个可能的输入之外的所有输入支付一个条件操作：0 和 MIN_VALUE。在第二个条件下，这两个被分配了不同的值映射。我怀疑你能更好地结合（代码）简单性和（计算）复杂性。

当然，如果你能忍受更差的分布，它会变得简单得多。通过将空间限制为 1/4 而不是 1/2 -1，您可以获得：

public static long badDistribution(final long hash) {
    return (hash & -4) + 1;
}
于 2012-07-23T15:59:24.650 回答
1

从信息论的角度来看，您可以将2^64值映射为2^63-1值。

因此，映射对于模运算符来说是微不足道的，因为它总是有一个非负的结果：

y = 1 + x % 0x7fffffffffffffff;  // the constant is 2^63-1

这可能非常昂贵，那么还有什么可能呢？

简单的数学2^64 = 2 * (2^63 - 1) + 2表示我们将有两个源值映射到一个目标值，但在两种特殊情况下，三个将变为一个。将它们视为两个特殊的 64 位值，将它们称为x1和x2，每个都与其他两个源值共享一个目标。在上面的mod表达式中，这是通过“包装”发生的。目标值y=2^31-2和y=2^31-3具有三个映射。所有其他人都有两个。由于我们必须使用比任何方法更复杂的东西mod，让我们寻找一种方法以低成本将特殊值映射到我们喜欢的任何地方

为了说明，让我们将 [-8..7] 中的 4 位有符号整数映射x到 [1..7]y中，而不是 64 位空间。

一个简单的方法是将[1..7] 中x的值映射到它们自己，然后问题x简化为 [-8..0] 到 [1..7] 中的映射y。请注意，这里有 9 个源值，只有 7 个目标，如上所述。

显然有很多策略。在这一点上，您可能会看到一个 gazzilion。我将只描述一个特别简单的。

让除特殊情况和y = 1 - x之外的所有值。整个哈希函数因此变为x1 == -8x2 == -7

y = x <= -7 ? S(x) : x <= 0 ? 1 - x : x;

这S(x)是一个简单的函数，它说明映射的位置x1和位置。根据您对数据的了解进行x2选择。S例如，如果您认为不太可能出现高目标值，请将它们映射到 6 和 7 S(x) = -1 - x。

最终映射为：

-8: 7    -7: 6    -6: 7    -5: 6    -4: 5    -3: 4    -2: 3    -1: 2
 0: 1     1: 1     2: 2     3: 3     4: 4     5: 5     6: 6     7: 7

将此逻辑带到 64 位空间，您将拥有

y = (x <= Long.MIN_VALUE + 1) ? -1 - x : x <= 0 ? 1 - x : x;

在此框架内可以进行许多其他类型的调整。

于 2012-07-22T19:58:03.820 回答
1

如果值为正，则可能可以直接使用，否则，反转所有位：

x >= 0 ? hash = x : hash = x ^ Long.MIN_VALUE

但是，如果 的值x是相关的（意思是：相似的对象为 产生相似的值x），您应该多打乱这个值，也许与

hash = a * (hash + b) % (Long.MAX_VALUE) + 1

对于一些正常数a和b， wherea应该相当大并且b防止0总是映射到1. 这也将整个事物映射到 [1,Long.MAX_VALUE] 而不是 [0,Long.MAX_VALUE]。通过更改 和 的值a，b您还可以实现更复杂的散列功能，例如Cooko 散列，这需要两个不同的散列函数。

绝对应该首选这样的解决方案，而不是每次使用时都为相同的值提供“奇怪的碰撞分布”的解决方案。

于 2012-07-24T09:39:21.123 回答
0

只需将您的输入值与 Long.MAX_VALUE 和 OR 与 1。不需要其他任何东西。

前任：

long hash = (input & Long.MAX_VALUE) | 1;
于 2012-07-26T04:18:53.007 回答
0

这似乎是最简单的：

(x % Long.MAX_VALUE) + 1

我会对所有给定方法的速度比较感兴趣。

于 2012-07-25T23:59:28.050 回答
0

只是为了确保你有一个 long 并且想将它散列到一个 int 吗？

你可以做...

(int) x                 // This results in a meaningless number, but it works
(int) (x & 0xffffffffl) // This will give you just the low order bits
(int) (x >> 32)         // This will give you just the high order bits
((Long) x).hashcode()   // This is the high and low order bits XORed together

如果你想保持很长时间，你可以做...

x & 0x7fffffffffffffffl // This will just ignore the sign, Long.MIN_VALUE -> 0
x & Long.MAX_VALUE      // Should be the same I think

如果得到一个 0 是不好的......

x & 0x7ffffffffffffffel + 1 // This has a 75% collision rate.

只是大声思考...

((x & Long.MAX_VALUE) << 1) + 1 // I think this is also 75%

我认为您需要接受 75% 或变得有点丑陋：

(x > 0) ? x : (x < 0) ? x & Long.MAX_VALUE : 7
于 2012-07-11T06:38:47.447 回答