Hash字符串匹配

╰+哭是因爲堅強的太久メ 2021-09-23 01:14 561阅读 0赞

hash字符串匹配即把固定长度的字符串转化为hash值进行匹配，这种匹配方式在大量数据的情况下是有误差的，大约万分之四五左右，这是因为hash值是通过字符和公式计算出来的，不同的字符串有可能根据我们的计算公式算出相同的hash值，这就会导致匹配的误差。

**一、普通Hash匹配**

普通hash匹配即每次截取模式串长度的字串计算hash值，然后原模式串的hash值进行比较，两者相同则认为匹配成功。

普通hash匹配会频繁计算原串的字串的hash值，如果原串长度为n，模式串长度为m，则原串需要计算hash值的字串数量为n-m，这n-m个hash值计算后再跟模式串hash值进行比较。

**计算hash值的方法**

static final int seed = 31;
    static long hash(String s) {
            long hash = 0L;
            for(int i=0;i<s.length();i++) {
                hash = hash * seed + s.charAt(i);//一般的线性计算方法
            }
            return hash%Long.MAX_VALUE;//防止溢出long
    }

**匹配方法**

static void matches(String org,String sub) {
            long hash_sub = hash(sub);
            int sub_len = sub.length();
            for(int i=0;i<org.length()-sub_len;i++)  {
                long hash_org =  hash(org.substring(i,i+sub_len));
                if(hash_org == hash_sub) {
                    System.out.println("match:"+i);
                }
            }
        }

**测试**

matches("acabababac","aba");

**二、滚动hash匹配**

滚动hash匹配是普通hash匹配的优化版，优化之处在于不再频繁计算原串子串的hash值，而是通过前一个子串的hash值得到后一个子串的hash值。

**代码**

/**
         * 第k位到第k+n位字串的hash值,是原字符串每个子串hash值的预处理
         * @param s 原字符串
         * @param n 子串长度
         * @return long数组
         */
        static long[] hash(final String s,final int  n) {
            long[] res = new long[s.length()-n+1];
            
            //前m个字符的hash值
            res[0]= hash(s.substring(0, n));
            for(int i=n;i<s.length();i++) {
                char newChar = s.charAt(i);//n
                char oldChar = s.charAt(i-n);//i==n  -> i-n=0
                //当i=n时
                //res[i-n]是long数组的首元素,值为原串前n个字符的hash值
                //v值为原串1~n+1个字符的hash值,这个值等于 第一个子串的hash值*seed+新字符-第一个子串的首字符,最后为了防止数值过大对long最大值取模,这个过程可以手动推导出来
                //可以借助下图来理解这个过程       
                long v = (res[i-n]*seed+newChar  -(long)Math.pow(seed,  n)*oldChar)%Long.MAX_VALUE;
                res[i-n+1] = v;
            }                   
            return res;
        }
    
        //与之前求hash值的方法相同
        static final int seed = 31;
        static long hash(String s) {
            int hash = 0;
            for(int i=0;i<s.length();i++) {
                hash = hash * seed + s.charAt(i);
            }
            return hash%Long.MAX_VALUE;
        }

**滚动hash计算的过程**

![20190520191708179.jpeg][]

**详细的计算和推理过程**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70][]**

**最后一步，与原串进行比较**

因为求long数组是对原串的hash值的预处理，求出long数组后直接与模式串的hash值比较即可，有多少值相同的就说明模式串与原串匹配成功多少次。

[20190520191708179.jpeg]: /images/20210920/75d97c157e1f4f7fb8b8e900c011afc2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzk0Mg_size_16_color_FFFFFF_t_70]: /images/20210920/c69407195e6240e4bc150ff3cd2529cc.png