DFA算法过滤敏感字如何删除敏感字

• 1. DFA算法简介
• 2. 需求来源
• 3. 算法原理
• 4. 代码实现

关于DFA算法的相关介绍，网上的文章有很多。不再赘述。这里提供两个传送门
参考一: java实现敏感词过滤（DFA算法）.
参考二: 敏感词过滤的算法原理之DFA算法.

首先敏感词库肯定不是一层不变的。需要经常的维护。词库维护后，必然要更新词库对应的hashmap。
我的第一想法是，既然更新，那就重新生成就好了。如果词库set和hashmap比较大的话，hashmap做了缓存，那么为了避免频繁的生成hashmap，可以为词库set和hashmap加上一个版本号，当需要使用hashmap时，验证二者的版本是否一致，如果不一致，重新生成hashmap。
但是，有人就觉的，重新生成，资源消耗也挺验证。还是直接同步删除的好。当set里删掉一个词的时候，就同步从hashmap里也把这个词删掉。
这时候问题来了，如何删除？在我搜索到的文章里都没有提到。所以只能自己写了。

在DFA中hashmap的存储的是一棵树，每个敏感词是这棵树上的一条路径，需要注意的是，这个路径不一定会到达树枝的最底层。所以我们删除一个敏感词，就是把这一条路径删掉。
如果对应的节点是独立节点，则直接把节点从hashmap里删除
否则，验证一下节点的isEnd是否为1，把1更新为0即可
流程图如下

import java.util.*;

public class MapTest {

    private static HashMap sensitiveWordMap;

    public static void main(String[] args) {

        Set words = new HashSet<>();
        words.add("日本鬼子");
        words.add("日本人");
        words.add("张三");
        words.add("张三丰");

        addSensitiveWordToHashMap(words);
        System.out.println("查看敏感词库数据:" + sensitiveWordMap);
        removeSensitiveWordFromHashMap(sensitiveWordMap,"张三");
        System.out.println("删除‘张三’:" + sensitiveWordMap);
        removeSensitiveWordFromHashMap(sensitiveWordMap,"张三丰");
        System.out.println("删除‘张三丰’:" + sensitiveWordMap);
    }

    private static void addSensitiveWordToHashMap(Set keyWordSet) {
        // 初始化HashMap对象并控制容器的大小
        sensitiveWordMap = new HashMap(keyWordSet.size());
        // 敏感词
        String key = null;
        // 用来按照相应的格式保存敏感词库数据
        Map nowMap = null;
        // 用来辅助构建敏感词库
        Map newWorMap = null;
        // 使用一个迭代器来循环敏感词集合
        Iterator iterator = keyWordSet.iterator();
        while (iterator.hasNext()) {
            key = iterator.next();
            // 等于敏感词库，HashMap对象在内存中占用的是同一个地址，所以此nowMap对象的变化，sensitiveWordMap对象也会跟着改变
            nowMap = sensitiveWordMap;
            for (int i = 0; i < key.length(); i++) {
                // 截取敏感词当中的字，在敏感词库中字为HashMap对象的Key键值
                char keyChar = key.charAt(i);

                // 判断这个字是否存在于敏感词库中
                Object wordMap = nowMap.get(keyChar);
                if (wordMap != null) {
                    nowMap = (Map) wordMap;
                } else {
                    newWorMap = new HashMap();
                    newWorMap.put("isEnd", "0");
                    nowMap.put(keyChar, newWorMap);
                    nowMap = newWorMap;
                }

                // 如果该字是当前敏感词的最后一个字，则标识为结尾字
                if (i == key.length() - 1) {
                    nowMap.put("isEnd", "1");
                }
                //System.out.println("封装敏感词库过程：" + sensitiveWordMap);
            }
           
        }
    }

    private static void removeSensitiveWordFromHashMap(Map map, String word) {

        // 截取敏感词当中的字，在敏感词库中字为HashMap对象的Key键值
        char keyChar = word.charAt(0);

        // 判断这个字是否存在于敏感词库中
        Map wordMap = (Map) map.get(keyChar);
        if (wordMap == null) {
            return;// 不存在，直接返回
        }

        if (word.length() == 1) {// 最后一个字符
            if (wordMap.size() == 1) {// 只有isEnd节点
                map.remove(keyChar);
            } else {
                if ("1".equals(wordMap.get("isEnd")))
                    wordMap.replace("isEnd", "1", "0");
            }
            return;
        }
        String newword = word.substring(1);
        removeSensitiveWordFromHashMap(wordMap, newword);
        if (wordMap.size() == 1) {// 只有isEnd节点
            map.remove(keyChar);
        }
    }

}