Глава 11. HashMap

В предыдущей главе мы написали реализацию интерфейса Map, использующую хеширование. Мы ожидали, что эта версия будет быстрее, поскольку список поиска короче, но порядок роста по-прежнему линейный.

Если существует n элементов и k подкарт, то размер подкарты в среднем равен n/k, что всё ещё пропорционально n. Однако, если мы увеличим k вместе с n, мы можем ограничить размер n/k.

Например, предположим, что каждый раз, когда n превышает k, мы удваиваем k; в этом случае среднее количество элементов на карте будет меньше 1, и почти всегда будет меньше 10, при условии, что хеш-функция может хорошо распределять ключи.

Если количество элементов в каждой подкарте постоянно, мы можем искать подкарту за постоянное время. И вычисление хеш-функции обычно занимает постоянное время (оно может зависеть от размера ключа, но не от количества ключей). Это делает основные методы Map, put и get, постоянными по времени.

В следующем упражнении вы увидите детали.

11.1 Упражнение 9

В MyHashMap.java я предоставил схему хеш-таблицы, которая растёт по мере необходимости. Вот определение:

public class MyHashMap<K, V> extends MyBetterMap<K, V> implements Map<K, V> {

    // average number of entries per sub-map before we rehash
    private static final double FACTOR = 1.0;

    @Override
    public V put(K key, V value) {
        V oldValue = super.put(key, value);

        // check if the number of elements per sub-map exceeds the threshold
        if (size() > maps.size() * FACTOR) {
            rehash();
        }
        return oldValue;
    }
}

MyHashMap расширяет MyBetterMap, поэтому он наследует определённые там методы. Он перекрывает только один метод — put, который вызывает версию put суперкласса — MyBetterMap. Затем он проверяет, нужно ли ему перехешировать. Вызов size возвращает общее количество n. Вызов maps.size возвращает количество встроенных отображений k.

Константа FACTOR (называемая коэффициентом загрузки) определяет среднее максимальное количество элементов для каждого подотображения. Если n > k * FACTOR, это означает, что n/k > FACTOR, что означает, что количество элементов подотображения превышает пороговое значение, поэтому мы вызываем rehash.

Запустите ant build для компиляции исходных файлов. Затем запустите ant MyHashMapTest. Он должен завершиться неудачно, потому что выполнение rehash вызовет исключение. Ваша задача — заполнить его.

Заполните тело rehash, чтобы собрать элементы таблицы, настроить размер таблицы, а затем повторно вставить элементы. Я предоставил два метода, которые могут быть полезны: MyBetterMap.makeMaps и MyLinearMap.getEntries. Каждый раз, когда вы его вызываете, ваше решение должно удваивать количество отображений.

11.2 Анализ MyHashMap

Если максимальное количество элементов в подотображении пропорционально n/k, и k пропорционально n, то несколько основных методов имеют постоянное время:

    public boolean containsKey（Object target）{ 
        MyLinearMap <K，V> map = chooseMap（target）; 
        return map.containsKey（target）; 
    } 

    public V get（Object key）{ 
        MyLinearMap <K，V> map = chooseMap（key）; return map.get（key）; 
    } 
    public V remove（Object key）{ 
        MyLinearMap <K，V> map = chooseMap（key）; 
        return map.remove（key）; 
    }

Каждый метод вычисляет хэш ключа, что занимает постоянное время, а затем вызывает метод в подотображении, которое также имеет постоянное время.

До сих пор всё было хорошо. Но другой основной метод, put, немного сложнее для анализа. Когда нам не нужно перехешивать, он имеет постоянное время, но когда мы это делаем, оно линейно. Таким образом, он похож на ArrayList.add, который мы анализировали в разделе 3.2.

По той же причине, если мы усредним ряд вызовов, результатом будет постоянное время. Аналогично, доказательство основано на анализе амортизации (см. раздел 3.2).

