1

我需要探索特定应用程序的整数哈希主题。我有几个要求：

  • 整数到整数哈希
  • “半”可逆性。我知道哈希不会是 1-1 可逆的，所以请尝试理解我在 n-1 哈希方面的想法。假设我有一个数字 0...n 的原始域，我将其散列到一个较小的域 0...k 中。如果我使用函数 f(n) = k 散列，那么我想要一些可逆的东西，因为我也有一个“逆”g(k) = {n1,n2,n3, ..., nj} 都是可能的散列到 k 的域成员
  • 合理均匀和“随机”分布
  • 对于我的“逆”函数 g，我对返回的集合的大小有一个严格的限制，对于任何给定的 k，这个大小大致相同
  • 快速整数哈希

在这里稍微解释一下应用程序......我在内存非常受限的环境中运行。我打算不允许碰撞。也就是说，如果与表中的现有值发生冲突，插入操作就会失败。没关系。我不需要每次插入都能成功。我准备好在空间和速度上做出权衡。现在关键是，当我将值存储在表中时，我需要绝对最小化表示的位数。我所希望的基本上是：

如果我散列到值 k，我可以立即将我存储的内容缩小到原始域的一小部分。如果散列是“半可逆的”，并且我可以枚举散列到 k 的所有可能的域元素，那么我可以对它们进行排序并将序数分配给每种可能性。然后我想存储那个更小的序数而不是原始值，这将需要更少的位。然后我应该能够通过枚举存储的序数 i 的第 i 个可能性来完全扭转这一点。

对逆集合 g(k) 的大小进行严格限制的重要性是因为我需要知道我需要为每个序数分配多少位，并且我想通过分配相同数量的位来保持事情相对简单每个表条目。是的。不过，我可能会处理小于一个字节的值。初始域的大小相对较小。

我对你的任何想法和任何人可能参考的任何例子都感兴趣。我认为这应该是可行的，但我想了解可能的解决方案的范围。

提前致谢！标记

4

2 回答 2

2

随机播放所需的分布

0..(n-1)在域中应用一些双射来稍微洗牌。如果是素数，这将特别容易n，因为在这种情况下，您可以将模算术视为一个字段，并执行各种漂亮的数学函数。可能会根据您的需要均匀地分配数字的一件事可能是乘以一个固定的数字c，然后是模数：

a ↦ (c*a) mod n

你必须选择c它与n, 即互质gcd(c,n)=1。如果n是素数，那么只要 是微不足道的c≠0，如果n是 2 的幂，那么任何奇数仍然足够。这种共质性条件确保了另一个数的存在，d它是 的倒数，c即它满足c*d ≡ 1 (mod n)乘以d将取消乘以 的效果c。例如，您可以BigInteger.modInverse在 Java 或Wolfram Alpha中使用来计算这个数字。

如果您n是 2 的幂，那么您可以避免模运算（以及所需的时间），而是执行简单的位掩码操作。但即使对于 的其他值n，您有时也可以提出避免通用除法运算的方案。当您选择c（并d使用它）时，您可以这样做，c并且d只有很少的非零位。那么乘法很可能用位移和加法来表示。只要您确保这些数字是编译时常量，您的优化编译器就应该为您解决这个问题。

这是一个使此优化明确的示例。请注意，不必以这种方式编写代码：通常编写诸如(25*a)&1023.

// n = 1024
// c = 25 = 16+8+1
// d = 41 = 32+8+1

static unsigned shuffle(unsigned a) {
  return (a + (a << 3) + (a << 4)) & 1023;
}
static unsigned unshuffle(unsigned a) {
  return (a + (a << 3) + (a << 5)) & 1023;
}

另一种适用于二的幂的情况的改组方法n是使用位移、掩码和异或的某些组合来修改值。这可以与上述乘法方法相结合，在乘法之前或之后进行位旋转，甚至两者兼而有之。做出选择很大程度上取决于价值的实际分布。

拆分和存储

结果值仍然在范围内0..(n-1)，可以分成两个值：一个在范围内0..(k-1)并将被调用lo，另一个在0..(ceil(n/k)-1)我将调用的范围内hi。

lo = a mod k
hi = floor(a/k)

