是否有一种散列技术可以 return 对字符串的反向进行与对原始字符串相同的散列？

Question

例如，对于这两个字符串，此哈希函数应该return相同的哈希值。

字符串 a = "hello" 字符串 b = "olleh"

这背后的动机是找到句子中重复的单词对。

Answer 1

构造 hash(min(string, reverse(string))) 应该可以解决问题。这是一个名为 canonicalization.

的技术实例

Answer 2

通常我们可以这样生成hash函数：

int hashCode(){
     int h = 0;
     if (h == 0 && value.length() > 0) {
        char val[] = value.toCharArray();

        for (int i = 0; i < value.length(); i++) {
             h = 31 * h + val[i];
        }

     }
     return h;
}

所以，我们可以稍微修改一下，得到我们的哈希函数

 int hashCode(){
     int h = 0;
     if (h == 0 && value.length() > 0) {
        char val[] = value.toCharArray();
        int mid = value.length()/2;
        int rate = 1;
        if(value.length() % 2 == 0){
           mid = (value.length()*2 - 1)/2;
           rate = 2;
        }
        for (int i = 0; i < value.length(); i++) {
            h +=  val[i]*Math.pow(31, Math.abs(rate*i - mid));
        }

     }
     return h;
}

因此，我们不再以第一个字符为起点计算哈希码，而是将计算哈希码的起点移至中间字符。

对于偶数长度的字符串，我们将所有索引乘以2，因此我们可以获得中间位置的整数值。

的哈希码

hello: 213202
olleh: 213202
olelh: 213412
hlelo: 213412

更新:

我们可以观察到，对于上述方法，围绕中点对称的两个位置将被视为相等，因此，例如 "hell" 和 "lelh" 将具有相同的哈希码。

~~为避免这种情况，一种方法是将字符串的每一半视为两个单独的字符串，并组合它们的哈希码：~~

public int hashCode() { long h = 0; if (h == 0 && value.length() > 0) { char val[] = value.toCharArray(); int mid = value.length() / 2; int rate = 1; if (value.length() % 2 == 0) { mid = (2*value.length() - 1)/2; rate = 2; } long midPart = 0; long lowerHalf = 0; long upperHalf = 0; if(value.length() % 2 != 0){ midPart = val[value.length()/2]; } for(int i = 0; i < value.length()/2; i++){ lowerHalf += Math.pow(31, mid - rate*i)*val[i]; } for(int i = (value.length() + 1)/2; i < value.length(); i++){ upperHalf += Math.pow(31,rate*i - mid)*val[i]; } long max = Math.max(lowerHalf, upperHalf); long min = Math.min(lowerHalf, upperHalf); h = max*(long)Math.pow(31, (value.length() + 1)/2) + min + midPart; } return (int)h; }

是否有一种散列技术可以 return 对字符串的反向进行与对原始字符串相同的散列？

Is there a hashing technique such that it would return the same hash for the reverse of a string as it would for the original string?

string

algorithm

hash