文章/答案/技术大牛

发布

社区首页 >问答首页 >半可逆整数散列(请保持开放心态)

问半可逆整数散列(请保持开放心态)
EN

Stack Overflow用户

提问于 2013-09-10 02:30:17

回答 2查看 528关注 0票数 1

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

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

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

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

关于逆集g(k)大小的紧界的重要性是因为我需要知道我需要为每个序号分配多少位，并且我希望通过为每个表条目分配相同的位数来保持相对简单。是。不过，我可能会处理小于一个字节的值。最初的域名将是一个相对较小的规模开始。

我对你的任何想法和任何人可能提到的例子都感兴趣。我认为这应该是可行的，但我想了解各种可能的解决办法。

提前感谢！标记

algorithm

math

hash

integer

inverse

回答 2

Stack Overflow用户

发布于 2013-09-10 08:25:00

洗牌以进行所需分配

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

a ↦ (c*a) mod n

您必须选择c，以便它与n (即gcd(c,n)=1 )是对等的。如果n是素数，那么这和c≠0一样简单，如果n是2的幂，那么任何奇数都足够了。这种同质性条件保证了另一个数d的存在-- 逆 of c，即满足c*d ≡ 1 (mod n)，从而使d乘法消除了c的乘法效应。例如，您可以在Java或沃尔夫拉姆阿尔法中使用沃尔夫拉姆阿尔法来计算这个数字。

如果您的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;
}

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

拆分和存储

结果值仍然在范围0..(n-1)中，可以分为两个值:一部分在范围0..(k-1)中，将被称为lo，另一部分在range 0..(ceil(n/k)-1)中，我将称之为hi。

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

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

如果要识别散列映射中未占用的槽，则应确保在每个时隙中为此目的保留一个特定的lo值(例如零)。如果无法在原始值集中实现此保留，则可能需要选择k作为二减一的幂，以便存储k本身的值以表示空单元格。或者您可以交换hi和lo的含义，这样您就可以调优n的值以省略一些值。我将在下面的示例中使用此方法。

倒置

要反转整个过程，您可以使用键hi和存储值lo，将它们组合到范围0..(n-1)中的值a=k*hi+lo，然后撤消初始的洗牌以返回到原始值。

示例

这个例子是为了避免所有乘法和除法。它在n=4032插槽上分配k=64值，其中n/k=63不同的值加上每个时隙可能有一个特殊的空值。它确实使用c=577和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);
  }
}

如您所见，可以避免所有乘法和除法操作，以及所有显式模调用。生成的代码是否比每次调用使用一个模块调用的代码具有更高的性能还有待测试。事实上，您需要多达三个减少步骤，以避免单一模块，这使得这相当昂贵。

你可以看以上代码的演示运行。

票数 2

Stack Overflow用户

发布于 2013-09-10 08:19:34

没有免费午餐这样的东西。

如果您有一个均匀的发行版，那么g(k1)将为每个k1提供n/k值。因此，您最终不得不存储k*n/k或n值，这恰好是您开始使用的相同的数字。

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

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

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/18709855

复制

相似问题

问半可逆整数散列(请保持开放心态)
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问半可逆整数散列(请保持开放心态)EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问半可逆整数散列(请保持开放心态)
EN