public interface IDictionary {

    /**
     * Помещает значение в ячейку с указанным ключем
     * @param key - ключ
     * @param value - значение
     * @return true - если помещение успешно, иначе - false
     */
    boolean put(String key, String value);

    /**
     * @param key - ключ
     * @return значение ассоциированное с указанным ключем
     */
    String get(String key);

    /**
     * Удаляет из структуры значение с указанным ключем
     * @param key - ключ
     * @return true - если удаление успешно, иначе - false
     */
    boolean remove(String key);

    /**
     * Проверяет структуру на пустоту
     * @return true - если в структуре нет значений, иначе false
     */
    boolean isEmpty();
}


import java.util.HashMap;
import java.util.Map;

public class Dictionary implements IDictionary {

    private Node root = new Node();

    private static class Node {
        Map<Character, Node> children = new HashMap<>();
        Node parent = null;
        String value = null;
    }

    @Override
    public boolean put(String key, String value) {
        try {
            Node currentNode = root;
            Node currentParent;

            for(char character : key.toCharArray()) {
                if (!currentNode.children.containsKey(character)) {
                    currentNode.children.put(character, new Node());
                }

                currentParent = currentNode;
                currentNode = currentNode.children.get(character);

                currentNode.parent = currentParent;
            }

            currentNode.value = value;

            return true;

        } catch (Exception e) {
            System.out.println("Добавление не удалось. Причина: " + e.getMessage());
            return false;
        }
    }

    @Override
    public String get(String key) {
        Node currentNode = root;

        for (char character : key.toCharArray()) {
            if (!currentNode.children.containsKey(character)) {
                return null;
            } else {
                currentNode = currentNode.children.get(character);
            }
        }

        return currentNode.value;
    }

    @Override
    public boolean remove(String key) {
        try {

            Node currentNode = root;

            for (char character : key.toCharArray()) {
                if (!currentNode.children.containsKey(character)) {
                    return false;
                } else {
                    currentNode = currentNode.children.get(character);
                }
            }

            currentNode.value = null;

            while (currentNode.parent != null && currentNode.children.size() == 0) {
                Node currentParent = currentNode.parent;
                if (currentParent.children.size() == 1 && currentNode.value == null) {
                    currentParent.children.clear();
                    currentNode = currentParent;
                }
                else {
                    break;
                }
            }

            return true;

        } catch (Exception e) {
            System.out.println("Удаление не удалось. Причина: " + e.getMessage());
            return false;
        }
    }

    @Override
    public boolean isEmpty() {
        return root.children.isEmpty();
    }
}


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

public class Main {

    private static final int NUMBER_OF_ELEMENTS = 1000000;

    public static void main(String[] args) {

        Dictionary dictionary = new Dictionary();

        HashMap<String, String> map = new HashMap<>();

        List<String> keys = new ArrayList<>();
        List<String> values = new ArrayList<>();

        for (int i = 0; i < NUMBER_OF_ELEMENTS; i++) {
            keys.add(getRandomString(10));
            values.add(getRandomString(50));
        }

        long start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            dictionary.put(keys.get(i), values.get(i));
        }
        long end = System.currentTimeMillis();

        System.out.println("Время добавления в Dictionary: " + (end - start) + " мсекунд.");

        start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            map.put(keys.get(i), values.get(i));
        }
        end = System.currentTimeMillis();

        System.out.println("Время добавления в HashMap: " + (end - start) + " мсекунд.");

        start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            dictionary.get(keys.get(i));
        }
        end = System.currentTimeMillis();

        System.out.println("Время взятия элемента в Dictionary: " + (end - start) + " мсекунд.");

        start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            map.get(keys.get(i));
        }
        end = System.currentTimeMillis();

        System.out.println("Время взятия элемента в HashMap: " + (end - start) + " мсекунд.");

        start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            dictionary.remove(keys.get(i));
        }
        end = System.currentTimeMillis();

        System.out.println("Время удаления элемента в Dictionary: " + (end - start) + " мсекунд.");

        start = System.currentTimeMillis();
        for (int i = 0; i < keys.size(); i++) {
            map.remove(keys.get(i));
        }
        end = System.currentTimeMillis();

        System.out.println("Время удаления элемента в HashMap: " + (end - start) + " мсекунд.");

    }

    private static String getRandomString(int length) {
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
        StringBuilder sb = new StringBuilder();
        Random rnd = new Random();

        while(sb.length() < length)
        {
            int index = (int) (rnd.nextFloat() * chars.length());
            sb.append(chars.charAt(index));
        }

        return sb.toString();
    }
}