Мы проанализировали два набора ArrayList и LinkedList. Мы знаем, что ArrayList реализован на основе массивов, а LinkedList реализован на основе связанных списков. У каждого есть свои преимущества и недостатки. Например, ArrayList будет лучше, чем LinkedList, когда позиционирует и искал элементы, в то время как LinkedList будет лучше, чем ArrayList при добавлении и удалении элементов. HashMap, представленный в этой статье, сочетает в себе преимущества обоих. Его базовый уровень реализован на основе хэш -таблицы. Если конфликт хэш не рассматривается, то временная сложность HashMap Кроме того, удаление, модификация и поисковые операции могут достичь удивительного O (1). Давайте сначала посмотрим на структуру хэш -таблицы, на которой она основана.
Как видно из приведенного выше рисунка, хэш -таблица представляет собой структуру, состоящую из массива и связанный список. Конечно, вышеупомянутая фигура является плохим примером. Хорошая хэш -функция должна попытаться усреднить распределение элементов в массиве, уменьшить конфликты хэша и уменьшить длину связанного списка. Чем дольше длина связанного списка означает, что чем больше узлов его нужно пересекать во время поиска, тем хуже будет производительность хэш -таблицы. Далее, давайте посмотрим на некоторые переменные члена Hashmap.
// По умолчанию начальная емкость Статическая окончательная конечная int default_initial_capacity = 1 << 4; // Статическое максимальное емкость по умолчанию. Переходная запись <K, v> [] table = (intry <K, v> []) empty_table; // размер хэшмапа, то есть количество пар клавишных значений, хранящихся в размере Transient int Hashmap; // Пороговое значение пары ключевых значений используется для определения емкости с использованием int-incemations-flocation liftor-clovatod withpostamations////////////edowdle, что используется невыполненное значение; Механизм Transient int modcount; // Использование порога по умолчанию альтернативного хэш -статического окончательного окончательного int alternative_hashing_threshold_default = integer.max_value; // Случайный семена хэша помогает уменьшить количество столкновений хэш transient int hashseed = 0;
Как видно из переменных элементов, начальная емкость HashMap по умолчанию составляет 16, а коэффициент загрузки по умолчанию - 0,75. Порог-это порог пары ключевых значений, которую можно хранить в наборе. По умолчанию является начальная мощность*коэффициент загрузки, то есть 16*0,75 = 12. Когда пара ключевых значений должна превышать порог, это означает, что хеш-таблица уже насыщена в настоящее время. Если элементы будут продолжаться, будет добавлен хэш -конфликт, который ухудшит производительность HashMap. В настоящее время механизм автоматического расширения пропускной способности будет запускается для обеспечения производительности HashMap. Мы также видим, что хэш-таблица на самом деле представляет собой массив входа, и каждая запись, хранящаяся в массиве, является узлом заголовка одностороннего списка связанных счетов. Эта запись представляет собой статический внутренний класс HashMap, давайте посмотрим на переменные входа члена.
Статическая запись класса <K, V> реализует Map.Entry <K, v> {final K Key; // значение V -ключа V; // запись значения <K, V> Далее; // Ссылка на следующую запись int hash; // histocode ... // Опустить следующий код}Экземпляр входа-это пара клавиш, которая содержит ключ и значение. Каждый экземпляр записи имеет ссылку на следующий экземпляр записи. Чтобы избежать повторяющихся расчетов, каждый экземпляр записи также хранит соответствующий хэш -код. Можно сказать, что входной массив является ядром HashMap, и все операции выполняются для этого массива. Поскольку исходный код HashMap относительно длинный, невозможно ввести все его методы всеобъемлющим образом, поэтому мы сосредоточены только на ключевых моментах, чтобы ввести их. Затем мы будем ориентированы на проблемы и подробно рассмотрим внутренний механизм HashMap для следующих вопросов.
1. Какие операции выполняет Hashmap во время строительства?
// Конструктор, пройти в емкость инициализации и коэффициент нагрузки Public Hashmap (int initialCapacity, float loadFactor) {if (initialCapacity <0) {бросить новый allosalargumentException («Незаконная начальная емкость:» + initialCapacity); } // Если способность инициализации больше максимальной емкости, установите ее на максимальную емкость, если (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Если коэффициент нагрузки меньше 0 или коэффициент загрузки не является номером плавающей запятой, исключение добавляется, если (loadfactor <= 0 || float.isnan (loadfactor)) {бросить новый allosalargumentException («Незаконная нагрузка:« + loadfactor); } // Установите коэффициент загрузки this.LoadFactor = loadFactor; // Порог - это порог емкости инициализации = initialCapacity; init ();} void init () {}Все конструкторы будут называть этот конструктор. В этом конструкторе мы видим, что в дополнение к некоторой проверке параметров он делает две вещи: установите коэффициент нагрузки на коэффициент входящего нагрузки и установите порог на входящий размер инициализации. Метод init пуст и ничего не делает. Обратите внимание, что в настоящее время не создается новый массив записи на основе входящего размера инициализации. Итак, когда мы создадим новый массив? Продолжайте читать.
2. Какие операции будут выполнены, когда HashMap добавляет пары клавиш?
// Поместите пары клавиш-значения в HashMap public v Put (k Key, v value) {// инициализировать if (table == umpty_table) {// инициализировать хэш-таблицу InflateTable (порог); } if (key == null) {return putfornullkey (value); } // Рассчитать хэш -код ключа int hash = hash (key); // позиционировать положение хэш -таблицы в соответствии с хэш -кодом int i = indexfor (hash, table.length); for (intry <k, v> e = table [i]; e! = null; e = e.next) {объект k; // Если соответствующий ключ уже существует, замените его значение и верните исходное значение, если (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldvalue = e.value; e.value = значение; e.recordaccess (это); вернуть OldValue; }} modcount ++; // Если нет соответствующего ключа, добавьте вход в AddEntry HashMap (хэш, ключ, значение, i); // return null return null;}Вы можете видеть, что при добавлении пар клавишных значений вы сначала проверьте, является ли хэш-таблица пустой таблицей, и если это пустая таблица, она будет инициализирована. Затем выполните последующие операции и вызовите функцию хэша для расчета хэш -кода прошедшего ключа. Поместите указанный слот массива входа в соответствии с хэш-кодом, а затем пройдите односторонний связанный список слота. Если пройти уже уже существует, выполните операцию замены, в противном случае будет создана новая запись и добавлена в хэш -таблицу.
3. Как инициализируется хэш -таблица?
// Инициализировать хэш -таблицу, и емкость хэш -таблицы будет расширена, поскольку возможно, что входящая емкость не является мощностью 2 частной пустоты, зажигаемой (int tosize) {// емкость хэш -таблицы должна быть мощностью 2 int емкости = rounduptoPowerof2 (tosize); // Установить порог, здесь обычно является емкостью * loadfactor threshold = (int) math.min (емкость * loadfactor, maximum_capacity + 1); // Создать новую хэш -таблицу с указанной таблицей емкости = новая запись [емкость]; // Инициализировать хеш -семян inithashseedasneedededededededededed (емкость);}Как мы знаем выше, при построении хэшмапа мы не будем создавать новый массив записей, но проверим, является ли текущая хэш -таблица пустой таблицей во время операции пута. Если это пустая таблица, вызовите метод зажигания для инициализации. Код для этого метода опубликован выше. Вы можете видеть, что емкость массива входа будет пересматриваться внутри метода, потому что размер инициализации, пройденное при построении HashMap, может не быть мощностью 2, поэтому вам необходимо преобразовать это число в мощность 2, а затем создать новый массив входа, основанный на новой емкости. При инициализации хэш -таблицы снова сбросьте порог, и порог, как правило, является емкостью*LoadFactor. Кроме того, семена хэша (хэш -стиль) будут инициализированы при инициализации хэш -таблицы. Этот хешс используется для оптимизации хэш -функции. По умолчанию 0, и альтернативный алгоритм хэш не используется, но вы также можете установить значение хеш -снятия самостоятельно для достижения эффекта оптимизации. Это будет подробно обсуждаться ниже.
4. Когда HashMap определяет, нужно ли он расширить емкость и как она расширяет емкость?
// Добавить метод записи и сначала определите, хотите ли вы расширить добавление емкости void (int hash, k -ключ, v Значение, int bucketIndex) {// Если размер хэшмапа больше, чем порог, и значение соответствующего слота хэш -таблицы не пуст, если (размер> = порог) и (null! Порог, это указывает на то, что конфликт хэш -конфликта собирается, поэтому расширяйте изменение размера емкости (2 * Table.length); хэш = (null! = ключ)? хэш (ключ): 0; bucketindex = indexfor (hash, table.length); } // Здесь показано, что размер хэшмапа не превышает порога, поэтому нет необходимости расширять емкость CreateEntry (хэш, ключ, значение, bucketIndex);} // расширять хэш таблицу void recainize (int newcapacity) {inpit [] oldTable = таблица; int oldCapacity = oldtable.length; // Если текущая максимальная емкость уже используется, вы можете только увеличить пороговое значение if (oldcapacity == maximum_capacity) {threshold = integer.max_value; возвращаться; } // В противном случае развернуть запись емкость [] newtable = new inpit [newCapacity]; // Метод переноса хэш -таблицы (новичок, inithashseedasneededededededededededededededededededededededededededededededededededededededededededededededededededededededed (newcapacity)); // Установить текущую таблицу хэш в новую таблицу хэш -таблицы = newtable; // Обновление HASH TABLE THRESHOLD = (int) math.min (newcapacity * loadfactor, maximum_capacity + 1);}При вызове метода PUT, чтобы добавить пару клавишных значений, если в коллекции нет ключа, вызовите метод AddEntry и создайте новую запись. Когда вы увидите код AddEntry, размещенный выше, перед созданием новой записи вы сначала определит, превышает ли размер текущего элемента коллекции порог. Если порог превышает порог, вызовите изменение размера для расширения. Новая пропущенная емкость вдвое превышает оригинальную хэш -таблицу. В методе изменения размера будет создан новый массив записи с емкостью в два раза в исходной хэш -таблице. Тогда все элементы в старом хеш -таблице мигрируются в новую хэш -таблицу, где можно выполнить перефразирование, и выполнять ли перефразирование, выполняется в соответствии со значением, рассчитанным методом инитэссоизированной. После завершения миграции хеш -таблицы, текущая хеш -таблица заменяется новой, и, наконец, пороговое значение HashMap пересчитывается на основе новой емкости хэш -таблицы.
5. Почему размер массива входа должен быть силой 2?
// возвращать индекс массива, соответствующий хэш-коду static int indexfor (int h, int length) {return h & (length-1); }Метод Indexfor вычисляет соответствующий индекс в массиве на основе хеш -кода. Мы видим, что (&) оператор используется внутри этого метода. Операция состоит в том, чтобы выполнить битовые операции на двух операнде. Если соответствующие два бита составляют 1, результат-1, в противном случае это 0. Операции часто используются для удаления высоких значений операндов, таких как: 0101101010 и 00001111 = 00001010. Давайте вернемся к коду и посмотрим, что делает H & (Length-1).
Известно, что длина, пройденная, - это длина входного массива. Мы знаем, что абонент массива рассчитывается по 0, поэтому максимальный индекс массива составляет длину-1. Если длина-это мощность 2, то двоичные биты длины-1 следуют 1. В настоящее время функция H & (длина-1) состоит в том, чтобы удалить высокое значение H и оставить только низкое значение H в качестве подростка массива. Исходя из этого, мы видим, что размер массива входа определяется как мощность 2, чтобы использовать этот алгоритм для определения подписания массива.
6. Как функция хэш рассчитывает хэш -код?
// функция, которая генерирует хэш -код окончательный int hash (объект k) {int h = hashseed; // Если ключ имеет тип строки, используйте другой алгоритм хэш -алгоритма if (0! = H && k exanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h ^= k.hashcode (); // функция возмущения h ^ = (h >>> 20) ^ (h >>> 12); вернуть H ^ (h >>> 7) ^ (h >>> 4);}Последние две строки метода хэша являются алгоритмом, который действительно рассчитывает хэш -значение. Алгоритм, который вычисляет хэш -код, называется функцией возмущения. Так называемая функция возмущения состоит в том, чтобы смешать все вместе. Вы можете видеть, что здесь используются четыре операции с правой сменой. Цель состоит в том, чтобы смешать высокое значение H и низкое значение, чтобы увеличить случайность низкого значения. Как указано выше, мы знаем, что индекс массива позиционирования определяется на основе низкого значения хеш-кода. Хэш -код ключа генерируется методом хэшкода, и низкое значение хеш -кода, сгенерированного плохим методом хэшкода, может иметь много повторения. Чтобы сделать хэш-код, отображенный относительно равномерно на массиве, функция возмущения пригодится, объединяя характеристики высокого значения в низкое значение, увеличивая случайность низкого значения, что делает распределение хэша более свободным, тем самым повышая производительность. На следующем рисунке приведен пример, чтобы помочь понять.
7. Что происходит с заменой хэша?
Мы видим, что в хеш -методе хешс сначала будет назначен H. Этот хешс является хэш -семенем, которое является случайным значением и используется для оптимизации функции хэш. Хэш -снятие по умолчанию составляет 0, что означает, что альтернативный алгоритм хэш -алгоритм не используется по умолчанию. Итак, когда использовать хэш -семей? Во -первых, вам необходимо установить альтернативный хэш для включения и установить значение jdk.map.althashing.Threshold в свойстве системы. Это значение по умолчанию в системном свойстве составляет -1. Когда это -1, пороговое значение использования альтернативного хэша является integer.max_value. Это также означает, что вы никогда не можете использовать хэш для замены. Конечно, вы можете установить этот порог немного меньше, так что случайный хешедж будет генерироваться, когда элемент набора достигает порога. Это увеличивает случайность хэш -функции. Зачем использовать альтернативный хэш? Когда элемент установки достигает установленного вами порога, это означает, что хэш -таблица относительно насыщенная, а возможность хэш -конфликтов значительно увеличится. В настоящее время использование более случайной хэш -функции для добавленных элементов может сделать добавленные элементы более случайным образом распределенным в хэш -таблице.
ПРИМЕЧАНИЕ. Все вышеперечисленные анализы основаны на JDK1.7, и между различными версиями будут существенные изменения, читатели должны обратить внимание.