Предположим, начальное количество подотображений равно k = 2, коэффициент загрузки равен 1. Теперь давайте посмотрим, сколько работы требуется для серии вызовов put. В качестве базовой «единицы работы» мы будем считать вычисление хэша для ключа и добавление его в подотображение.

При первом вызове put требуется 1 единица работы. Второй вызов также требует 1 единицу. При третьем вызове нам нужно перехешировать, поэтому требуется 2 единицы для повторного заполнения существующих ключей и 1 единица для нового ключа.

Примечание переводчика: можно отдельно подсчитать количество элементов, перемещаемых при перехешивании, и сложить сложность перемещения элементов с вычислением хэша.

Теперь размер хеш-таблицы равен 4, поэтому следующий вызов put требует 1 единицы работы. Однако в следующий раз нам придётся перехешировать, потребуется 4 единицы для перехешивания существующих ключей и 1 единица для вычисления хэша нового ключа.

Рисунок 11.1 показывает закономерность, нормальное количество работы для добавления новых ключей показано внизу, дополнительное количество работы показано в виде башен.

Рисунок 11.1: Количество работы, необходимое для добавления элементов в хеш-таблицу

Как показано стрелками, если мы опрокинем башни, каждый блок заполнит пространство перед следующей башней. Результат кажется равным 2 единицам работы в среднем, что означает, что put в среднем имеет постоянное время.

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

11.3 Оценка

Мы уже показали, что containsKey, get и remove имеют постоянное время, а put — в среднем постоянное. Нам следует потратить некоторое время на то, чтобы оценить, насколько это замечательно. Независимо от того, насколько велика хеш-таблица, производительность этих операций практически одинакова. Это так.

Помните, что наш анализ основан на простой модели вычислений, где каждая «единица работы» занимает одинаковое количество времени. Реальные компьютеры более сложны. В частности, структуры данных, которые достаточно малы и подходят для высокоскоростного кэширования, обычно являются самыми быстрыми; если структура не подходит для высокоскоростного кеширования, но всё ещё подходит для памяти, она немного медленнее; если структура не подходит ни для памяти, ни для высокоскоростного кеширования, она очень медленная.

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

Также есть ограничение: некоторые постоянные по времени методы MyLinearMap становятся линейными. Например:

    public void clear() {
        for (int i=0; i<maps.size(); i++) {
            maps.get(i).clear();
        }
    }

clear должен очистить все подотображения, количество которых пропорционально n, поэтому оно линейное. К счастью, эта операция используется нечасто, поэтому в большинстве приложений этот компромисс приемлем.

11.4 Анализ MyHashMap

Прежде чем продолжить, мы должны проверить, действительно ли MyHashMap.put имеет постоянное время.

Запустите ant build, чтобы скомпилировать исходные файлы. Затем запустите ant ProfileMapPut. Он использует серию проблем разного масштаба, измеряет время выполнения HashMap.put (предоставленное Java) и строит график времени выполнения в зависимости от масштаба проблемы на логарифмической шкале. Если эта операция имеет постоянное время, общее время n операций должно быть линейным, поэтому результат должен быть прямой линией с наклоном 1. Когда я запускаю этот код, предполагаемый наклон близок к 1, что согласуется с нашим анализом. Вы должны получить нечто подобное.

Измените ProfileMapPut.java, чтобы измерить вашу реализацию MyHashMap, а не Java HashMap. Снова запустите анализатор, чтобы увидеть, близок ли наклон к 1. Возможно, вам потребуется настроить startN и endMillis, чтобы найти диапазон масштабов проблем, где время выполнения превышает несколько миллисекунд, но не превышает нескольких секунд.

Когда я запускал этот код, я был удивлён: наклон был примерно равен 1,7, что указывает на то, что эта реализация не всегда постоянна. Она содержит «ошибку производительности».

Перед чтением следующего раздела вы должны отследить ошибку, исправить её и убедиться, что теперь put имеет постоянное время и соответствует ожиданиям.