Пример блокировки чтения/записи. Потокобезопасное префиксное дерево (threadsafe trie)

Рассмотрим применение блокировки чтения/записи. Реализуем потокобезопасное префиксное дерево. Блокировки чтения/записи рассматриваются в данных постах:
Блокировка чтения/записи. Часть 1.
Блокировка чтения/записи. Часть 2
Блокировка чтения/записи. Часть 3
Блокировка чтения/записи. Часть 4
Блокировка чтения/записи. Часть 5
Блокировка чтения/записи. Часть 6
Префиксное дерево рассматривается в этом посте:
Префиксное дерево (trie)

Вот код потокобезопасного префиксного дерева:

import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.ReadWriteLock;
 
public class ThreadsafeTrie {
    ReadWriteLock rwlLock = new ReentrantReadWriteLock();
 
    static class TrieNode {
        Map<Character, TrieNode> children = new TreeMap<Character, TrieNode>();
        boolean leaf;
    }
 
    TrieNode root = new TrieNode();
 
    public void put(String s) {
        TrieNode v = root;
 
        rwlLock.writeLock().lock();
        {
            for (char ch : s.toLowerCase().toCharArray()) {
                if (!v.children.containsKey(ch)) {
                    v.children.put(ch, new TrieNode());
                }
                v = v.children.get(ch);
            }
            v.leaf = true;
        }
        rwlLock.writeLock().unlock();
    }
 
    public boolean find(String s) {
        TrieNode v = root;
        boolean result = true;
 
        rwlLock.readLock().lock();
        {
            for (char ch : s.toLowerCase().toCharArray()) {
                if (!v.children.containsKey(ch)) {
                    result = false;
                    break;
                } else {
                    v = v.children.get(ch);
                }
            }
        }
        rwlLock.readLock().unlock();
        return result;
    }
 
    static Map<Integer,String> levelSpacesMap = new ConcurrentHashMap<Integer,String>();
 
    static String getSpace(int level) {
        String result = levelSpacesMap.get(level);        
        if (result == null) {
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<level; i++) {
                sb.append(" ");
            }
            result = sb.toString();
            levelSpacesMap.put(level,result);
        }
        return result;
    }
 
    public void printSorted() {
        rwlLock.readLock().lock();
        {
            printSorted2(root,0);
        }
        rwlLock.readLock().unlock();
    }
 
    private void printSorted2(TrieNode node, int level) {
        for (Character ch : node.children.keySet()) {
            System.out.println(getSpace(level)+ch);
            printSorted2(node.children.get(ch), level+1);
        }
        if (node.leaf) {
            System.out.println();
        }
    }    
 
    // Usage example
    public static void main(String[] args) {
        ThreadsafeTrie trie = new ThreadsafeTrie();
        trie.put("hello");        
        trie.put("house");
        trie.put("hell");
        trie.put("world");
        System.out.println(trie.find("hello"));
        trie.printSorted();
    }
}

Здесь мы используем ReadWriteLock из пакета java.util.concurrent.locks. Рассмотрим операции над деревом.

Операция put. Тут происходит изменение данных, поэтому нам здесь нужно ставить блокировку на запись.
Операции find, printSorted. Здесь происходит лишь чтение данных, поэтому нам здесь достаточно ставить блокировку на чтение.

Использование блокировки чтения/записи делает работу класса более быстрой, чем если бы мы поставили перед каждым методом атрибут synchronized, и таким бы образом блокировали все операции (и чтения, и записи), давая в каждый момент времени выполняться лишь одному потоку.

Префиксное дерево (trie)

Префиксное дерево (trie) - структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. См. статьи в Wikipedia: trie, префиксное дерево.

Префиксное дерево используется для множества приложений: вместо других структур данных (например, хеш-таблиц), представление словарей, сортировка, полнотекстовый поиск, битовые и сжатые деревья. Алгоритм Ахо-Корасик (используется для поиска подстроки в строке) строит префиксное дерево в процессе своей работы.

Реализация префиксного дерева на Java:

import java.util.*;
 
public class Trie {
    static class TrieNode {
        Map<Character, TrieNode> children = new TreeMap<Character, TrieNode>();
        boolean leaf;
    }
 
    TrieNode root = new TrieNode();
 
    public void put(String s) {
        TrieNode v = root;
        for (char ch : s.toLowerCase().toCharArray()) {
            if (!v.children.containsKey(ch)) {
                v.children.put(ch, new TrieNode());
            }
            v = v.children.get(ch);
        }
        v.leaf = true;
    }
 
    public boolean find(String s) {
        TrieNode v = root;
        for (char ch : s.toLowerCase().toCharArray()) {
            if (!v.children.containsKey(ch)) {
                return false;
            } else {
                v = v.children.get(ch);
            }
        }
        return true;
    }
 
    static Map<Integer,String> levelSpacesMap = new HashMap<Integer,String>();
 
    static String getSpace(int level) {
        String result = levelSpacesMap.get(level);        
        if (result == null) {
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<level; i++) {
                sb.append(" ");
            }
            result = sb.toString();
            levelSpacesMap.put(level,result);
        }
        return result;
    }
 
    public static void printSorted(TrieNode node) {
        printSorted2(node,0);        
    }
 
    private static void printSorted2(TrieNode node, int level) {
        for (Character ch : node.children.keySet()) {
            System.out.println(getSpace(level)+ch);
            printSorted2(node.children.get(ch), level+1);
        }
        if (node.leaf) {
            System.out.println();
        }
    }    
 
    // Usage example
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.put("hello");        
        trie.put("house");
        trie.put("hell");
        trie.put("world");
        System.out.println(trie.find("hello"));
        printSorted(trie.root);
    }
}