对于类似堆栈的对象是否有可推送/可弹出的散列函数？
我知道滚动哈希函数类似于有界队列上的散列。堆栈有类似的东西吗？
我的用例是，我正在对可能的程序跟踪进行深度第一次搜索(通过循环展开，这样这些堆栈就可以获得biiiiig)，并且我需要通过这些跟踪来识别分支。我不想存储一堆深度1000的堆栈，而是要散列它们，这样我就可以按int索引。但是，如果我有深度10000+，那么这个哈希将是昂贵的，因此我希望跟踪我的最后一个散列，这样当我从堆栈中推送/弹出时，我可以分别散列/解散新/旧项。
特别是，我正在寻找一个具有属性的散列h(Object, Hash)，该散列u(Object, Hash)具有要对对象x进行散列处理的属性：
u(x, h(x, baseHash)) = baseHash此外，这个散列不应该是可交换的，因为顺序很重要。
其中一个想法是GL(2, F(2^k))上的矩阵乘法，也许是使用Cayley图？例如，在A_0中取两个可逆矩阵B_0和B_1中的可逆矩阵B_0和B_1，然后计算对象x的哈希，首先用位b31b30...b1b0计算一些整数哈希，然后再计算。
H(x) = A_b31 . A_b30 . ... . A_b1 . A_b0这有一个相反的
U(x) = B_b0 . B_b1 . ... . B_b30 . B_31.因此，h(x, baseHash) = H(x) . baseHash和u(x, baseHash) = U(x) . baseHash，所以
u(x, h(x, base)) = U(x) . H(x) . base = base,如你所愿。
这似乎比所需的更昂贵，但是对于2x2矩阵来说，它应该不会太糟糕吗？
回答 1
Stack Overflow用户
发布于 2018-04-24 03:02:02
大多数增量哈希函数可以通过两种操作来实现：
( 1)将以前的散列混合在一起的可逆扩散函数。为此选择了可逆函数，这样它们就不会丢失信息。否则，散列将倾向于一些值；以及
2)将新数据混合到散列中的可逆混合函数。为此使用了可逆函数，以便输入的每个部分对最终的哈希值都有同等的影响。
由于这两种情况都是可逆的，因此很容易撤消增量散列的最后一部分，并从以前的值中“弹出”。
例如，使用中最常见的简单哈希函数是多项式哈希函数。若要使用新输入“x”更新先前的散列值，请计算：
h‘= h*A +x模M
乘法是扩散函数。为了使这是可逆的，A必须有一个乘法逆模M -通常选择M作为素数，或者M是2E 211的幂，而E 112AE 213是奇数。
由于乘法逆存在，只要您仍然可以访问它，就很容易从散列中弹出最后一个值：
h = (h‘- x)*(1/A)模M
您可以使用扩展的欧几里德算法来寻找A：algorithm的逆
大多数其他常见的非加密散列，如CRCs、FNV、murmurHash等，也同样容易将值弹出。
其中一些散列在增量工作之后有一个最终的扩散步骤，但该步骤也几乎总是可逆的，以确保散列可以接受任何值，因此您可以撤销它以返回增量部分。
扩散运算通常是由本原可逆运算序列进行的。若要撤消它们，您将按反向顺序撤消每个操作。您将看到的一些常见类型包括：
- 循环移位
- 可逆乘法(如上)
- X=x XOR (x >>移位)
- Feistel回合(见cipher)
混合操作通常是+或异或。
https://stackoverflow.com/questions/49992455
复制相似问题
腾讯云开发者
