使用动态完美哈希在 64 位整数值的小型容器中进行超快速查找
Ultra fast lookup in small sized container of 64-bit integer values using dynamic perfect hashing
我有输入密钥，可以廉价地转换为 uint64_t（即，输入包含小于或等于 64 位）。
每个唯一键（尚未在地图中）将被分配一些数据（指向对象的指针）。很像 std::map<uint64_t, Object*> 这样。
插入新密钥对时间要求不高，因为总共只有少量密钥，这些密钥永远不会被再次移除。其中 small 小于 100.
一个典型的实现会使用std::vector（因为元素数量少）并且要么只扫描所有元素，要么使用二进制搜索（即boost::flat_map）；但这对我来说还不够理想。一旦所有元素都被插入，映射是静态的，应该可以在几个时钟周期内找到属于给定键的指针。
我想到的是每次插入新密钥时确定一个完美的散列，然后使用这个散列（函数）找回指针。
这需要两件事：
一种寻找廉价哈希函数的算法，该函数将给定的 64 位值的较小列表转换为 8、9、10（或需要多少）位而没有冲突（又名，a完美的哈希函数），以便后者可以直接用于查找 table（即 256、512、1024... 大小）。
一种动态创建这种哈希函数的方法；我不得不承认我不愿意 运行 外部编译器并动态加载新的哈希函数 ;-).
如果您有一个包含常量的散列函数，那么对于该常量的每个可能值，您都有一个“新”函数。例如，您可以将 64 位值散列为 0-1023 之间的值，您可以将其用作查找 table 的索引，如下所示：
int HashValue(int64_t key, int mult)
{
return (int)(key ^ ((key * mult) >> 32)) & 1023;
}
其中 mult 是乘数常数。对于一组给定的 <= 100 个键，您可以尝试 mult 的随机值，直到找到一个不会导致任何冲突的值。我试了一下，它通常会在散列到 0-1023 范围时尝试大约 50 次后找到一个“完美”的散列函数。对于 0-511，它需要大约 20000 次尝试，对于 0-255，它失败了。
下面的示例 C++ 实现：
using namespace std;
#include <stdlib.h>
#include <time.h>
#include <list>
#include <unordered_set>
int HashValue(int64_t key, int mult)
{
return (int)(key ^ ((key * mult) >> 32)) & 1023;
// slower alternative with more thorough mixing
// key = key ^ (key * mult);
// int hash = (int)(key ^ (key >> 32));
// hash ^= key >> 16;
// return (hash ^ (hash >> 8)) & 1023;
}
int FindHash(std::list<int64_t> keys)
{
for(int i = 0; i < 10000; i++) // try 10000 times
{
std::unordered_set<int> hashset;
bool collided = false;
int mult = rand();
for (std::list<int64_t>::iterator it = keys.begin(); it != keys.end(); it++)
{
int val = HashValue(*it, mult);
if(hashset.find(val) != hashset.end())
{
collided = true;
break;
}
hashset.insert(val);
}
if(!collided)
{
std::cout << "Found collision-free function with mult = " << mult << " on attempt " << i;
return mult;
}
}
std::cout << "Failed to find collision-free hashing function";
return 0;
}
int main()
{
// test with 100 random keys
srand (time(NULL));
std::list<int64_t> keys = {};
for(int i = 0; i < 100; i++)
{
// 64 bit random number
keys.push_back(((int64_t)rand() << 32) | rand());
}
FindHash(keys);
return 0;
}
第 3 部分
我完成了 UltraHash 的实现。结果比我预期的要好——而且确实比“乘法散列”方法好得多。
- 64 位密钥的转换 --> 查找 table 索引需要 67 个时钟周期（18 ns）。
- 对于 100 个键，查找 table 索引不是 10 位、9 位或 8 位...而是 7 位！如果你的键数少于 64 个，你可能会得到 6 位。 200个key，返回的索引仍然只有8位！
- 用键初始化
UltraHash 对象，不需要 0.3 秒 - 不..需要 1 到 3 毫秒！
涉及的代码量太多，无法粘贴到这里（我想？~800 行）。不过其中 lot 行是注释。我确实详细解释了代码的作用以及算法的工作原理。如果有人有兴趣并希望将它包含在这里，请告诉我，我会花更多时间做这件事。
主要思想如下：
每个 n 键都是 64 位 - 我们可以将整体视为 n x 64 的矩阵。对 64 列中的每一列进行随机性检查（非常基本），然后按照对每组 32 到 64 个密钥的均匀分布密钥集的贡献可能性的顺序对它们进行排序。然后通过蛮力选择列的组合，导致将键划分为所述集合，其中尝试为每个集合找到一个完美的散列。失败时列数增加。
找到一组 32 到 64 个键的完美散列是通过 GF(2) 上的线性代数完成的，这涉及高斯消元法等
您可以找到代码 here and the accompanied header here。
由于代码是我的 utils git 子模块的一部分，它使用该库中的其他文件，以及来自 cwds, but it should be easy to make it work standalone. The project ai-utils-testsuite is a configurable and compile-able project that contains benchmark and test code.
的调试代码
下面是其中一个函数之前的注释
在 UltraHash.cxx:
// This function checks if the n given keys (in K) are linear independent and
// if they are - fills in Mᵀ with the magic numbers to convert the keys to a
// number in the range [0, 64> (64 --> 6 bits); the perfect hash.
//
// This involves solving a linear (matrix) equation of the form:
//
// K M = L
//
// Where each row of K is a 64-bit key, M is to be solved, and L exists
// of rows that are - in fact - the values returned by UtraHash::index:
// 6 bit numbers.
//
// For example, let K be a 3x5 matrix (3 keys of 5 bits):
//
// Column 0 (lsb)
// |
// v
// ⎡ 1 1 0 1 1 ⎤ <-- row 0 = key 1
// K = ⎢ 1 1 1 0 1 ⎥ key 2
// ⎣ 1 1 1 1 0 ⎦ key 3
//
// Note that column 0 is stored in the least significant bit of the uint64_t,
// the uint64_t values of the keys are therefore 27, 23 and 15, in this example.
//
// In order to visualize the relationship with the std::array<uint64_t, sz>
// variables we'll put column 0 on the right, but then also invert the rows
// in order to keep an indentity matrix visually unchanged (rotate the whole
// thing 180 degrees).
//
// Column 0 (lsb)
// |
// v
// ⎡ 0 1 1 1 1 ⎤ K[2] = 15
// K = ⎢ 1 0 1 1 1 ⎥ K[1] = 23
// ⎣ 1 1 0 1 1 ⎦ <-- row 0, K[0] = 27
//
// Furthermore, let L be such that it simply contains each row number in order:
//
// Column 0 (lsb)
// |
// v
// ⎡ 1 0 ⎤ row 2: 2
// L = ⎢ 0 1 ⎥ row 1: 1
// ⎣ 0 0 ⎦ <-- row 0: 0
//
// Note that values in the rows of L don't really matter, as long as they
// are all different.
//
// The matrix equation K M = L reads, in this example,
//
// ⎡ z e ⎤ <-- msb
// ⎡ 0 1 1 1 1 ⎤ ⎢ y d ⎥ ⎡ 1 0 ⎤
// ⎢ 1 0 1 1 1 ⎥ ⎢ x c ⎥ = ⎢ 0 1 ⎥
// ⎣ 1 1 0 1 1 ⎦ ⎢ w b ⎥ ⎣ 0 0 ⎦
// ⎣ v a ⎦
// ^
// |
// index 0
//
// where edcba is the binary representation of the value in the first position of MT, etc.
// Namely, if we transpose M, we get:
//
// lsb (column 0 of Mᵀ; row 0 of M).
// |
// v
// ⎡z y x w v ⎤
// Mᵀ = ⎣e d c b a ⎦ <-- MT[0] (row 0 of Mᵀ / column 0 of M).
//
// The matrix equation remains the same if we substract row i from row j (i != j)
// in both K and L, provided all rows in both matrices are different.
//
// If the keys are linearly independent we'll be able to put K
// in row echelon form (K') where each next row has more zeroes in
// the leading columns (or since we put the matrix upside down,
// in the trailing colums):
//
// For example, subtracting (XOR-ing) the bottom row (row 0) from row 1 and 2,
// and then substracting row 1 from row 2, gives
//
// ⎡ z e ⎤
// ⎡ 1 1 0 0 0 ⎤ ⎢ y d ⎥ ⎡ 1 1 ⎤
// K' = ⎢ 0 1 1 0 0 ⎥ ⎢ x c ⎥ = ⎢ 0 1 ⎥
// ⎣ 1 1 0 1 1 ⎦ ⎢ w b ⎥ ⎣ 0 0 ⎦
// ⎣ v a ⎦
//
// Where each row (starting at the bottom) has more zeroes on the
// right than the previous row (the row below it).
//
// This already proves that the keys were linearly independent,
// because there is no row that has all zeroes in K.
// Note that even if there was a row in K with all zeroes, we might
// still be able to find a solution if also L has all zeroes in that row.
//
// The above is corresponding to the set of equations:
// ⎡ 1 1 0 ⎤
// Lᵀ = ⎣ 1 0 0 ⎦
// 1 1 0 0 0
// e+d = 1
// z+y = 1
//
// 0 1 1 0 0
// d+c = 1
// y+x = 0
//
// 1 1 0 1 1
// e+d +b+a = 0
// z+y +w+v = 0
//
// and from top to bottom we want to
//
// 1) set d to 1 (keep e at 0).
// set y to 1 (keep z at 0).
// 2) set c to 1 + d.
// set x to 0 + y.
// 3) set a to 0 + e + d (keep b at 0).
// set v to 0 + z + y (keep w at 0).
//
// It is easy to verify that this answer also holds in the original
// equation:
// 1 0 <---- 1 0 <-- column m.
// .-- row n v v | | .-- row n.
// v ⎡ 0 0 ⎤ v v v
// 2 ⎡ 0 1 1 1 1 ⎤ ⎢ 1 1 ⎥ ⎡ 1 0 ⎤ 2
// 1 ⎢ 1 0 1 1 1 ⎥ ⎢ 1 0 ⎥ = ⎢ 0 1 ⎥ 1
// 0 ⎣ 1 1 0 1 1 ⎦ ⎢ 0 0 ⎥ ⎣ 0 0 ⎦ 0
// ⎣ 1 1 ⎦
//
// That is, the bit in L at row n and column m is the parity of
// the bit-wise AND between the key at row n in K and column m of M.
//
// Finally we transpose this result to get the output variable MT:
//
// ⎡ 0 1 1 0 1 ⎤
// Mᵀ = ⎣ 0 1 0 0 1 ⎦
//
// Since a zero key always results in a zero in L, we can not use
// the value zero in L when one of the keys in zero. Instead we
// ignore the key and use different and non-zero values in L.
//
// For example, if we had the same keys as in the above example,
// but ALSO an all zeroes key:
//
// ⎡ 1 1 0 1 1 ⎤ <-- row 0 = key 1
// ⎢ 0 0 0 0 0 ⎥ key 2
// K = ⎢ 0 1 1 0 0 ⎥ key 3
// ⎣ 0 1 1 1 1 ⎦ key 4
//
// Then the zero key is removed and we use for L the matrix
//
// ⎡ 1 1 ⎤
// L = ⎢ 1 0 ⎥
// ⎣ 0 1 ⎦
//
// The algorithm to solve M from K' in row echelon form is, as you can see
// from the 1) 2) 3) steps above, done per whole row of M:
//
// First, we start with M being all zeroes:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 0 0 ⎥ 3
// ⎢ 0 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// We skip over row 4, leaving it all zeroes, because the first row of
// K' is 1 1 0 0 0
// 4 3 <-- start with row 3.
// ^-- the last 1.
// And that row is made equal to the first row of L: 1 1.
// The result after step 1) is therefore:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3 <-- last updated.
// ⎢ 0 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// The next row of K' is 0 1 1 0 0
// 4 3 2 <-- continue with row 2.
// ^-- the last 1.
// And that row is made equal to L's second row [ 0 1 ]
// XOR the current row of K' times M so far:
//
// ⎡ 0 0 ⎤
// ⎢ 1 1 ⎥
// [ 0 1 1 0 0 ] ⎢ 0 0 ⎥ = [ 1 1 ]
// ⎢ 0 0 ⎥
// ⎣ 0 0 ⎦
//
// [ 0 1 ] + [ 1 1 ] = [ 1 0 ]
//
// So that after step 2) M has become:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3
// ⎢ 1 0 ⎥ 2 <-- last updated.
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// The final row of K' is 1 1 0 1 1
// 4 3 2 1 0 <-- continue with row 0.
// ^-- the last 1.
// The next row of L is [ 0 0 ] and
//
// ⎡ 0 0 ⎤
// ⎢ 1 1 ⎥
// [ 0 0 ] + [ 1 1 0 1 1 ] ⎢ 1 0 ⎥ = [ 1 1 ]
// ⎢ 0 0 ⎥
// ⎣ 0 0 ⎦
//
// So that after step 3) M has become:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3
// ⎢ 1 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 1 1 ⎦ 0 <-- last updated.
//
相信我，这是我为一个函数写的最长评论:)。
原版POST:
随机倍数法
我尝试了与 samgak 相同的方法：我的散列函数只是 uint64_t 密钥与 uint64_t 乘数的乘积，然后我尝试了乘数的随机值，直到最少 high-bits 个结果不同。事实证明，这很容易需要 0.3 秒才能达到 9 位输出。
这里我使用了下面的函数来求出需要的高位数：
// Return the maximal right-shift that is possible on
// the values in `hashes` such that the results are still all different.
int max_shift(std::vector<uint32_t> hashes)
{
std::sort(hashes.begin(), hashes.end());
int sm = 0;
int sz = hashes.size();
for (int i = 1; i < sz; ++i)
{
uint32_t d = hashes[i - 1] ^ hashes[i];
int s = std::countl_zero(d);
if (s > sm)
sm = s;
}
return 31 - sm;
}
这里的hashes例如就是乘法结果的最高32位；较低的 32 位将被移出/忽略。
考虑到 100 个值，小于 128，理论上适合 7 位（尽管我从来没有用上述方法找到 8 位；当你意识到随机尝试的机会对应于有 100 个人和 256 个生日的生日问题；1 in 5807421181 chance 没有碰撞）而且我发现等待 0.3 秒，理论上要长得多，有点烦人——我开始考虑一种计算哈希函数的方法。
为了能够进行任何计算，我决定使用线性代数方法。
使用线性代数
想法是使用线性代数（矩阵，向量）。由于我们正在处理任意位，最合乎逻辑的做法是处理 
。好的，这种从 LaTeX 到图像的外部转换不起作用，我将使用 UTF8：ℤ₂
让所有的输入键都用64维的列向量在ℤ₂上表示：ᵢ。
注意最多可以存在 64 个这样的线性无关向量。假设我们有 64 个这样的键。然后我们可以构造矩阵
K = [₀ ₁ … ᵢ … ₆₃]
并计算它的倒数（因为 ᵢ 是线性独立的）。让我们用 K⁻¹ 表示这个逆。
此外，注意我们需要6位来枚举64个输入键。现在令6×64矩阵L为所有6维列向量存在的矩阵：
⎡ 0 0 0 0 0 1 1 ⎤
⎢ 0 0 0 0 0 1 1 ⎥
L = ⎢ 0 0 0 0 0 ... 1 1 ⎥
⎢ 0 0 0 0 1 1 1 ⎥
⎢ 0 0 1 1 0 1 1 ⎥
⎣ 0 1 0 1 0 0 1 ⎦
设6×64矩阵M为
M = L K⁻¹
然后
M K = L K⁻¹ K = L
和left-multiplying任何带有M的输入键ᵢ都会给出一个唯一的6位列向量；又名 - 完美哈希。
线性相关键
这种方法的主要问题当然是输入键可能不是线性独立的，当超过 64 个键时肯定会出现这种情况。
为了检测 if/when 键不是线性独立的，我们可以在新键进入时简单地对矩阵 K 进行三角剖分。为了举例，假设我们有 vectors/keys 个4 位而不是 64 位。
考虑以下五个不同的输入键：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝1⎠ ⎝1⎠ ⎝0⎠ ⎝1⎠
然后我们从单位矩阵开始（主对角线上的所有元素和重置零），并放置第一个键，使顶部 1 与矩阵对角线上的 1 对齐：
⎡ 0 0 0 1 ⎤
K'= ⎢ 0 0 1 0 ⎥
⎢ 0 1 1 0 ⎥
⎣ 1 0 0 0 ⎦
* <-- used
因此，这个矩阵有一个逆矩阵，因为upper-left三角形全为零，主对角线全为1。
下一个键，V₁，同样可以as-is放在这个矩阵中：
⎡ 0 0 0 1 ⎤
K'= ⎢ 0 0 1 0 ⎥
⎢ 0 1 1 1 ⎥
⎣ 1 0 0 1 ⎦
* * <-- used
现在使用第四列，所以我们不能用它来输入 V2（顶部也有一个 1）。因此，我们首先从 V2 中减去第四列（请注意，对 ℤ2 的减法是加法模 2，也称为异或运算）。 V2 则变为：
⎛1⎞ ⎛1⎞ ⎛0⎞
⎜0⎟ - ⎜0⎟ =⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟
⎝1⎠ ⎝1⎠ ⎝0⎠
我们可以将它放在矩阵的第 2 列中（这不会改变它）。
V₃ 现在不能再放在第 2 列，因为它是“used”。
如果我们尝试使用相同的技巧，从 V₃ 中减去第 2 列，我们得到
⎛0⎞ ⎛0⎞ ⎛0⎞
⎜0⎟ - ⎜0⎟ =⎜0⎟
⎜1⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝0⎠ ⎝0⎠
全为零。这表明前四个键是线性相关的。
我们可以通过在底部用 1 扩展向量（以及所有其他带有零的向量）来缓解这种情况：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠ ⎝0⎠
如果我们用这些输入重复相同的事情，我们会得到完全相同的矩阵，但在左下角多了一个 1：
⎡ 0 0 0 0 1 ⎤
K'= ⎢ 0 0 0 1 0 ⎥
⎢ 0 0 1 1 1 ⎥
⎢ 0 1 0 0 1 ⎥
⎣ 1 0 0 0 0 ⎦
* * * * <-- used
V₄ 结果也是线性相关的：它的顶部有一个 1，因此减去最后一列，然后我们得到（现在）已经使用的第四列。因此我们必须添加另一行：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠
和
⎡ 0 0 0 0 0 1 ⎤
K'= ⎢ 0 0 0 0 1 0 ⎥
⎢ 0 0 0 1 1 1 ⎥
⎢ 0 0 1 0 0 1 ⎥
⎢ 0 1 0 0 0 0 ⎥
⎣ 1 0 0 0 0 0 ⎦
* * * * * <-- used
现在让我们按照上面的描述构造 K（只需将所有 V 放入其中）：
⎡ 0 1 1 . 0 1 ⎤
⎢ 1 0 0 . 0 1 ⎥
K = ⎢ 1 1 0 . 1 0 ⎥
⎢ 0 1 1 . 0 1 ⎥
⎢ 0 0 0 . 1 0 ⎥
⎣ 0 0 0 . 0 1 ⎦
我将第四列留空，因为即使（原始）密钥是 4 位，我们也只能找到三个线性独立的密钥。也就是说，如果密钥是 64 位，而我们只能找到 62 个线性无关的密钥，我们将留空 2 列。那就是……我们将用与之前的密钥线性独立的伪密钥填充它们；这将导致那些列的低位为零：
⎡ 0 1 1 . 0 1 ⎤
⎢ 1 0 0 . 0 1 ⎥
K = ⎢ 1 1 0 . 1 0 ⎥
⎢ 0 1 1 . 0 1 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
此外，缺少的线性无关键通常是K'中未使用的列，因此可以通过将对角线从右下角延伸到左上角来完成K:
⎡ 0 1 1 0 0 1 ⎤
⎢ 1 0 0 0 0 1 ⎥
K = ⎢ 1 1 0 0 1 0 ⎥
⎢ 0 1 1 1 0 1 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
因为现在所有的列都是线性无关的，所以这个矩阵有一个逆矩阵，在这种情况下就是
⎡ 0 1 0 0 0 1 ⎤
⎢ 0 1 1 0 1 1 ⎥
K⁻¹=⎢ 1 1 1 0 1 0 ⎥
⎢ 1 0 0 1 0 0 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
最初我们有 5 个输入键，但即使有额外的伪键，我们也可以用 3 位来枚举它。但是，考虑到我们对伪密钥的结果并不真正感兴趣 - 因此我们使用以下 L:
⎡ 0 0 0 ? 0 1 ⎤
L = ⎢ 0 0 1 ? 1 0 ⎥
⎣ 0 1 0 ? 1 0 ⎦
您可以在第四列中填写任何内容。
如果填写下一个数字（5）：
⎡ 0 0 0 1 0 1 ⎤
L = ⎢ 0 0 1 0 1 0 ⎥
⎣ 0 1 0 1 1 0 ⎦
然后
⎡ 1 0 0 1 0 1 ⎤
M = L K⁻¹ = ⎢ 1 1 1 0 0 0 ⎥
⎣ 1 1 1 1 0 1 ⎦
用原始密钥（V₀、V₁、V₂、V₃ 和 V₄）构建 Kₒ：
⎡ 0 1 1 0 1 ⎤
Kₒ=⎢ 1 0 0 0 1 ⎥
⎢ 1 1 0 1 0 ⎥
⎣ 0 1 1 0 1 ⎦
并使用没有最后两列的 M，
⎡ 1 0 0 1 ⎤
M = ⎢ 1 1 1 0 ⎥
⎣ 1 1 1 1 ⎦
我们得到
⎡ 0 0 0 0 0 ⎤
M Kₒ = ⎢ 0 0 1 1 0 ⎥
⎣ 0 1 0 1 1 ⎦
显示与该矩阵 M 相乘不是完美的散列：最后一列与第二列相同。
确切的变化是显而易见的：如果我们使用了完整的矩阵（包括最后两列）和扩展键，那么只有最后一个键在最后一列中有一个 1，因此 XOR-ed矩阵的最后一列：
⮶what we get
1 1 0
0 XOR 0 = 0
0 1 1
⮴expected
因此，纠正输出的唯一方法是根据该列的前四位知道它属于 K 的哪一列（最后一列），这很像我们试图解决的原始问题开始。
第 2 部分
诀窍是将键分成 64 个或更少线性独立键的集合。这很容易，因为对于完全随机的 64 位值，平均前 62.18 个键将是线性独立的，这足够接近 64 是有效的。
然而，密钥应该很好地散列，例如，如果 64 位密钥是 uint64_t，值在 0 到 64 之间，只使用 6 位，那么你显然只能找到 6 个线性独立的一次钥匙，至少需要 64 / 6 = 11 套。
这会减慢查找速度，因为在将键与正确的矩阵相乘之前，您必须能够确定键属于哪个集合。
一种方法是对键进行排序并记住下一组中第一个键的值（第一个键线性依赖于上一组中的键）。
例如，假设我们有三组：
S₀={V₀,V₁,V₂}, S₁={V₃,V₄} and S₂={V₅,V₆,V₇,V₈}
因为V₃可以用S₀中的key表示（例如V₀ + V₂），而V₅可以表示为V₃ + V₄。
让我们试着想一个这样的例子。请记住，我们对键进行了排序，因此 V₀<V₁<V₂<V₃<V₄<V₅<V₆<V₇<V₈ 当表示为数字时。假设存储它们的无符号整数的最低有效位对应于向量的第 0 行，则可能的值可能是：
{ 0b00001, 0b00010, 0b00100 }, { 0b00101, 0b01000 }, { 0b01101, 0b01111, 0b11001, 0b11110 }
或
⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛1⎞ ⎛1⎞
⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟
V₀=⎜0⎟, V₁=⎜0⎟, V₂=⎜1⎟, V₃=⎜1⎟, V₄=⎜0⎟, V₅=⎜1⎟, V₆=⎜1⎟,V₇=⎜0⎟, V₈=⎜1⎟
⎜0⎟ ⎜1⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎝1⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠ ⎝0⎠ ⎝1⎠ ⎝1⎠ ⎝1⎠ ⎝0⎠
所以 V₃=V₀+V₂ 和 V₅=V₃+V₄.
但我们可以做得更好！不需要对key进行排序，用<来指定set之间的边界。一种非常有效的方法是使用二叉树在每次使用一个特定位时找到正确的集合。
请注意，预计有 ~100 个键和大小为 ~62 的集合 - 我们预计只有两个集合！所以只有一个位可以打开。这个位可以通过反复试验找到。在上面的例子中我们可以创建以下两组线性无关的向量：
S₀={V₁,V₂,V₄,V₈} and S₁={V₀,V₃,V₅,V₆,V₇}
只需打开最低有效位即可。
一百个 64 位密钥的总查找代码将存在测试 1 位，确定使用六个 64 位值中的哪个 table，然后进行六次异或运算（可以是理论上并行完成；因此应该大约 3 个时钟周期）和同样的 6 个奇偶校验测试——我将其计为 6 个时钟周期（有关奇偶校验的更多信息，请参见 ）。这给我带来了十几个时钟周期左右。结果将是 7 位，而不是 9 位！此外，计算这些矩阵可以比 0.3 秒快得多。
当我有工作代码时，我会post更新。
我有输入密钥，可以廉价地转换为 uint64_t（即，输入包含小于或等于 64 位）。
每个唯一键（尚未在地图中）将被分配一些数据（指向对象的指针）。很像 std::map<uint64_t, Object*> 这样。
插入新密钥对时间要求不高，因为总共只有少量密钥，这些密钥永远不会被再次移除。其中 small 小于 100.
一个典型的实现会使用std::vector（因为元素数量少）并且要么只扫描所有元素，要么使用二进制搜索（即boost::flat_map）；但这对我来说还不够理想。一旦所有元素都被插入，映射是静态的，应该可以在几个时钟周期内找到属于给定键的指针。
我想到的是每次插入新密钥时确定一个完美的散列，然后使用这个散列（函数）找回指针。
这需要两件事：
一种寻找廉价哈希函数的算法，该函数将给定的 64 位值的较小列表转换为 8、9、10（或需要多少）位而没有冲突（又名，a完美的哈希函数），以便后者可以直接用于查找 table（即 256、512、1024... 大小）。
一种动态创建这种哈希函数的方法；我不得不承认我不愿意 运行 外部编译器并动态加载新的哈希函数 ;-).
如果您有一个包含常量的散列函数，那么对于该常量的每个可能值，您都有一个“新”函数。例如，您可以将 64 位值散列为 0-1023 之间的值，您可以将其用作查找 table 的索引，如下所示：
int HashValue(int64_t key, int mult)
{
return (int)(key ^ ((key * mult) >> 32)) & 1023;
}
其中 mult 是乘数常数。对于一组给定的 <= 100 个键，您可以尝试 mult 的随机值，直到找到一个不会导致任何冲突的值。我试了一下，它通常会在散列到 0-1023 范围时尝试大约 50 次后找到一个“完美”的散列函数。对于 0-511，它需要大约 20000 次尝试，对于 0-255，它失败了。
下面的示例 C++ 实现：
using namespace std;
#include <stdlib.h>
#include <time.h>
#include <list>
#include <unordered_set>
int HashValue(int64_t key, int mult)
{
return (int)(key ^ ((key * mult) >> 32)) & 1023;
// slower alternative with more thorough mixing
// key = key ^ (key * mult);
// int hash = (int)(key ^ (key >> 32));
// hash ^= key >> 16;
// return (hash ^ (hash >> 8)) & 1023;
}
int FindHash(std::list<int64_t> keys)
{
for(int i = 0; i < 10000; i++) // try 10000 times
{
std::unordered_set<int> hashset;
bool collided = false;
int mult = rand();
for (std::list<int64_t>::iterator it = keys.begin(); it != keys.end(); it++)
{
int val = HashValue(*it, mult);
if(hashset.find(val) != hashset.end())
{
collided = true;
break;
}
hashset.insert(val);
}
if(!collided)
{
std::cout << "Found collision-free function with mult = " << mult << " on attempt " << i;
return mult;
}
}
std::cout << "Failed to find collision-free hashing function";
return 0;
}
int main()
{
// test with 100 random keys
srand (time(NULL));
std::list<int64_t> keys = {};
for(int i = 0; i < 100; i++)
{
// 64 bit random number
keys.push_back(((int64_t)rand() << 32) | rand());
}
FindHash(keys);
return 0;
}
第 3 部分
我完成了 UltraHash 的实现。结果比我预期的要好——而且确实比“乘法散列”方法好得多。
- 64 位密钥的转换 --> 查找 table 索引需要 67 个时钟周期（18 ns）。
- 对于 100 个键，查找 table 索引不是 10 位、9 位或 8 位...而是 7 位！如果你的键数少于 64 个，你可能会得到 6 位。 200个key，返回的索引仍然只有8位！
- 用键初始化
UltraHash对象，不需要 0.3 秒 - 不..需要 1 到 3 毫秒！
涉及的代码量太多，无法粘贴到这里（我想？~800 行）。不过其中 lot 行是注释。我确实详细解释了代码的作用以及算法的工作原理。如果有人有兴趣并希望将它包含在这里，请告诉我，我会花更多时间做这件事。
主要思想如下：
每个 n 键都是 64 位 - 我们可以将整体视为 n x 64 的矩阵。对 64 列中的每一列进行随机性检查（非常基本），然后按照对每组 32 到 64 个密钥的均匀分布密钥集的贡献可能性的顺序对它们进行排序。然后通过蛮力选择列的组合，导致将键划分为所述集合，其中尝试为每个集合找到一个完美的散列。失败时列数增加。
找到一组 32 到 64 个键的完美散列是通过 GF(2) 上的线性代数完成的，这涉及高斯消元法等
您可以找到代码 here and the accompanied header here。
由于代码是我的 utils git 子模块的一部分，它使用该库中的其他文件，以及来自 cwds, but it should be easy to make it work standalone. The project ai-utils-testsuite is a configurable and compile-able project that contains benchmark and test code.
下面是其中一个函数之前的注释
在 UltraHash.cxx:
// This function checks if the n given keys (in K) are linear independent and
// if they are - fills in Mᵀ with the magic numbers to convert the keys to a
// number in the range [0, 64> (64 --> 6 bits); the perfect hash.
//
// This involves solving a linear (matrix) equation of the form:
//
// K M = L
//
// Where each row of K is a 64-bit key, M is to be solved, and L exists
// of rows that are - in fact - the values returned by UtraHash::index:
// 6 bit numbers.
//
// For example, let K be a 3x5 matrix (3 keys of 5 bits):
//
// Column 0 (lsb)
// |
// v
// ⎡ 1 1 0 1 1 ⎤ <-- row 0 = key 1
// K = ⎢ 1 1 1 0 1 ⎥ key 2
// ⎣ 1 1 1 1 0 ⎦ key 3
//
// Note that column 0 is stored in the least significant bit of the uint64_t,
// the uint64_t values of the keys are therefore 27, 23 and 15, in this example.
//
// In order to visualize the relationship with the std::array<uint64_t, sz>
// variables we'll put column 0 on the right, but then also invert the rows
// in order to keep an indentity matrix visually unchanged (rotate the whole
// thing 180 degrees).
//
// Column 0 (lsb)
// |
// v
// ⎡ 0 1 1 1 1 ⎤ K[2] = 15
// K = ⎢ 1 0 1 1 1 ⎥ K[1] = 23
// ⎣ 1 1 0 1 1 ⎦ <-- row 0, K[0] = 27
//
// Furthermore, let L be such that it simply contains each row number in order:
//
// Column 0 (lsb)
// |
// v
// ⎡ 1 0 ⎤ row 2: 2
// L = ⎢ 0 1 ⎥ row 1: 1
// ⎣ 0 0 ⎦ <-- row 0: 0
//
// Note that values in the rows of L don't really matter, as long as they
// are all different.
//
// The matrix equation K M = L reads, in this example,
//
// ⎡ z e ⎤ <-- msb
// ⎡ 0 1 1 1 1 ⎤ ⎢ y d ⎥ ⎡ 1 0 ⎤
// ⎢ 1 0 1 1 1 ⎥ ⎢ x c ⎥ = ⎢ 0 1 ⎥
// ⎣ 1 1 0 1 1 ⎦ ⎢ w b ⎥ ⎣ 0 0 ⎦
// ⎣ v a ⎦
// ^
// |
// index 0
//
// where edcba is the binary representation of the value in the first position of MT, etc.
// Namely, if we transpose M, we get:
//
// lsb (column 0 of Mᵀ; row 0 of M).
// |
// v
// ⎡z y x w v ⎤
// Mᵀ = ⎣e d c b a ⎦ <-- MT[0] (row 0 of Mᵀ / column 0 of M).
//
// The matrix equation remains the same if we substract row i from row j (i != j)
// in both K and L, provided all rows in both matrices are different.
//
// If the keys are linearly independent we'll be able to put K
// in row echelon form (K') where each next row has more zeroes in
// the leading columns (or since we put the matrix upside down,
// in the trailing colums):
//
// For example, subtracting (XOR-ing) the bottom row (row 0) from row 1 and 2,
// and then substracting row 1 from row 2, gives
//
// ⎡ z e ⎤
// ⎡ 1 1 0 0 0 ⎤ ⎢ y d ⎥ ⎡ 1 1 ⎤
// K' = ⎢ 0 1 1 0 0 ⎥ ⎢ x c ⎥ = ⎢ 0 1 ⎥
// ⎣ 1 1 0 1 1 ⎦ ⎢ w b ⎥ ⎣ 0 0 ⎦
// ⎣ v a ⎦
//
// Where each row (starting at the bottom) has more zeroes on the
// right than the previous row (the row below it).
//
// This already proves that the keys were linearly independent,
// because there is no row that has all zeroes in K.
// Note that even if there was a row in K with all zeroes, we might
// still be able to find a solution if also L has all zeroes in that row.
//
// The above is corresponding to the set of equations:
// ⎡ 1 1 0 ⎤
// Lᵀ = ⎣ 1 0 0 ⎦
// 1 1 0 0 0
// e+d = 1
// z+y = 1
//
// 0 1 1 0 0
// d+c = 1
// y+x = 0
//
// 1 1 0 1 1
// e+d +b+a = 0
// z+y +w+v = 0
//
// and from top to bottom we want to
//
// 1) set d to 1 (keep e at 0).
// set y to 1 (keep z at 0).
// 2) set c to 1 + d.
// set x to 0 + y.
// 3) set a to 0 + e + d (keep b at 0).
// set v to 0 + z + y (keep w at 0).
//
// It is easy to verify that this answer also holds in the original
// equation:
// 1 0 <---- 1 0 <-- column m.
// .-- row n v v | | .-- row n.
// v ⎡ 0 0 ⎤ v v v
// 2 ⎡ 0 1 1 1 1 ⎤ ⎢ 1 1 ⎥ ⎡ 1 0 ⎤ 2
// 1 ⎢ 1 0 1 1 1 ⎥ ⎢ 1 0 ⎥ = ⎢ 0 1 ⎥ 1
// 0 ⎣ 1 1 0 1 1 ⎦ ⎢ 0 0 ⎥ ⎣ 0 0 ⎦ 0
// ⎣ 1 1 ⎦
//
// That is, the bit in L at row n and column m is the parity of
// the bit-wise AND between the key at row n in K and column m of M.
//
// Finally we transpose this result to get the output variable MT:
//
// ⎡ 0 1 1 0 1 ⎤
// Mᵀ = ⎣ 0 1 0 0 1 ⎦
//
// Since a zero key always results in a zero in L, we can not use
// the value zero in L when one of the keys in zero. Instead we
// ignore the key and use different and non-zero values in L.
//
// For example, if we had the same keys as in the above example,
// but ALSO an all zeroes key:
//
// ⎡ 1 1 0 1 1 ⎤ <-- row 0 = key 1
// ⎢ 0 0 0 0 0 ⎥ key 2
// K = ⎢ 0 1 1 0 0 ⎥ key 3
// ⎣ 0 1 1 1 1 ⎦ key 4
//
// Then the zero key is removed and we use for L the matrix
//
// ⎡ 1 1 ⎤
// L = ⎢ 1 0 ⎥
// ⎣ 0 1 ⎦
//
// The algorithm to solve M from K' in row echelon form is, as you can see
// from the 1) 2) 3) steps above, done per whole row of M:
//
// First, we start with M being all zeroes:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 0 0 ⎥ 3
// ⎢ 0 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// We skip over row 4, leaving it all zeroes, because the first row of
// K' is 1 1 0 0 0
// 4 3 <-- start with row 3.
// ^-- the last 1.
// And that row is made equal to the first row of L: 1 1.
// The result after step 1) is therefore:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3 <-- last updated.
// ⎢ 0 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// The next row of K' is 0 1 1 0 0
// 4 3 2 <-- continue with row 2.
// ^-- the last 1.
// And that row is made equal to L's second row [ 0 1 ]
// XOR the current row of K' times M so far:
//
// ⎡ 0 0 ⎤
// ⎢ 1 1 ⎥
// [ 0 1 1 0 0 ] ⎢ 0 0 ⎥ = [ 1 1 ]
// ⎢ 0 0 ⎥
// ⎣ 0 0 ⎦
//
// [ 0 1 ] + [ 1 1 ] = [ 1 0 ]
//
// So that after step 2) M has become:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3
// ⎢ 1 0 ⎥ 2 <-- last updated.
// ⎢ 0 0 ⎥ 1
// ⎣ 0 0 ⎦ 0
//
// The final row of K' is 1 1 0 1 1
// 4 3 2 1 0 <-- continue with row 0.
// ^-- the last 1.
// The next row of L is [ 0 0 ] and
//
// ⎡ 0 0 ⎤
// ⎢ 1 1 ⎥
// [ 0 0 ] + [ 1 1 0 1 1 ] ⎢ 1 0 ⎥ = [ 1 1 ]
// ⎢ 0 0 ⎥
// ⎣ 0 0 ⎦
//
// So that after step 3) M has become:
//
// n=5 row
// ⎡ 0 0 ⎤ 4
// ⎢ 1 1 ⎥ 3
// ⎢ 1 0 ⎥ 2
// ⎢ 0 0 ⎥ 1
// ⎣ 1 1 ⎦ 0 <-- last updated.
//
相信我，这是我为一个函数写的最长评论:)。
原版POST:
随机倍数法
我尝试了与 samgak 相同的方法：我的散列函数只是 uint64_t 密钥与 uint64_t 乘数的乘积，然后我尝试了乘数的随机值，直到最少 high-bits 个结果不同。事实证明，这很容易需要 0.3 秒才能达到 9 位输出。
这里我使用了下面的函数来求出需要的高位数：
// Return the maximal right-shift that is possible on
// the values in `hashes` such that the results are still all different.
int max_shift(std::vector<uint32_t> hashes)
{
std::sort(hashes.begin(), hashes.end());
int sm = 0;
int sz = hashes.size();
for (int i = 1; i < sz; ++i)
{
uint32_t d = hashes[i - 1] ^ hashes[i];
int s = std::countl_zero(d);
if (s > sm)
sm = s;
}
return 31 - sm;
}
这里的hashes例如就是乘法结果的最高32位；较低的 32 位将被移出/忽略。
考虑到 100 个值，小于 128，理论上适合 7 位（尽管我从来没有用上述方法找到 8 位；当你意识到随机尝试的机会对应于有 100 个人和 256 个生日的生日问题；1 in 5807421181 chance 没有碰撞）而且我发现等待 0.3 秒，理论上要长得多，有点烦人——我开始考虑一种计算哈希函数的方法。
为了能够进行任何计算，我决定使用线性代数方法。
使用线性代数
想法是使用线性代数（矩阵，向量）。由于我们正在处理任意位，最合乎逻辑的做法是处理 。好的，这种从 LaTeX 到图像的外部转换不起作用，我将使用 UTF8：ℤ₂
让所有的输入键都用64维的列向量在ℤ₂上表示：ᵢ。
注意最多可以存在 64 个这样的线性无关向量。假设我们有 64 个这样的键。然后我们可以构造矩阵
K = [₀ ₁ … ᵢ … ₆₃]
并计算它的倒数（因为 ᵢ 是线性独立的）。让我们用 K⁻¹ 表示这个逆。
此外，注意我们需要6位来枚举64个输入键。现在令6×64矩阵L为所有6维列向量存在的矩阵：
⎡ 0 0 0 0 0 1 1 ⎤
⎢ 0 0 0 0 0 1 1 ⎥
L = ⎢ 0 0 0 0 0 ... 1 1 ⎥
⎢ 0 0 0 0 1 1 1 ⎥
⎢ 0 0 1 1 0 1 1 ⎥
⎣ 0 1 0 1 0 0 1 ⎦
设6×64矩阵M为
M = L K⁻¹
然后
M K = L K⁻¹ K = L
和left-multiplying任何带有M的输入键ᵢ都会给出一个唯一的6位列向量；又名 - 完美哈希。
线性相关键
这种方法的主要问题当然是输入键可能不是线性独立的，当超过 64 个键时肯定会出现这种情况。
为了检测 if/when 键不是线性独立的，我们可以在新键进入时简单地对矩阵 K 进行三角剖分。为了举例，假设我们有 vectors/keys 个4 位而不是 64 位。
考虑以下五个不同的输入键：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝1⎠ ⎝1⎠ ⎝0⎠ ⎝1⎠
然后我们从单位矩阵开始（主对角线上的所有元素和重置零），并放置第一个键，使顶部 1 与矩阵对角线上的 1 对齐：
⎡ 0 0 0 1 ⎤
K'= ⎢ 0 0 1 0 ⎥
⎢ 0 1 1 0 ⎥
⎣ 1 0 0 0 ⎦
* <-- used
因此，这个矩阵有一个逆矩阵，因为upper-left三角形全为零，主对角线全为1。
下一个键，V₁，同样可以as-is放在这个矩阵中：
⎡ 0 0 0 1 ⎤
K'= ⎢ 0 0 1 0 ⎥
⎢ 0 1 1 1 ⎥
⎣ 1 0 0 1 ⎦
* * <-- used
现在使用第四列，所以我们不能用它来输入 V2（顶部也有一个 1）。因此，我们首先从 V2 中减去第四列（请注意，对 ℤ2 的减法是加法模 2，也称为异或运算）。 V2 则变为：
⎛1⎞ ⎛1⎞ ⎛0⎞
⎜0⎟ - ⎜0⎟ =⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟
⎝1⎠ ⎝1⎠ ⎝0⎠
我们可以将它放在矩阵的第 2 列中（这不会改变它）。 V₃ 现在不能再放在第 2 列，因为它是“used”。
如果我们尝试使用相同的技巧，从 V₃ 中减去第 2 列，我们得到
⎛0⎞ ⎛0⎞ ⎛0⎞
⎜0⎟ - ⎜0⎟ =⎜0⎟
⎜1⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝0⎠ ⎝0⎠
全为零。这表明前四个键是线性相关的。 我们可以通过在底部用 1 扩展向量（以及所有其他带有零的向量）来缓解这种情况：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠ ⎝0⎠
如果我们用这些输入重复相同的事情，我们会得到完全相同的矩阵，但在左下角多了一个 1：
⎡ 0 0 0 0 1 ⎤
K'= ⎢ 0 0 0 1 0 ⎥
⎢ 0 0 1 1 1 ⎥
⎢ 0 1 0 0 1 ⎥
⎣ 1 0 0 0 0 ⎦
* * * * <-- used
V₄ 结果也是线性相关的：它的顶部有一个 1，因此减去最后一列，然后我们得到（现在）已经使用的第四列。因此我们必须添加另一行：
⎛0⎞ ⎛1⎞ ⎛1⎞ ⎛0⎞ ⎛1⎞
V₀=⎜1⎟, V₁=⎜0⎟, V₂=⎜0⎟, V₃=⎜0⎟, V₄=⎜1⎟
⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟
⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠
和
⎡ 0 0 0 0 0 1 ⎤
K'= ⎢ 0 0 0 0 1 0 ⎥
⎢ 0 0 0 1 1 1 ⎥
⎢ 0 0 1 0 0 1 ⎥
⎢ 0 1 0 0 0 0 ⎥
⎣ 1 0 0 0 0 0 ⎦
* * * * * <-- used
现在让我们按照上面的描述构造 K（只需将所有 V 放入其中）：
⎡ 0 1 1 . 0 1 ⎤
⎢ 1 0 0 . 0 1 ⎥
K = ⎢ 1 1 0 . 1 0 ⎥
⎢ 0 1 1 . 0 1 ⎥
⎢ 0 0 0 . 1 0 ⎥
⎣ 0 0 0 . 0 1 ⎦
我将第四列留空，因为即使（原始）密钥是 4 位，我们也只能找到三个线性独立的密钥。也就是说，如果密钥是 64 位，而我们只能找到 62 个线性无关的密钥，我们将留空 2 列。那就是……我们将用与之前的密钥线性独立的伪密钥填充它们；这将导致那些列的低位为零：
⎡ 0 1 1 . 0 1 ⎤
⎢ 1 0 0 . 0 1 ⎥
K = ⎢ 1 1 0 . 1 0 ⎥
⎢ 0 1 1 . 0 1 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
此外，缺少的线性无关键通常是K'中未使用的列，因此可以通过将对角线从右下角延伸到左上角来完成K:
⎡ 0 1 1 0 0 1 ⎤
⎢ 1 0 0 0 0 1 ⎥
K = ⎢ 1 1 0 0 1 0 ⎥
⎢ 0 1 1 1 0 1 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
因为现在所有的列都是线性无关的，所以这个矩阵有一个逆矩阵，在这种情况下就是
⎡ 0 1 0 0 0 1 ⎤
⎢ 0 1 1 0 1 1 ⎥
K⁻¹=⎢ 1 1 1 0 1 0 ⎥
⎢ 1 0 0 1 0 0 ⎥
⎢ 0 0 0 0 1 0 ⎥
⎣ 0 0 0 0 0 1 ⎦
最初我们有 5 个输入键，但即使有额外的伪键，我们也可以用 3 位来枚举它。但是，考虑到我们对伪密钥的结果并不真正感兴趣 - 因此我们使用以下 L:
⎡ 0 0 0 ? 0 1 ⎤
L = ⎢ 0 0 1 ? 1 0 ⎥
⎣ 0 1 0 ? 1 0 ⎦
您可以在第四列中填写任何内容。 如果填写下一个数字（5）：
⎡ 0 0 0 1 0 1 ⎤
L = ⎢ 0 0 1 0 1 0 ⎥
⎣ 0 1 0 1 1 0 ⎦
然后
⎡ 1 0 0 1 0 1 ⎤
M = L K⁻¹ = ⎢ 1 1 1 0 0 0 ⎥
⎣ 1 1 1 1 0 1 ⎦
用原始密钥（V₀、V₁、V₂、V₃ 和 V₄）构建 Kₒ：
⎡ 0 1 1 0 1 ⎤
Kₒ=⎢ 1 0 0 0 1 ⎥
⎢ 1 1 0 1 0 ⎥
⎣ 0 1 1 0 1 ⎦
并使用没有最后两列的 M，
⎡ 1 0 0 1 ⎤
M = ⎢ 1 1 1 0 ⎥
⎣ 1 1 1 1 ⎦
我们得到
⎡ 0 0 0 0 0 ⎤
M Kₒ = ⎢ 0 0 1 1 0 ⎥
⎣ 0 1 0 1 1 ⎦
显示与该矩阵 M 相乘不是完美的散列：最后一列与第二列相同。
确切的变化是显而易见的：如果我们使用了完整的矩阵（包括最后两列）和扩展键，那么只有最后一个键在最后一列中有一个 1，因此 XOR-ed矩阵的最后一列：
⮶what we get
1 1 0
0 XOR 0 = 0
0 1 1
⮴expected
因此，纠正输出的唯一方法是根据该列的前四位知道它属于 K 的哪一列（最后一列），这很像我们试图解决的原始问题开始。
第 2 部分
诀窍是将键分成 64 个或更少线性独立键的集合。这很容易，因为对于完全随机的 64 位值，平均前 62.18 个键将是线性独立的，这足够接近 64 是有效的。
然而，密钥应该很好地散列，例如，如果 64 位密钥是 uint64_t，值在 0 到 64 之间，只使用 6 位，那么你显然只能找到 6 个线性独立的一次钥匙，至少需要 64 / 6 = 11 套。
这会减慢查找速度，因为在将键与正确的矩阵相乘之前，您必须能够确定键属于哪个集合。
一种方法是对键进行排序并记住下一组中第一个键的值（第一个键线性依赖于上一组中的键）。
例如，假设我们有三组：
S₀={V₀,V₁,V₂}, S₁={V₃,V₄} and S₂={V₅,V₆,V₇,V₈}
因为V₃可以用S₀中的key表示（例如V₀ + V₂），而V₅可以表示为V₃ + V₄。
让我们试着想一个这样的例子。请记住，我们对键进行了排序，因此 V₀<V₁<V₂<V₃<V₄<V₅<V₆<V₇<V₈ 当表示为数字时。假设存储它们的无符号整数的最低有效位对应于向量的第 0 行，则可能的值可能是：
{ 0b00001, 0b00010, 0b00100 }, { 0b00101, 0b01000 }, { 0b01101, 0b01111, 0b11001, 0b11110 }
或
⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛0⎞ ⎛1⎞ ⎛1⎞
⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟ ⎜1⎟
V₀=⎜0⎟, V₁=⎜0⎟, V₂=⎜1⎟, V₃=⎜1⎟, V₄=⎜0⎟, V₅=⎜1⎟, V₆=⎜1⎟,V₇=⎜0⎟, V₈=⎜1⎟
⎜0⎟ ⎜1⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜0⎟ ⎜1⎟ ⎜0⎟ ⎜1⎟
⎝1⎠ ⎝0⎠ ⎝0⎠ ⎝1⎠ ⎝0⎠ ⎝1⎠ ⎝1⎠ ⎝1⎠ ⎝0⎠
所以 V₃=V₀+V₂ 和 V₅=V₃+V₄.
但我们可以做得更好！不需要对key进行排序，用<来指定set之间的边界。一种非常有效的方法是使用二叉树在每次使用一个特定位时找到正确的集合。
请注意，预计有 ~100 个键和大小为 ~62 的集合 - 我们预计只有两个集合！所以只有一个位可以打开。这个位可以通过反复试验找到。在上面的例子中我们可以创建以下两组线性无关的向量：
S₀={V₁,V₂,V₄,V₈} and S₁={V₀,V₃,V₅,V₆,V₇}
只需打开最低有效位即可。
一百个 64 位密钥的总查找代码将存在测试 1 位，确定使用六个 64 位值中的哪个 table，然后进行六次异或运算（可以是理论上并行完成；因此应该大约 3 个时钟周期）和同样的 6 个奇偶校验测试——我将其计为 6 个时钟周期（有关奇偶校验的更多信息，请参见
当我有工作代码时，我会post更新。