HashMap также является коллекцией, которую мы много используем. Это реализация интерфейса карты на основе хэш-таблиц и существует в виде ключевой стоимости. В HashMap-значение всегда обрабатывается в целом. Система будет рассчитать местоположение хранилища ключевой стоимости на основе хэш-алгоритма. Мы всегда можем быстро сохранить и получить значение через ключ. Давайте проанализируем доступ к HashMap.
1. Определение
HashMap реализует интерфейс карты и наследует AbstractMap. Интерфейс карты определяет правила отображения ключей с значениями, а класс AbstractMap предоставляет внедрение магистрали интерфейса карты для минимизации работы, необходимой для реализации этого интерфейса. На самом деле, класс AbstractMap реализовал карту. Я думаю, что здесь должно быть яснее отмечать карту LZ здесь!
Общедоступный класс Hashmap <K, V> расширяет AbstractMap <K, V> реализует карту <K, V>, клонируемый, сериализуемый
2. Функция конструктора
HashMap предоставляет три конструктора:
HashMap (): создает пустой хэшмап с начальной емкостью по умолчанию (16) и коэффициентом загрузки по умолчанию (0,75).
Hashmap (int initycapacity): создает пустой хэшмап с указанной начальной емкостью и коэффициентом загрузки по умолчанию (0,75).
HashMap (int initialCapacity, Float LoadFactor): конструирует пустой хэшмап с указанной начальной емкостью и коэффициентом нагрузки.
Здесь упоминаются два параметра: начальная емкость, коэффициент загрузки. Эти два параметра являются важными параметрами, которые влияют на производительность HashMap. Емкость представляет количество ведер в хэш -таблице. Начальная емкость - это емкость при создании хэш -таблицы. Коэффициент загрузки - это шкала, которую хэш -таблица может достигать до автоматического увеличения его емкости. Он измеряет степень использования хеш -табличного пространства. Чем больше коэффициент нагрузки указывает, чем выше степень нагрузки хэш -таблицы и наоборот. Для хэш -таблиц с использованием метода связанного списка среднее время для поиска элемента - O (1+a). Следовательно, если коэффициент нагрузки больше, пространство будет более полно использоваться, но следствием является снижение эффективности поиска; Если коэффициент нагрузки слишком мал, данные о хэш -таблице будут слишком редкими, что приведет к серьезным отходам в пространство. Коэффициент загрузки системы по умолчанию составляет 0,75, и нам, как правило, не нужно ее модифицировать.
HashMap - это структура данных, которая поддерживает быстрый доступ. Чтобы понять его производительность, вы должны понимать его структуру данных.
Iii. Структура данных
Мы знаем, что две наиболее часто используемые структуры в Java являются массивами и смоделированными указателями (ссылки). Почти все структуры данных могут быть реализованы в сочетании с этими двумя, и то же самое относится и к Hashmap. Фактически, HashMap - это «связанный список хэш», следующую за его структурой данных:
Из приведенного выше рисунка мы можем увидеть, является ли базовая реализация HashMap или массив, но каждый элемент в массиве является цепью. Параметр начальная капота представляет длину массива. Ниже приведен исходный код конструктора HashMap:
public hashmap (int initialCapacity, float loadFactor) {// Начальная емкость не может быть <0 if (initialCapacity <0). Выбросить новое allodalargumentException («Незаконная начальная емкость:» + initialCapacity); // Начальная емкость не может> максимальное значение емкости, максимальная емкость HashMap составляет 2^30 IF (initialCapacity> Maximum_Capacity) initialCapacity = maximum_capacity; // коэффициент нагрузки не может быть <0 if (loadfactor <= 0 || float.isnan (loadfactor)) бросить новое allodalargumentException («Коэффициент незаконной нагрузки:» + loadfactor); // Рассчитайте значение N-Power наименьшее 2 больше, чем начало. int емкость = 1; В то время как (емкость <initialCapacity) емкость << = 1; this.LoadFactor = LoadFactor; // Установить предел емкости HashMap. Когда емкость HashMap достигает этого предела, операция расширения емкости будет выполнена Threshold = (int) (емкость * LoadFactor); // Инициализировать таблицу таблицы таблицы = новая запись [емкость]; init (); } Как видно из исходного кода, массив таблиц будет инициализироваться каждый раз, когда создается новый HashMap. Элемент массива таблицы - это входной узел.
Статическая запись класса <K, V> реализует Map.Entry <K, v> {final K Key; V Значение; Вход <K, V> Далее; окончательный int hash; /*** Создает новую запись. */ Inpit (int H, K K, V V, intry <K, v> n) {value = v; Next = N; Key = k; хэш = h; } .....}Среди них вход - внутренний класс HashMap, который содержит ключ, значение значения, следующий узел и значение хэша. Это очень важно. Это именно потому, что вход формирует элементы массива таблиц в качестве связанного списка.
Вышеуказанное кратко анализирует структуру данных HashMap, а ниже будет изучать, как HashMap реализует быстрый доступ.
4. Реализация хранения: положить (ключ, VLAUE)
Во -первых, давайте посмотрим на исходный код
public v Put (k Key, v value) {// Когда ключ нулевой, вызовите метод PutfornullKey, чтобы сохранить первую позицию NULL и таблицы. Вот почему HashMap позволяет null if (key == null) return putfornullkey (значение); // Рассчитать значение хэша ключа int hash = hash (key.hashcode ()); ----- (1) // Рассчитать положение ключевого значения хэша в массиве таблиц int i = indexfor (hash, table.length); ----- (2) // Итерация из i и найдите местоположение, где ключ сохраняется для (intpirt <K, v> e = table [i]; e! = Null; e = e.next) {объект k; // Судят, есть ли такое же значение хэш -значения на цепочке (ключ одинаково) // Если то же самое существует, непосредственно перезаписывает значение и верните старое значение, если (e.hash == hash && ((k = e.key) == key || equals (k))) {v oldvalue = e.value; // старое значение = новое значение e.value = value; e.recordaccess (это); вернуть OldValue; // возвращать старое значение}} // Увеличение количества модификаций на 1 ModCount ++; // Добавить ключ и значение в AddEntry I Position (хэш, ключ, значение, i); вернуть ноль; }Через исходный код мы можем четко видеть, что процесс сохранения HashMap: сначала определите, является ли ключ нулевой. Если он нулю, напрямую вызовите метод Putfornullkey. Если он не является пустым, сначала вычислите значение хэша клавиши, а затем найдите позицию индекса в массиве таблиц в соответствии со значением хэша. Если в этой позиции есть элемент, сравните, существует ли тот же ключ. Если он существует, перезаписывайте значение исходного ключа, в противном случае сохраните элемент в головке цепи (первый сохраненный элемент находится в конце цепи). Если таблица там не имеет элементов, она будет сохранена напрямую. Этот процесс кажется простым, но на самом деле он имеет глубокую внутреннюю информацию. Есть несколько моментов следующим образом:
1. Давайте сначала посмотрим на итерацию. Причина итерации здесь состоит в том, чтобы предотвратить существование того же значения ключа. Если два значения хеш (ключи) будут одинаковыми, метод обработки HashMap заключается в замене старого значения новым значением. Ключ не обрабатывается здесь, что объясняет, что в Hashmap нет двух одинаковых ключей.
2. В виде (1) и (2). Это суть HashMap. Прежде всего, есть хэш -метод, который является чистым математическим расчетом, который предназначен для расчета хеш -значения H.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); вернуть H ^ (h >>> 7) ^ (h >>> 4); }Мы знаем, что для таблиц HashMap распределение данных должно быть равномерным (лучше всего иметь только один элемент для каждого элемента, чтобы его можно было найти напрямую). Это не может быть слишком плотным или слишком свободным. Слишком плотно приведет к медленной скорости запроса, и слишком свободное будет тратить пространство. После расчета значения хэша, как мы можем убедиться, что элементы таблицы распределены одинаково? Мы будем думать о приобретении плесени, но поскольку приобретение плесени много потребляет, HashMap обрабатывает его так: вызовите метод Indexfor.
static int indexfor (int h, int length) {return h & (длина-1); }Длина базового массива HashMap всегда находится на N-силе 2, и он существует в конструкторе: емкость << = 1; Это всегда может гарантировать, что длина базового массива HashMap находится на N -силе 2. Когда длина до N мощности 2, H & (длина - 1) эквивалентна модулю длины, а скорость намного быстрее, чем принять модуль напрямую. Это оптимизация HashMap с точки зрения скорости. Что касается того, почему это 2 к NTH Power, то следующее объяснение.
Давайте вернемся к методу Indexfor, который имеет только одно утверждение: H & (длина - 1). В дополнение к приведенной выше операции модуля, это предложение также несет очень важную ответственность: равномерно распределить данные о таблице и полностью использовать пространство.
Здесь мы предполагаем, что длина составляет 16 (2^n) и 15, а H - 5, 6 и 7.
Когда n = 15, результаты 6 и 7 одинаковы, что означает, что их местоположения, хранящиеся в таблице, одинаковы, то есть происходит столкновение, а 6 и 7 будут образовывать связанный список в одном месте, что приведет к снижению скорости запроса. Это правда, что здесь анализируются только три числа, но не многие, поэтому давайте посмотрим на 0-15.
Из приведенной выше диаграммы мы видим в общей сложности 8 столкновений, и в то же время мы обнаруживаем, что впустую пространство очень большое, без записей в 1, 3, 5, 7, 9, 11, 13 и 15 местах, то есть данные не хранятся. Это связано с тем, что, когда они выполняют и работают с 14, последний бит результата, который они получают, всегда будет 0, то есть невозможно хранить данные в местах 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 и 1111. Пространство уменьшается, и вероятность столкновения будет увеличиваться, что приведет к медленной скорости запроса. Когда длина = 16, длина 1 = 15 составляет 1111. Затем при выполнении низкого бата и операции значение всегда совпадает с исходным хэш-значением, и при выполнении операции с высоким батом его значение равно его низкому значению. Следовательно, когда длина = 2^n вероятность столкновения между различными значениями хэша является относительно мала, что будет равномерно распределять данные в массиве таблиц, а скорость запроса быстрее.
Здесь мы рассмотрим процесс PUT: когда мы хотим добавить пару клавишных значений в хэшмап, система сначала рассчитает значения хэша ключа, а затем подтвердит местоположение, хранящее в таблице на основе значения хэша. Если в этой позиции нет элемента, вставьте его напрямую. В противном случае, итерация над списком элементов на этой точке и сравните значения хэша его ключа. Если два значения хэш равны, а значения ключей равны (e.hash == hash && ((k = e.key) == key || key.equals (k))), значение исходного узла перезаписывается значением новой записи. Если два значения хэш равны, но значения ключей не равны, вставьте узел в заголовок связанного списка. Для конкретного процесса реализации см. Метод добавления следующим образом:
void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {// Получить запись записи <K, v> e = таблица [bucketIndex]; // Поместите недавно созданный вход в индекс BucketIndex и пусть новая точка входа в исходную таблицу записи [BucketIndex] = Новая запись <K, V> (хэш, ключ, значение, E); // Если количество элементов в HashMap превышает предел, емкость будет в два раза больше, если (size ++> = пороговое значение) Resize (2 * Table.length); }В этом методе есть два момента:
Одним из них является поколение цепей. Это очень элегантный дизайн. Система всегда добавляет новый объект входа в BucketIndex. Если в BucketIndex есть объект, недавно добавленный объект входа будет указывать на исходный объект входа, формируя цепочку входа. Однако, если в BucketIndex нет объекта ввода, то есть e == NULL, то вновь добавленный объект входа указывает на NULL, и не будет сгенерирована цепочка входа.
2. Расширение пропускной способности.
По мере увеличения количества элементов в HashMap вероятность столкновения становится все больше и больше, а длина списка сгенерированных ссылок станет длиннее и длиннее. Это неизбежно повлияет на скорость HashMap. Чтобы обеспечить эффективность HashMap, система должна расширить емкость в определенной критической точке. Эта критическая точка - когда количество элементов в HashMap равно длине массива таблиц* коэффициент нагрузки. Но масштабирование-это очень трудоемкий процесс, потому что он требует пересчитывания местоположения этих данных в новой массиве таблиц и его копирования. Поэтому, если мы предсказали количество элементов в HashMap, то количество заданных элементов может эффективно улучшить производительность HashMap.
5. Чтение реализации: Get (Key)
По сравнению с хранением HashMap, снятие относительно простое. Найдите запись в индексе в массиве таблиц через хэш -значение ключа, а затем верните значение, соответствующее ключу.
public v get (object key) {// Если null, вызовите метод getfornullkey, чтобы вернуть соответствующее значение if (key == null) return getFornullKey (); // Рассчитать его хэш -код на основе значения хэшкода ключа int hash = hash (key.hashcode ()); // Установите значение в указанном индексе в массиве таблиц для (intpirt <K, v> e = table [indexfor (hash, table.length)]; e! = Null; e = e.next) {объект k; // Если поисковый ключ такой же, как и поисковый ключ, верните соответствующее значение, если (e.hash == hash && ((k = e.key) == key || key.equals (k))) return e.value; } return null; } Здесь значение, которое может быть быстро извлечено в зависимости от ключа, не только неразделимо от структуры данных HashMap, но и во многом связано с входом. Как упоминалось ранее, HashMap не хранит ключ и значение отдельно в хранимой процедуре, но обрабатывается как целое значение ключа, которое является объектом входа. В то же время значение только эквивалентно привязанности ключа. Во время процесса хранения система определяет местоположение хранения записи в массиве таблиц на основе хэшкода ключа, и в процессе извлечения соответствующий объект входа также выводится в соответствии с хэшкодом ключа.
Оригинальная ссылка: http://www.cnblogs.com/chenssy/p/3521565.html
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.