Java 与数据结构（9）：字典树

向右看齐 2024-03-22 19:16 131阅读 0赞

--------------------

Java面试题  
面试准备、常见面试题、面试经验、面试总结  
链接：[Java面试资料，面试准备、面试题，面试真题][Java]

--------------------

## 一、字典树 ##

字典树（Trie树）是一种树形数据结构，用于高效地存储和查找字符串集合。字典树的每个节点包含一个字符和指向其子节点的指针。从根节点到叶子节点的路径表示一个字符串。

字典树的主要特点是：

1.  根节点不包含字符，除根节点外的每个节点都包含一个字符。
2.  从根节点到任意一个节点的路径表示一个字符串。
3.  每个节点的子节点包含的字符不相同。
4.  字典树通常用于字符串的查找和前缀匹配等操作。

字典树的常见操作包括插入字符串、查询字符串和前缀匹配等。其中，插入字符串和查询字符串的时间复杂度为O(m)，其中m为字符串的长度，前缀匹配的时间复杂度为O(k)，其中k为匹配的字符串的长度。

字典树的优点是能够高效地存储和查找字符串集合，特别是在大量字符串的情况下。但是，字典树的缺点是空间消耗较大，且在某些情况下可能会出现性能问题。

## 二、Java 示例 ##

下面是一个Java实现字典树的示例：

class TrieNode {
        
        private TrieNode[] children;
        private boolean isEndOfWord;
    
        public TrieNode() {
        
            children = new TrieNode[26];
            isEndOfWord = false;
        }
    
        public void insert(String word) {
        
            TrieNode current = this;
            for (char c : word.toCharArray()) {
        
                int index = c - 'a';
                if (current.children[index] == null) {
        
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            current.isEndOfWord = true;
        }
    
        public boolean search(String word) {
        
            TrieNode current = this;
            for (char c : word.toCharArray()) {
        
                int index = c - 'a';
                if (current.children[index] == null) {
        
                    return false;
                }
                current = current.children[index];
            }
            return current.isEndOfWord;
        }
    
        public boolean startsWith(String prefix) {
        
            TrieNode current = this;
            for (char c : prefix.toCharArray()) {
        
                int index = c - 'a';
                if (current.children[index] == null) {
        
                    return false;
                }
                current = current.children[index];
            }
            return true;
        }
    }
    
    public class Trie {
        
        private TrieNode root;
    
        public Trie() {
        
            root = new TrieNode();
        }
    
        public void insert(String word) {
        
            root.insert(word);
        }
    
        public boolean search(String word) {
        
            return root.search(word);
        }
    
        public boolean startsWith(String prefix) {
        
            return root.startsWith(prefix);
        }
    }

使用示例：

Trie trie = new Trie();
    trie.insert("apple");
    System.out.println(trie.search("apple")); // true
    System.out.println(trie.search("app")); // false
    System.out.println(trie.startsWith("app")); // true
    trie.insert("app");
    System.out.println(trie.search("app")); // true

## 三、字典树在spring 中的作用 ##

在Spring框架中，字典树的应用主要体现在字符串匹配和路由等方面。Spring Cloud Gateway和Spring Security等模块都使用了字典树来实现路由和权限控制等功能。

在Spring Cloud Gateway中，路由规则是通过配置文件或者代码进行定义的，每个路由规则都包含一个路径匹配模式和一个目标URI。为了高效地匹配请求的路径和路由规则，Spring Cloud Gateway使用了字典树来存储路由规则，每个节点包含一个字符和指向其子节点的指针。从根节点到叶子节点的路径表示一个路由规则，匹配请求的路径时，只需要从根节点开始，依次比较路径中的每个字符，直到匹配到叶子节点为止。

在Spring Security中，权限控制规则是通过配置文件或者代码进行定义的，每个权限控制规则都包含一个路径匹配模式和一个访问权限。为了高效地匹配请求的路径和权限控制规则，Spring Security使用了字典树来存储权限控制规则，每个节点包含一个字符和指向其子节点的指针。从根节点到叶子节点的路径表示一个权限控制规则，匹配请求的路径时，只需要从根节点开始，依次比较路径中的每个字符，直到匹配到叶子节点为止。

通过使用字典树，Spring框架能够高效地实现字符串匹配和路由等功能，提高应用程序的性能和可扩展性。

[Java]: https://download.csdn.net/download/qq_42449106/87797076