应用哈希对字符串问题进行高效处理

今天药忘吃喽~ 2022-07-03 16:18 151阅读 0赞

往往我们需要牺牲一定的空间为代码来优化时间性能，尽可能的缩短响应时间，也就是我们经常提到的“以空间换时间”。哈希表（散列表）是一种非常高效的查找数据结构，在原理上也与其他的查找不尽相同，它回避了关键字之间反复比较的繁琐，而是直接一步到位查找结果。当然，这也带来了记录之间没有任何关联的弊端。应该说，散列表对于那些查找性能要求高，记录之间关系无要求的数据有非常好的适用性。注意对散列函数的选择和处理冲突的方法。 Hash表是使用 O(1)时间进行数据的插入、删除和查找，但是 hash 表不保证表中数据的有序性，这样在 hash 表中查找最大数据或者最小数据的时间是 O(N) 。

对于一些字符串问题，如果是大数据的话，例如对于一个海量的文件中存储着不同的URL，用最小的时间复杂度去除重复的URL，我们可以使用现有的容器例如HashMap来解决，但是对于小型的字符串处理问题，使用容器未免有些大材小用，我们可以使用数组来实现一个简易的Hash表。

# 在字符串中找出第一个只出现一次的字符 #

我们可以将数组视为容器，把每一个字符映射成一个数字，就是哈希表的键值（Key）是字符，而值（Value）是该字符出现的次数，时间复杂度是O(n)，分为两步解决如上问题，先是扫描字符串，将每个字符的出现次数记录，之后是再次扫描，找到第一个次数是1的字符，时间复杂度也是O(n)，因此总复杂度是O(n)：

public int FirstNotRepeatingChar(String str) {
                if(str==null) return -1;
                int hashsize = 256;
                int[] hashtable = new int[hashsize];
                //字符串的结束符'\0'
                for(int i=0;i<str.length();i++){
                    hashtable[str.charAt(i)]++;
                }
                //搜索
                for (int i=0;i<str.length();i++){
                    if (hashtable[str.charAt(i)]==1){
                        return i;
                    }
                }
                return -1;
            }

# 不改变出现顺序的情况下删除重复字符 #

可以建立布尔类型的数组，出现过即设置为true，没有出现过即设置为false。

public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()){
                String str = sc.nextLine();
                int len = str.length();
                boolean[] rs = new boolean[256];
                for (int i=0;i<256;i++){
                    rs[i] = false;
                }
                StringBuilder sb = new StringBuilder();
                for (int i=0;i<len;i++){
                    if(rs[str.charAt(i)] == false){
                        rs[str.charAt(i)] = true;
                        sb.append(str.charAt(i));
                    }
                }
                System.out.println(sb.toString());
            }
        }

使用容器的实现，可以用于大型数据：

（1）删除重复数据

public static void main(String[] args){
            //TreeSet对元素排序，默认升序，LinkedHashSet 保持元素添加顺序，HashSet的元素存放顺序和添加进去时候的顺序没有任何关系
            LinkedHashSet<Character> tr = new LinkedHashSet<>();
            String str = "abaafmkalbffmm";
            System.out.println("处理前"+str);
            char[] arr = str.toCharArray();
            for (int i=0;i<arr.length;i++){
                tr.add(arr[i]);
            }
            StringBuffer rs = new StringBuffer();
            Iterator iter = tr.iterator();
            while (iter.hasNext()){
                rs.append(iter.next());
            }
    
            System.out.println("处理后："+rs.toString());
        }

（2）统计出现次数

public class Demo {
        //统计一个字符串中相应字符出现的次数
        public static void main(String[] args) {
            //
            String s = "aagfagdlkerjgavpofjmvglk我是你的";
            //调用自定义方法来 统计相应字符出现的次数
            method(s);
    
        }
    
        private static void method(String s) {
            //定义 一个容器
            TreeMap<Character, Integer> tm = new TreeMap<Character, Integer>();
            //将这TreeMap中的key全部取出来，然后储存到set集合中去
            Set<Character> st = tm.keySet();
            //将所需要统计的字符串转换成一个字符数组
            char[] c = s.toCharArray();
            //通过for循环逐一统计每个字符出现的次数
            for (int x = 0; x < c.length; x++) {
                if (!st.contains(c[x])) {
                    tm.put(c[x], 1);
                } else {
                    tm.put(c[x], tm.get(c[x]) + 1);
                }
            }
            //调用自定义方法在控制台上输出统计信息
            printMapDemo(tm);
        }
    
        private static void printMapDemo(TreeMap<Character, Integer> tm) {
            // TODO Auto-generated method stub
    
            Set<Character> st = tm.keySet();
            Iterator<Character> ti = st.iterator();
            for (; ti.hasNext(); ) {
                char key = ti.next();
                System.out.println(key + "(" + tm.get(key) + ")");
            }
        }
    }

# 判断是否是变位词 #

变位词：如果两个单词中出现的字母相同，并且每个字母的出现次数也相同，则两个单词为变位词。可以在扫描第一个字符串时用数组记录每个字符的出现次数，扫描第二个字符串时，对应字符次数减1，看数组最终是否元素都为0.

public class DemoAnagram {
        public static boolean isAnagram(String str1,String str2){
            int len1 = str1.length();
            int len2 = str2.length();
            if (len1!=len2){
                return false;
            }
            int[] rs = new int[256];
            for (int i=0;i<len1;i++){
                rs[str1.charAt(i)]++;
            }
            for (int i=0;i<len2;i++){
                rs[str2.charAt(i)]--;
            }
            for (int i=0;i<256;i++){
                if (rs[i]!=0){
                    return false;
                }
            }
            return true;
        }
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()){
                String str1 = sc.nextLine();
                String str2 = sc.nextLine();
                boolean result = isAnagram(str1,str2);
                System.out.println(result);
            }
        }
    }

# 从一个字符串中删除另一个字符串中出现过的字符 #

例如字符串1是“We are students”，第二个字符串是“aeiou”，删除在2中出现过的字符的结果是“W r Stdnts  
”。可以用一个数组实现的哈希表来存储第二个字符串中的字符，array\[str2.charAt\[i\]\]为1，再从头扫描第一个字符串，array\[str1.charAt\[i\]\]为1则在2中出现，删除即可。实现方式同理，在此不再赘述。

通过基于数组创建一个简单的哈希表，可以用很小的空间消耗换来时间效率的提升。