Отметьте это, и в то же время вы можете хорошо объединить методы HashCode () и Equals (). HashCode () не является равным, это также должно быть различным, чтобы иметь возможность вывести Equals ();
Поскольку, когда получает хэшмап, сначала сравните хэшкод, затем сравните равные, hashcode == && равен, оба являются истинными, поэтому он считается одним и тем же ключом
1. Обзор Hashmap:
Hashmap - это асинхронная реализация интерфейса карты на основе хэш -таблицы. Эта реализация предоставляет все дополнительные операции отображения и позволяет использовать нулевые значения и нулевые клавиши. Этот класс не гарантирует порядок отображений, особенно он не гарантирует, что заказ продлится.
2. Структура данных HashMap:
В языке программирования Java есть две основные структуры, одна - это массив, а другая - моделируемый указатель (ссылка). HashMap на самом деле является структурой данных «связанный список хэш», то есть комбинацию массивов и связанных списков.
Как видно из приведенного выше рисунка, базовый слой HashMap является структурой массива, и каждый элемент в массиве является еще одним связанным списком. Когда создается новый HashMap, будет инициализирован массив.
Исходный код заключается в следующем:
/ ** * ТАБЛИЦА, ПРИМЕНЕНИЕ ВСЕГДА. V Значение;
Видно, что запись является элементом в массиве.
3. Реализация HashMap Access:
1) Хранение:
public v Put (k Key, v value) {// hashmap позволяет нулевые клавиши и нулевые значения. // Когда ключ нуль, вызовите метод PutfornullKey и поместите значение в первую позицию массива. if (key == null) return putfornullkey (value); int hash = hash (key.hashcode ()); int i = indexfor (hash, table.length); для (intry <k, v> e = table [i]; e! = null; e = e.next) {объект k; || что это еще нет входа. modcount ++; AddEntry (хэш, ключ, значение, i); Из приведенного выше исходного кода мы видим, что когда мы помещаем элемент в HashMap, мы сначала пересчитываем хеш -значение на основе хэшкода ключа, и в соответствии с значением хэша, положение этого элемента в массиве (т.е. ), если на массиве есть и другие элементы, уже хранящиеся на этой позиции, поэтому элементы в этой позиции будут храниться в виде связанного списка, новые добавленные помещаются в главе цепи, а первая добавлена Один размещены в конце цепи. Если в этой позиции нет элемента в массиве, поместите элемент непосредственно в эту позицию в массив.
Метод AddEntry (хэш, ключ, значение, i) помещает пару клавишных значений в индексе I таблицы массива на основе расчетного хэш-значения. AddEntry - это метод разрешений на доступ к пакетам, предоставляемые HashMap, код заключается в следующем:
void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {// Получить запись в указанной индексе BucketIndex <K, V> E = Table [BucketIndex]; Индекс и пусть новая точка входа в исходную таблицу записи (размер ++> = порог) // Расширить длину объекта таблицы вдвое больше исходного. Изменение размера (2 * Table.length); Когда система решает сохранить пару ключевых значений в HashMap, значение в записи вообще не рассматривается, и она просто вычисляет и определяет местоположение хранения каждой записи на основе ключа. Мы можем полностью рассматривать значение в сборе карт как прикрепление к ключу.
Метод хэша (int h) пересчитывает хэш, один раз на основе хэшкода ключа. Этот алгоритм добавляет расчеты с высоким содержанием, чтобы предотвратить хэш-конфликты, вызванные, когда низкий балл остается неизменным, и при изменении высокой биты.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); Мы видим, что чтобы найти элемент в HashMap, нам нужно найти соответствующую позицию в массиве на основе значения хэша ключа. Как вычислять эту позицию - это алгоритм хэш. Как упоминалось ранее, структура данных HashMap представляет собой комбинацию массивов и связанных списков, поэтому, конечно, мы надеемся, что позиции элементов в этом HashMap должны быть равномерно распределены как можно больше, чтобы количество элементов на каждой позиции было только Один. эффективность запроса.
Для любого данного объекта, до тех пор, пока его возвращаемое значение HashCode () одинаково, значение хэш -кода, рассчитанное по программе, вызывающему метод хэш (int H), всегда одинаково. Первое, о чем мы думаем, это модуль хеш -значения до длины массива, чтобы распределение элементов было относительно однородным. Тем не менее, операция «Modulo» много потребляет, и это делается в Hashmap: вызовите метод Indexfor (int h, int length), чтобы вычислить, какой индекс объект должен храниться в массиве таблиц.
Код метода indexfor (int h, int length) выглядит следующим образом:
static int indexfor (int h, int length) {return h & (длина-1);Этот метод очень умный. Условия скорости. В конструкторе HashMap есть следующий код:
int емкость = 1;
Этот код гарантирует, что емкость HashMap всегда на n мощности 2 во время инициализации, то есть длина базового массива всегда находится на n мощности 2.
Когда длина всегда к мощности N 2, операция H & (длину-1) эквивалентна длине модуля, то есть длиной H %, но и имеет более высокую эффективность, чем %.
Это выглядит очень просто, но на самом деле это довольно загадочно.
Предполагая, что длина массива составляет 15 и 16, а оптимизированные хэш -коды составляют 8 и 9 соответственно, тогда результат после и операции выглядит следующим образом:
H & (table.length-1) Hash Table.length-1
8 & (15-1): 0100 и 1110 = 0100
9 & (15-1): 0101 и 1110 = 0100
------------------------------------------------------ ------------------------------------------------------ ---------------------------- ------------------------------------------ ------------------------------------------------------ ------------------------------------------------------ ------ -------------------------------------------- ------------------------------------------------------ -----------------------------------
8 & (16-1): 0100 и 1111 = 0100
9 & (16-1): 0101 и 1111 = 0101
Как видно из приведенного выше примера: когда они «как» с 15-1 (1110), тот же результат дается, то есть они будут расположены в том же положении в массиве, что создает столкновение, 8 и 9 будет расположено в той же положении в массиве, чтобы сформировать связанный список. В то же время мы также можем обнаружить, что когда длина массива составляет 15, значение хэша будет «как» с 15-1 (1110), тогда последний бит всегда будет 0, и 0001, 0011, 0101, 1001 , 1011, 0111, 0111, 1101 никогда не может хранить элементы, и пространство потрачено впустую довольно много. Вероятность столкновения увеличивается и медленная эффективность запроса! Когда длина массива составляет 16 лет, то есть, когда она к мощности N 2, значение на каждом бинке бинарного числа, полученного 2N-1 Это и на низком бите, так что низкий уровень полученного хэша суммы одинаково, в сочетании с методом хэш (int h) еще больше оптимизирует хэшкод ключа и добавляет вычисления с высоким батом, так что только два значения Того же значения хэша будет размещено в том же положении в массиве, чтобы сформировать связанный список.
Следовательно, когда длина массива равна n мощности 2, вероятность того, что разные ключи могут рассчитать один и тот же индекс меньше, поэтому данные будут равномерно распределены по массиву, что означает, что вероятность столкновения невелика, относительно, запрос при На этот раз вам не нужно пересекать связанный список в определенном месте, поэтому эффективность запроса будет выше.
Согласно исходному коду метода POT выше, когда программа пытается поместить пару ключевых значений в HashMAP, программа сначала определяет местоположение хранения записи на основе возвращаемого значения HASHCODE (): если Ключ из двух записей hashcode () возвращаемое значение одинаково, а местоположение их хранения одинаково. Если ключи от этих двух записей возвращают True через сравнение по равным, значение вновь добавленной записи переопределяет значение исходной записи в коллекции, но ключ не будет переоценить. Если ключи от этих двух записей возвращают false через сравнение равных, недавно добавленная запись сформирует цепочку входа с исходной записью в коллекции, а недавно добавленная запись находится в начале цепочки входа - подробности продолжаются видеть Описание метода AddEntry ().
2) Читать:
public v get (object key) {if (key == null) return getFornullKey (); Длина); вернуть E.Value; С помощью хэш -алгоритма, хранящегося выше в качестве основы, легко понять этот код. Из приведенного выше исходного кода мы видим, что при получении элемента в HashMap сначала вычислите хэшкод ключа, найдите элемент в соответствующей позиции в массиве, а затем найдите необходимый элемент в связанном списке соответствующей позиции через метод равных ключа.
3) Подводя итог, HashMap обрабатывает ключевую ценность в целом внизу, и это целое является объектом входа. В основном HashMap используется массив входа [] для хранения всех пар клавишных значений. Метод равных.
4. Hashmap's Resisize (Rechash):
Поскольку в HashMap все больше и больше элементов, вероятность конфликта хеш -конфликта становится все выше и выше, потому что длина массива фиксированной. Поэтому, чтобы повысить эффективность запроса, массив Hashmap должен быть расширен в Появляются: данные в исходном массиве должны быть пересчитаны и размещены в новом массиве, который изменяется.
Итак, когда будет расширен Hashmap? Когда количество элементов в HashMap превышает размер массива *LoadFactor, массив расширяется. То есть по умолчанию размер массива составляет 16. Тогда, когда количество элементов в HashMap превышает 16*0,75 = 12, размер массива увеличивается до 2*16 = 32, то есть вдвое больше размера, и затем пересчитывайте его. Полем
5. Параметры производительности HashMap:
HashMap содержит следующие конструкторы:
HashMap (): построить HashMap с начальной емкостью 16 и коэффициентом нагрузки 0,75.
Hashmap (int initycape): постройте хэшмап с начальной емкостью и коэффициентом нагрузки 0,75.
HashMap (int initialCapacity, float loadFactor): создает HashMap с указанной начальной емкостью и указанным коэффициентом нагрузки.
Основной конструктор HashMap, HashMap (int initialCapacity, Float LoadFactor), имеет два параметра, они представляют собой начальную емкость и начальную емкость и коэффициент нагрузки.
Первоначальная силу: максимальная емкость HashMap, то есть длину базового массива.
fultfactor: коэффициент нагрузки определяется как: фактическое количество элементов хэш -таблицы (n)/емкость хэш -таблицы (M).
Коэффициент нагрузки измеряет степень использования хэш -пространства. Для хэш -таблиц с использованием метода связанного списка среднее время для поиска элемента составляет O (1+A) Коэффициент нагрузки также является небольшим, тогда данные хэш -таблицы будут слишком редкими, что вызывает серьезную трату места.
При реализации HashMap максимальная емкость HashMap определяется пороговым полем:
Кода -копия выглядит следующим образом:
порог = (int) (емкость * loadfactor);
Основываясь на формуле определения коэффициента нагрузки, можно видеть, что порог представляет собой максимальное количество элементов, разрешенных в соответствии с FALTECTOR и емкостью. Коэффициент нагрузки по умолчанию 0,75 является сбалансированным выбором для пространственной и временной эффективности. Когда пропускная способность превышает эту максимальную емкость, увеличение размера емкость HashMap в два раза превышает емкость:
if (size ++> = пороговое значение) RESIZE (2 * TABLE.Length);
6. Неудачный механизм:
Мы знаем, что java.util.hashmap не безопасен для потока, поэтому, если другие потоки изменяют карту во время процесса использования итератора, будет выбрана совместная стратегия.
Эта стратегия реализована в исходном коде через поле Modcount. Ожидаемый модконт итератора.
Hashiterator () {weardmodcount = modcount; ; Во время процесса итерации определите, равны ли ModCount и WeallyModCount.
Обратите внимание, что ModCount объявлен как нестабильный, обеспечивая видимость модификаций между потоками.
Окончательная запись <K, v> nextentry () {if (modcount! = wedermodcount) бросить новый comproundmodificationexception (); В API HashMap заявлено:
Итераторы, возвращаемые «методом сбора» из всех классов HashMap быстро: после создания итератора, если отображение модифицировано из структуры, если он не пройдет через собственный метод удаления итератора, любой другой способ Бросьте condurentModificationException, если модификация сделана. Следовательно, в соответствии с одновременными модификациями, итератор скоро потерпит неудачу, не рискуя произвольным неопределенным поведением в неопределенные времена в будущем.
Обратите внимание, что быстрое поведение итератора не может быть гарантировано. Fast Fail Iterator бросает condurentmodificationException, когда оно работает лучше всего. Следовательно, неправильно писать программы, которые полагаются на это исключение, и правильным способом является то, что быстрое поведение итератора следует использовать только для обнаружения ошибок программы.