Словарь - это абстрактный тип данных, который связывает ключи со значениями. Его ещё называют ассоциативный массив, карта, таблица символов, коллекция. Будет две статьи на эту тему, где мы покажем шесть картинок / способов реализации словаря, которые отличаются друг от друга по времени работы и по требованию к памяти.

Первая статья:

1. Линейный массив

2. Односвязный список

3. Отсортированный массив

Вторая статья:

4. Двоичное дерево поиска

5. Хэш-таблица

6. Префиксное дерево

Дом для кота, Интерфейс для словаря

Начнём созидание словаря с формулировки методов для работы с ним. Минимальный набор таких методов: put - добавить, get - получить.

По хорошему, мы должны создать обобщённый интерфейс с возможностью указать любой тип данных как для ключа, так и для значения. Однако, в рамках этой работы мы будем для удобства использовать string для ключей, int для значений. Ещё в словаре могут быть методы для удаления ключей, для итерации по всем записям, получение количества элементов и много других важных и приятных мелочей, которые мы опустим.

Пример кода на языке Java

interface IStorage
{
    Integer get(String key);
    void put(String key, Integer value);
}

public class Main 
{
    public static void main(String args[])
    {
        Main test = new Main();
        test.runMapExample(new ArrayStorage());
    }
    
    void runMapExample(IStorage map)
    {
        map.put("cat", 30);
        map.put("fox", 50);
        map.put("art", 10);
        map.put("owl", 80);
        map.put("box", 20);
        map.put("dog", 40);
        System.out.println(map.get("art"));
        System.out.println(map.get("box"));
        System.out.println(map.get("cat"));
        System.out.println(map.get("dog"));
        System.out.println(map.get("fox"));
        System.out.println(map.get("owl"));
    }
}

Картинка первая. Линейный массив.

Самый простой способ для хранения пар «ключ, значение» - это создание класса или структуры Node (узел) и декларация линейного массива сих пар.

Для поиска узла по ключу необходимо просканировать весь массив от начала до конца и в каждом узле проверять, не совпало ли значение. Если совпало - вернуть найденное значение, если сканирование завершилось, а значение так и не было найдено - рапортуем, что не найдено. На это нужно N операций. 

class ArrayStorage implements IStorage
{
    int size = 0;
    Node[] array = new Node[1];
    Node empty = new Node(null, null);

    class Node
    {
        public String key;
        public Integer value;

        public Node(String key, Integer value)
        {
            this.key = key;
            this.value = value;
        }
    }

    Node find(String key)
    {
        for (int j = 0; j < size; j ++)
            if (key.equals(array[j].key))
                return array[j];
        return empty;
    }

    public Integer get(String key)
    {
        return find(key).value;
    }

Для добавления новой пары достаточно в конец массива вписать новый узел, это быстро, всего 1 операция. Однако, прежде чем добавить новый узел, мы должны убедиться, что в словаре нет узла с точно таким же значением ключа, для этого необходимо вызвать метод поиска. Если такой ключ есть - мы записываем новое значение на место старого.

    void resize()
    {
        Node[] newArray = new Node[size * 2 + 1];
        for (int j = 0; j < size; j ++)
            newArray[j] = array[j];
        array = newArray;
    }
    
    public void put(String key, Integer value)
    {
        Node node = find(key);
        if (node.key == null)
        {
            if (size == array.length)
                resize();
            array[size++] = new Node(key, value);
        } else
            node.value = value;
    }  
}

Сколько памяти выделять для словаря? Какого размера массив необходимо декларировать для эффективной работы? Если размер массива будет совпадать с количеством элементов, то при каждом добавлении пары необходимо пересоздавать массив увеличенного размера и заниматься копированием значений из старого массива в новый, а это, на минуточку, N действий для каждой операции добавления элемента. 

Чтобы избежать тьмы лишних действий, можно выделять массив удвоенного размера, тогда процесс пересоздания массива добавит к сложности алгоритма лишь Log N операций, однако размер требуемой памяти удвоится.

Сложность поиска: N операций = O(N).
Сложность вставки: N (поиск) + Log N (пересоздание) + 1 (вставка) = O(N).
Требование к памяти: N (словарь) + N (резерв) = O(N).

Вывод: простой, но медленный способ, двойной расход памяти

Исходный код Storage1_Array можно посмотреть и запустить здесь.

Картинка вторая. Односвязный список.

Есть идеи по экономии памяти, но чтобы при этом не нужно было тратиться на дополнительные операции по пересозданию массива и копированию элементов? Ответ лежит на поверхности: односвязный список! Это динамическая структура, которая занимает ровно столько место, сколько в ней элементов и позволяет легко добавлять новые сущности.

Как видим, в класс узла добавилось ещё одно поле next - указатель на следующий элемент списка (между нами говоря, накладные расходы на необходимость хранить этот указатель могут свести на нет то, ради чего мы, собственно, и).