如果k是 2 的幂，则可以lo使用位掩码和hi位移位来获得。然后，您可以使用hi来表示哈希存储桶，并lo表示要存储在该存储桶中的值。所有具有相同hi值的值都会发生冲突，但它们的lo部分将有助于检索实际存储的值。

如果您想识别散列映射中未占用的插槽，则应确保lo在每个插槽中为此目的保留一个特定值（例如零）。如果您无法在原始值集中实现此保留，那么您可能希望选择k2 减一的幂，以便您可以存储k自身的值以表示空单元格。或者您可以交换 and 的含义hi，lo这样您就可以调整 的值n以省略一些值。我将在下面的示例中使用它。

倒置

要反转这整个过程，您需要获取 keyhi和存储的 value lo，将它们组合成a=k*hi+lorange 中的一个值0..(n-1)，然后撤消初始洗牌以返回原始值。

例子

这个例子旨在避免所有的乘法和除法。它在插槽上分配n=4032值，每个插槽可能k=64具有n/k=63不同的值加上一个特殊的空值。它使用c=577and进行洗牌d=1153。

unsigned char bitseq[50] = { 0 };

int store(unsigned a) {
  unsigned b, lo, hi, bitpos, byteno, cur;
  assert(a < 4032);                        // a has range 0 .. 0xfbf

  // shuffle
  b = (a << 9) + (a << 6) + a + 64;        // range 0x40 ..0x237dbf
  b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0x9d7f
  b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0x11ff
  b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0xfff
  b -= 64;                                 // range 0x00 .. 0xfbf

  // split
  lo = b & 63;                             // range 0x00 .. 0x3f
  hi = b >> 6;                             // range 0x00 .. 0x3e

  // access bit sequence
  bitpos = (lo << 2) + (lo << 1);          // range 0x00 .. 0x17a
  byteno = (bitpos >> 3);                  // range 0x00 .. 0x30
  bitpos &= 7;                             // range 0x00 .. 0x7
  cur = (((bitseq[byteno + 1] << 8) | bitseq[byteno]) >> bitpos) & 0xff;
  if (cur != 0) return 1; // slot already occupied.
  cur = hi + 1;           // range 0x01 .. 0x3f means occupied
  bitseq[byteno] |= (cur << bitpos) & 0xff;
  bitseq[byteno + 1] |= ((cur << bitpos) & 0xff00) >> 8;
  return 0;               // slot was free, value stored
}

void list_all() {
  unsigned b, lo, hi, bitpos, byteno, cur;
  for (lo = 0; lo != 64; ++lo) {
    // access bit sequence
    bitpos = (lo << 2) + (lo << 1);
    byteno = (bitpos >> 3);
    bitpos &= 7;
    cur = (((bitseq[byteno + 1] << 8) | bitseq[byteno]) >> bitpos) & 0x3f;
    if (cur == 0) continue;

    // recombine
    hi = cur - 1;
    b = (hi << 6) | lo;

    // unshuffle
    b = (b << 10) + (b << 7) + b + 64;
    b = (b & 0xfff) + ((b & 0xfff000) >> 6);
    b = (b & 0xfff) + ((b & 0xfff000) >> 6);
    b = (b & 0xfff) + ((b & 0xfff000) >> 6);
    b -= 64;

    // report
    printf("%4d was stored in slot %2d using value %2d.\n", b, lo, cur);
  }
}

如您所见，可以避免所有乘法和除法运算，以及所有显式模调用。生成的代码是否比每次调用使用单个模调用的代码具有更高的性能仍有待测试。您需要最多三个归约步骤来避免单个模数，这一事实使得这相当昂贵。

您可以观看上述代码的演示运行。

于 2013-09-10T08:25:00.503 回答
0

没有免费的午餐。

如果您的分布均匀，g(k1)那么n/k每个k1. 因此，您最终不得不存储k*n/k或n值，这恰好与您开始使用的数字相同。

您可能应该寻找压缩算法而不是哈希函数。它会提高你的谷歌魅力。

也就是说，在不知道数字分布的情况下很难提出压缩算法。如果它真的是随机的，那么它将很难压缩。

于 2013-09-10T08:19:34.533 回答