Hashmap и Hashset являются двумя важными членами фреймворка коллекции Java. HashMap - это общий класс реализации для интерфейса карты, а Hashset - это общий класс реализации для интерфейса SET. Хотя спецификации интерфейса, реализованные HashMap и HashSet, различны, их базовый механизм хранения хранения точно одинаковы, и даже сам Hashset использует HashMap для его реализации.
На самом деле, есть много сходства между хэшсом и хэшмапом. Для Hashset в системе используется алгоритм хэш для определения местоположения хранилища элементов сбора, чтобы гарантировать, что элементы сбора можно было бы быстро храниться и извлекать; Для HashMap значительная стоимость системы обрабатывается в целом, и система всегда вычисляет местоположение хранилища клавишного значения на основе алгоритма хэш-алгоритма, так что пара клавишных значений может быть быстро сохранена и восстановлена.
Перед тем, как ввести хранилище сбора, следует отметить, что, хотя коллекция претендует на хранение объектов Java, на самом деле она не помещает объекты Java в коллекцию SET, а только сохраняет ссылки на эти объекты в сборе набора. То есть коллекция Java на самом деле представляет собой набор нескольких эталонных переменных, которые указывают на фактический объект Java.
1. Основные особенности HashMap
После прочтения комментариев в исходном коде JDK Hashmap.class вы можете подвести итог множество функций HashMap.
Hashmap позволяет как ключ, так и значение быть нулевым, а хэштаблируется.
Hashmap-это небезопасно, а хэштаблируется.
Порядок элементов в HashMap не всегда одинаковы, а положение одного и того же элемента также может измениться со временем (случай изменения размера)
Временная сложность прохождения хэшмапа пропорциональна его способности и количеству существующих элементов. Если вы хотите обеспечить эффективность обхода, начальная мощность не может быть установлена слишком высокой или коэффициент баланса не может быть установлен слишком низким.
Подобно предыдущему связанному списку, поскольку HashMap является невыполненным потоком, Fail-Fast будет генерироваться, когда итератор пытается изменить структуру контейнера во время итерационного процесса. Синхронизированный хэшмап можно получить с помощью сбора.
2. Анализ структуры структуры данных хеш -таблицы
Хэш -таблица (хэш -таблица, хэш -таблица) - это структура данных, которая непосредственно обращается к местам хранения памяти на основе ключевых слов. То есть хеш -таблица устанавливает прямое отображение между ключевыми словами и адресами хранения
Как показано на рисунке ниже, ключ получает индексное положение ведра через функцию хеш -функции.
Получение индекса через функцию хэш неизбежно возникнет в той же ситуации, то есть конфликт. Вот несколько способов разрешения конфликтов:
Открытая адресация: Основная идея этого метода состоит в том, чтобы сканировать положения N под таблицей последовательно при столкновении с конфликтами, и заполнить, если есть какой -либо свободный. Конкретный алгоритм больше не будет объяснен, следующая схематическая диаграмма:
Отдельная цепочка: Основная идея этого метода состоит в том, чтобы объединить запись с тем же значением индекса в связанном списке при столкновении с конфликтами. Конкретный алгоритм больше не будет объяснен, следующая схематическая диаграмма:
Метод разрешения конфликтов в HashMap в JDK заключается в использовании отдельного метода цепочки.
3. Анализ исходного кода HashMap (JDK1.7)
1. Hashmap Read and Write Elements
Вход
Элементы, хранящиеся в 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; } // Методы получения и установки ключа, значение опущены, получают и устанавливают операции в последующих итераторах ... Общедоступные окончательные логические равенства (Object O) {if (! (O exactionOf map.Entry)) вернуть false; Map.Entry e = (map.Entry) o; Объект K1 = getKey (); Объект K2 = e.getKey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {object v1 = getValue (); Объект v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2))) вернуть true; } вернуть false; } // Здесь, сделайте или используйте хэшкод ключа и хэшкод значения, чтобы получить хэшкод входа в общедоступный окончательный окончательный int hashcode () {return objects.hashcode (getKey ()) ^ objects.hashcode (getValue ()); } public final String toString () {return getKey () + "=" + getValue (); } /** * Этот метод вызывается всякий раз, когда значение в записи * перезаписывается призывом POT (k, V) для ключа K, который уже * в HashMap. * / void recordaccess (hashmap <k, v> m) {} / ** * Этот метод вызывается всякий раз, когда запись * удаляется из таблицы. */ void recordRemoval (hashmap <K, v> m) {}}Запись включает в себя ключ, значение, хэш и ссылку на следующую запись. Очевидно, что это единственный связанный список, который реализует интерфейс Map.Entry.
RecordAcess (Hashmap <K, V> и RecordRemoval (HashMap <K, V>) не реализованы в HashMap. Однако два метода LinkedHashmap используются для реализации алгоритма LRU.
GET: Читать элементы, чтобы получить соответствующую запись из HashMap. Ниже приведен исходный код GET:
public v get (object key) {// ситуация, когда ключ - null if (key == null) return getFornullKey (); // Найти запись на основе записи клавиш <K, v> intry = getEntry (key); return null == запись? null: entry.getValue (); }GetFornullKey исходный код
private v getfornullkey () {if (size == 0) {return null; } // transtraighten Цепочка конфликтов для (inpit <k, v> e = table [0]; e! = Null; e = e.next) {if (e.key == null) return e.value; } return null; }Вход с ключом NULL хранится в таблице [0], но цепочка конфликтов в таблице [0] не обязательно имеет ключ как нулевой, поэтому ее необходимо пройти.
Получите запись в соответствии с ключом:
Окончательная запись <K, v> getEntry (object key) {if (size == 0) {return null; } int hash = (key == null)? 0: хэш (ключ); // Получить позицию индекса в таблице через хэш, а затем пройти конфликтующий связанный список, чтобы найти ключ для (entry <K, v> e = table [indexfor (hash, table.length)]; e! = Null; e = e.next) {объект k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k))) return e; } return null; }Выше приведено процесс чтения HASHMAP и ее исходного кода. Временная сложность O (1)
Поместите: написать элементы
Операция PUT в HashMap относительно сложна, потому что во время операции POT будет проходить операция расширения HashMAP.
Когда записан новый элемент, если есть ключ для написания элемента в HashMap, выполняется операция замены значения, что эквивалентно обновлению. Вот исходный код PUT:
public v put (k key, v value) {// Если таблица пуста, заполните if (table == empty_table) в соответствии с порогом размера {inflateTable (порог); } // Заполните запись с помощью ключа как null if (key == null) return putfornullkey (value); // генерировать хэш, чтобы получить отображение индекса индекса int hash = hash (key); int i = indexfor (hash, table.length); // транслируют цепочку конфликта текущего индекса, чтобы обнаружить, существует ли соответствующий ключ для (intry <K, v> e = table [i]; e! = Null; e = e.next) {объект k; // Если соответствующий ключ существует, замените OldValue и верните OldValue if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldvalue = e.value; e.value = значение; e.recordaccess (это); вернуть OldValue; }} // Ключ из вновь написанной записи не существует в цепочке конфликта modcount ++; // вставить новое дополнение к записи (хэш, ключ, значение, i); вернуть ноль; }исходный код AddEntry и CreateEntry:
void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {// Перед вставкой новой записи сначала судите по размеру текущего хэшмапа и его порогового размера и выберите, развернуть ли if (size> = threshold) && (null! хэш = (null! = ключ)? хэш (ключ): 0; bucketindex = indexfor (hash, table.length); } createEntry (хэш, ключ, значение, bucketIndex); } void createEntry (int hash, k key, v value, int bucketindex) {inpit <k, v> e = table [bucketindex]; // Метод вставки головы, вновь написанная запись вводится в переднюю часть первой записи в цепочке конфликта в текущей позиции индекса. Таблица [BucketIndex] = Новая запись <> (хэш, ключ, значение, E); размер ++; }Выше приведено процесс написания входа в хэшмап и его исходный код. Временная сложность O (1)
Удалить элемент удалить:
Окончательная запись <K, v> removeEntryForkey (ключ объекта) {if (size == 0) {return null; } // Рассчитать значение хэша в соответствии с ключом и получить индекс int hash = (key == null)? 0: хэш (ключ); int i = indexfor (hash, table.length); // Удалить связанный список, определите два указателя, предварительно представляет предшественник <K, v> prev = table [i]; Запись <K, v> e = prev; // transraight Цепочка конфликтов и удалить все ключ, в то время как (e! = Null) {intpirt <K, v> next = e.next; Объект k; // если найдено (e.hash == hash && ((k = e.key) == key || (key! = Null && key.equals (k)))) {modcount ++; размер--; // Поиск первого узла - это узел, который должен быть удален, если (prev == e) Таблица [i] = Далее; else prev.next = Далее; e.recordremoval (это); вернуть E; } prev = e; e = Далее; } return e; }Выше приведено процесс удаления HashMap, и ее исходный код. Временная сложность O (1)
2. Принцип хэш -хэш -хешина (функция хэш)
Реализация функции хэш в HashMap осуществляется с помощью хэша (объекта K) и Indexfor (int H, int Length). Давайте посмотрим на исходный код ниже:
окончательный int hash (объект k) {int h = hashseed; if (0! = h && k encessionof string) {return sun.misc.hashing.stringhash32 (((String) k); } h ^= k.hashcode (); // Эта функция гарантирует, что хешкоды, которые различаются только по // постоянным кратным в каждом битовом положении, имеют ограниченное количество столкновений (приблизительно 8 при коэффициенте загрузки по умолчанию). // Чтобы уменьшить вероятность конфликта h ^ = (h >>> 20) ^ (h >>> 12); вернуть H ^ (h >>> 7) ^ (h >>> 4); }Получите исходный код индекса индекса:
static int indexfor (int h, int length) {// утверждать integer.bitcount (длина) == 1: «длина должна быть ненулевой мощностью 2»; вернуть H & (длина-1); }Клавиши HashMap Карты с индексами в пределах интервала [0, Table.length] через хэш -функцию. Как правило, есть два вида методов индексации:
хэш (ключ) % Таблица. Длина, где длина должна быть основным числом. Hashtable использует эту реализацию в JDK.
По конкретным причинам использования первичных чисел вы можете найти соответствующие доказательства данных алгоритма, которые здесь не будут указаны.
хэш (ключ) и (таблица. Hashmap в JDK использует этот метод реализации.
Поскольку размер длины составляет 2 экспоненциального времени, хэш (ключ) и (таблица. Length - 1) всегда будет между [0, длина - 1]. Однако, если вы сделаете это в одиночку, будет большая проблема с конфликтом, потому что ценность хэшкода на Java составляет 32 бита. Когда емкость HashMap мала, например, когда 16, при выполнении операции XOR, высокий бит всегда отбрасывается, но после низкой операции, вероятность возникновения конфликта увеличивается.
Следовательно, чтобы уменьшить вероятность возникновения конфликта, в коде выполняется множество битовых операций и эксклюзивных или операций.
3. Стратегия распределения памяти Hashmap
Емкость переменной участника и Fultfactor
Требуемая емкость является экспоненциальным кратным 2 в HashMap, а емкость по умолчанию составляет 1 << 4 = 16. Существует также коэффициент баланса (нагрузка) в Hashmap. Чрезмерно высокие факторы уменьшат место для хранения, но время для поиска (поиск, включая методы PUT и GET в HashMap). Значение по умолчанию нагрузки составляет 0,75, что является оптимальным значением, приведенным при взвешивании сложности времени и сложности пространства.
Статический конечный int default_initial_capacity = 1 << 4; // aka 16 Статический окончательный конечный int maximum_capacity = 1 << 30; Static Final Float Default_Load_Factor = 0,75F;
Hashmap Constructor
Конструкция HashMap заключается в установлении емкости и начальном значении FultFactor
public hashmap (int initialCapacity, float loadFactor) {if (initialCapacity <0). Выбросить новое allodalargumentException («Незаконная начальная емкость:» + initialCapacity); if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) бросить новое allosalargumentException («Коэффициент незаконной нагрузки:» + loadfactor); this.LoadFactor = LoadFactor; Порог = начальная капсула; init (); } Я сказал, что до этой емкости в Hashmap должна быть экспоненциальное время 2, и в конструкторе нет предела. Итак, как обеспечить, чтобы значение емкости было экспоненциальным временем 2?
Во время операции пута исходный код будет определять, является ли текущая хэш -таблица пустой таблицей. Если это так, вызовите InflateTable (int tosize)
private void inflateletable (int tosize) {// Найти силу 2> = tosize intive = rounduptopowerof2 (tosize); threshold = (int) math.min (емкость * loadfactor, maximum_capacity + 1); Таблица = Новая запись [емкость]; inithashseedasneed (емкость); }где rounduptopowerof2 должен получить мощность N 2 больше или равна данному параметру
private static int out rounduptopowerof2 (int number) {// assert Number> = 0: «Номер должен быть неотрицательным»; Возврат номер> = Maximum_capacity? Maximum_capacity: (номер> 1)? Integer.highestonebit ((номер - 1) << 1): 1; }Integer.hightestonebit (int) - это операция, которая сохраняет самый высокий бит данного параметра и изменяет оставшиеся 0. Проще говоря, он должен изменить параметр int на n n portions меньше или равных его максимуму 2.
Если число N составляет n мощности 2, самый высокий бит находится на исходном втором высоком бите после уменьшения 1, а затем сдвиньте 1 бит, чтобы по -прежнему быть расположенным в положение наибольшего бита. Если число не является n мощностью 2, самый высокий бит по -прежнему является исходным самым высоким битом после уменьшения 1 бит осталось, чтобы сместить 1 бит, чтобы быть
Расширить емкость:
HashMap будет иметь изменение размера поведения при работе. Конкретный исходный код заключается в следующем:
void reszize (int newcapacity) {inpit [] oldtable = table; int oldCapacity = oldtable.length; // Хэш -таблица достигла своей максимальной емкости, 1 << 30 if (OldCapacity == Maximum_capacity) {threshold = integer.max_value; возвращаться; } Inpit [] newtable = new intry [newCapacity]; // Передача записи в OldTable на новичку // возвращаемое значение inithashseedAseded определяет, следует ли пересчитать передачу хэш -значения (новичок, inithashseedasneed (newcapacity)); Таблица = новичок; // пересчитывание порога порога = (int) math.min (newcapacity * loadfactor, maximum_capacity + 1); } void Transfer (entry [] newtable, boolean rehash) {int newcapacity = newtable.length; // transweep oldtable for (intry <k, v> e: table) {// transweep conflict while while (null! = E) {intry <k, v> next = e.next; if (rehash) {// пересчитывать хэш -значение e.hash = null == e.key? 0: хэш (E.Key); } int i = indexfor (e.hash, newcapacity); // вставить элемент в голову, метод вставки заголовка e.next = newtable [i]; Newtable [i] = E; e = Далее; }}}Вышеуказанное - весь процесс распределения памяти HashMap. Таким образом, когда HashMap ставит запись, он проверит текущую емкость и пороговый размер, чтобы выбрать, расширить ли емкость. Размер каждого расширения составляет 2 * Таблица. В течение периода расширения он будет определять, необходимо ли пересматривать значение хэша на основе inithashseseededed.
4. Hashmap итератор
Такие итераторы, как stustiretator, Keyterator, intryTerator и другие в HashMap, основаны на Hashiterator. Давайте посмотрим на его исходный код:
Частный абстрактный класс Hashiterator <e> реализует итератор <e> {intpirt <K, v> Next; // Следующая запись, чтобы вернуть int weddcount; // для быстрого обжима Int Index; // ток -слот, вход индекса таблицы <K, V> Current; // текущая запись hashiterator () {wedermodcount = modcount; // Найти первую запись в хэш -таблице if (size> 0) {inpit [] t = table; while (index <t.length && (next = t [index ++]) == null); }} public final boolean hasnext () {return next! = null; } Окончательная запись <K, v> nextentry () {// hashmap не является ratread-safe, и при прохождении, все же определите, существует ли какая-либо изменение структуры таблицы, если (modcount! = wedermodcount) бросьте New countrentModificationException (); Вход <K, V> e = Далее; if (e == null) бросить новый noshelementexception (); if ((next = e.next) == null) {// Найти следующую запись записи [] t = таблица; while (index <t.length && (next = t [index ++]) == null); } current = e; вернуть E; } public void remove () {if (current == null) бросить new allodalstateexception (); if (modcount! = weardModCount) бросить новый concurrentModificationException (); Объект k = current.key; ток = null; Hashmap.this.removeentryforkey (k); weddcount = modcount; }}Три итератора, ключ, стоимость и запись, инкапсулируются и становятся тремя перспективами сбора: Keyset, значения и вход. Эти три перспективы сбора подтверждают операции HOSHMAP Remove, RemoveAll и четкие операции HashMap, а также не поддерживают операции Add и Addall.