algorithm - 半可逆整数哈希(请保持开放态度)

Question

我需要探索一个特定应用程序的整数散列主题我有几个要求：
整数到整数哈希
“半”可逆性我知道散列不是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）的大小的重要性是因为我需要知道需要为每个序数分配多少位，并且我希望通过为每个表条目分配相同数量的位来保持相对简单对。不过，我可能会处理小于一个字节的值。最初的域将是一个相对较小的大小。
我对你的任何想法和任何人可以参考的例子感兴趣。我认为这应该是可行的，但我想了解一系列可能的解决方案。
提前谢谢！
作记号

Answer 1

为所需的分发进行洗牌
在0..(n-1)域中应用一些双射来稍微洗牌。如果n是质数，这将特别容易，因为在这种情况下，可以将模运算视为一个字段，并执行各种良好的数学函数。有一件事可以使数字均匀分布以满足您的需要，那就是用一个固定的数乘以c，然后是模：

a ↦ (c*a) mod n

您必须选择c以便它与n互质，即gcd(c,n)=1如果n是一个素数，那么只要c≠0这是微不足道的，如果n是2的幂，那么任何奇数仍然足够。这一互质条件保证了另一个数d是c的inverse >，即它满足c*d ≡ 1 (mod n)，因此乘以d将取消乘以c的乘法效果。例如，您可以使用Java中的BigInteger.modInverse或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为2的幂的情况的洗牌方法是使用位移位、掩码和异或的一些组合来修改值这可以与上述乘法方法相结合，在乘法之前或之后进行位旋转，甚至两者都可以。做出选择在很大程度上取决于价值观的实际分布。
分开存放
结果值仍在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值（例如0）。如果无法在原始值集中实现此保留，则可能需要选择k作为2减1的幂，以便可以存储k本身的值来表示空单元格或者您可以交换hi和lo的含义，这样您就可以调整n的值以去掉一些值。我将在下面的例子中使用这个。
反转
要反转整件事，您可以使用键hi和存储值lo，将它们合并到a=k*hi+lo范围内的值0..(n-1)，然后撤消初始洗牌以返回原始值。
例子
这个例子是为了避免所有的乘法和除法。它将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);
  }
}

如您所见，可以避免所有的乘法和除法运算，以及所有显式的模调用。生成的代码是否比每次调用使用一个模块调用的代码具有更高的性能还有待测试事实上，您需要多达三个简化步骤来避免单一的模块，这使得成本相当高。
你可以看ademo run of the above code。