Сложность поиска узла по ключу не изменилась - нам вновь необходимо сканировать весь список от начала до конца, прыгая по кочкам списка.

class LinkedListStorage implements IStorage
{
    Node root = null;
    Node empty = new Node(null, null, null);

    class Node
    {
        public String key;
        public Integer value;
        public Node next;

        public Node(String key, Integer value, Node next)
        {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    Node find(String key)
    {
        for (Node curr = root; curr != null; curr = curr.next)
            if (key.equals(curr.key))
                return curr;
        return empty;
    }

    public Integer get(String key)
    {
        return find(key).value;
    }

Сложность добавления элемента значительно ускорился - нет дополнительных расходов на пересоздание массива, а новые пары удобнее всего добавлять в начало списка. Обратите внимание, что на рисунке порядок расположения пар реверсивен: кот был первым, а стал последним.

    public void put(String key, Integer value)
    {
        Node node = find(key);
        if (node.key == null)
            root = new Node(key, value, root);
        else
            node.value = value;
    }
}

Сложность поиска: N операций = O(N).
Сложность вставки: N (поиск) + 1 (вставка) = O(N).
Требование к памяти: N (словарь) = O(N).

Вывод: простой, но медленный способ, эффективен по памяти.

Исходный код Storage2_LinkedList можно посмотреть и запустить здесь.

А можно ли как-то ускорить процесс поиска ключей? Линейное время, это слишком медленно и применимо лишь на малых размерах словаря. Можно.

Картина третья. Отсортированный список.

В книжных словарях слова расположены по алфавиту, что позволяет искать их значительно быстрее, за логарифмическое время. Например, для поиска ключа в отсортированном списке из 1000 записей достаточно сделать всего десять сравнений, потому как 2^10 = 1024.

Давайте и мы попробуем располагать ключи в алфавитном порядке.

Теперь для поиска ключа можно применить бинарный поиск: смотрим, какой элемент посередине списка находится и рекурсивно продолжаем поиск либо в первой половине, либо во второй. Время поиска O(Log N).

class SortedStorage implements IStorage
{
    int size = 0;
    Node[] array = new Node[1];

    class Node
    {
        public String key;
        public Integer value;

        public Node(String key, Integer value)
        {
            this.key = key;
            this.value = value;
        }
    }

    int findIndex(String key)
    {
        int left = 0;
        int right = size - 1;
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (key.equals(array[mid].key)) 
                return mid; // found!
            if (key.compareTo(array[mid].key) > 0) 
                left = mid + 1;  // key < mid.key, move to right
            else 
                right = mid - 1; // key > mid.key, move to left
        }
        if (left < size && key.compareTo(array[left].key) > 0) 
            left++; // key must be placed at the right of [left]
        return left;
    }

    public Integer get(String key)
    {
        int j = findIndex(key);
        if (j < size && key.equals(array[j].key))
            return array[j].value;
        return null;
    }

Для добавления новой пары в словарь нужно сначала найти индекс в массиве, куда следует вставить пару, чтобы ключи располагались в алфавитном порядке, на это нужно Log N операций. Затем нужно сдвинуть все элементы на одну позицию вперёд и в освободившееся место разместить новую пару. Хотел бы обратить внимание, что сдвигать элементы нужно с хвоста поезда. 

    public void put(String key, Integer value)
    {
        int j = findIndex(key);
        if (j < size && key.equals(array[j].key))
        {
            array[j].value = value;
            return;
        }
        if (size == array.length)
            resize();
        for (int t = size; t > j; t--)
            array[t] = array[t - 1];
        array[j] = new Node(key, value);
        size++;
    }

    void resize()
    {
        Node[] newArray = new Node[size * 2 + 1];
        for (int j = 0; j < size; j ++)
            newArray[j] = array[j];
        array = newArray;
    }
}

На сдвиг элементов может потребоваться до N действий. Возможны дополнительные операции на пересоздание и копирование массива в размере Log N.

Сложность поиска: Log N операций = O(Log N).
Сложность вставки: Log N (поиск) + Log N (пересоздание) + N (сдвиг)  + 1 (вставка) = O(N).
Требование к памяти: N (словарь) + N (резерв) = O(N).

Вывод: логарифмический поиск, линейное добавление, двойной расход памяти.

Исходный код Storage3_SortedArray можно посмотреть и запустить здесь.

Кстати, а можно ли уменьшить расходы по памяти, используя для хранения пар односвязный отсортированный список? Увы, нельзя. Потому как мы можем только скользить по односвязному списку, без возможности перехода к любому элементу по индексу. А отличительная черта обычного массива - это моментальный доступ к любому элементу по его индексу, что и используется при двоичном поиске ключа в отсортированном массиве.

Впрочем, мы можем отказаться от излишних копирований и сдвигов элементов, если для хранения словаря воспользуемся двоичным деревом поиска. 

Но об этом в следующей статье, а также на бесплатном уроке, который пройдет уже 20 октября.

• Зарегистрироваться на бесплатный урок