Структура хранения
Во -первых, HashMap хранится на основе хэш -таблицы. Внутри его есть массив. Когда должен храниться элемент, сначала вычислите значение хэша его ключа и найдите соответствующий индекс элемента в массиве на основе значения хэша. Если в этой позиции нет элемента, поместите текущий элемент напрямую. Если есть элемент (запоминается как здесь), свяжите текущий элемент с передней частью элемента A, а затем поместите текущий элемент в массив. Таким образом, в HashMap массив фактически сохраняет первый узел связанного списка. Ниже приведена изображение из энциклопедии Baidu:
Как показано на рисунке выше, каждый элемент является объектом входа, где сохраняются ключ и значение элемента, и есть указатель, который можно использовать для указания на следующий объект. Все ключи с одинаковым значением хэша (то есть конфликтом) объединяют их, используя связанный список, который является методом молнии.
Внутренние переменные
// По умолчанию начальная емкость Статическая конечная конечная int default_initial_capacity = 16; // Статическая максимальная емкость Статическая конечная конечная int maximum_capacity = 1 << 30; // коэффициент загрузки по умолчанию Статический окончательный float default_load_factor = 0.75f; // hast table transient intry <K, v> [] таблица; // Количество клавиш-Value transiet transiet int size; Коэффициент хэш -массива окончательный поплавок нагрузки;
В приведенных выше переменных емкость относится к длине хэш -таблицы, то есть размером таблицы, а по умолчанию составляет 16. Коэффициент нагрузки нагрузки - это «полная степень» хэш -таблицы, и в документации JDK говорится:
Коэффициент нагрузки является мерой того, насколько полной хэш -таблица разрешена добраться до того, как его емкость будет автоматически увеличиваться. Когда количество записей в хэш -таблице превышает произведение коэффициента нагрузки и текущей емкости, хэш -таблица перефразируется (то есть внутренние структуры данных перестраиваются), так что хэш -таблица имеет приблизительно вдвое больше количества ведер.
Общее значение имеет: коэффициент загрузки - это мера того, насколько полна хэш -таблица может быть установлена до расширения. Когда количество «паров ключевых значений» в хэш-таблице превышает продукт текущей емкости и коэффициента загрузки, хэш-таблица хэшируется (то есть внутренняя структура данных восстановлена), а емкость хэш-таблицы становится примерно вдвое превышающим оригинал.
Как видно из приведенной выше определения переменной, коэффициент загрузки по умолчанию default_load_factor составляет 0,75. Чем больше это значение, тем выше скорость использования пространства, но скорость запроса (включая Get и Plat) замедлит. После понимания коэффициента загрузки порог также может его понять. На самом деле это равна коэффициенту загрузки емкости.
Конструктор
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); // Найти мощность 2> = initialCapacity int емкость = 1; В то время как (емкость <initialCapacity) // Рассчитайте наименьшую мощность 2, которая больше, чем указанная емкость << = 1; this.LoadFactor = LoadFactor; threshold = (int) math.min (емкость * loadfactor, maximum_capacity + 1); Таблица = Новая запись [емкость]; // выделять пространство на хэш -таблицу usealthashing = sun.misc.vm.isbooted () && (емкость> = holder.alternative_hashing_threshold); init ();}Есть несколько конструкторов, и они в конечном итоге будут называть вышеизложенное. Он принимает два параметра, один - начальная емкость, а другой - коэффициент загрузки. Вначале мы сначала определяем, является ли комбинация стоимости законной, и если есть какие -либо проблемы, будет брошено исключение. Важным является расчет приведенной ниже емкости, его логика состоит в том, чтобы вычислять наименьшую мощность 2 больше, чем начальная валичность. Фактически, цель состоит в том, чтобы сделать емкость более или равной указанной начальной емкости, но это значение должно быть экспоненциальным кратным 2, что является ключевой проблемой. Причиной этого является в основном для картирования значений хэш. Давайте сначала посмотрим на хэш -метод в хэшмапе:
окончательный int hash (объект k) {int h = 0; if (usealthashing) {if (k exanceof string) {return sun.misc.hashing.stringhash32 ((string) k); } h = hashseed; } h ^= k.hashcode (); // Эта функция гарантирует, что хешкоды, которые различаются только по // постоянным кратным в каждом битовом положении, имеют ограниченное количество столкновений (приблизительно 8 при коэффициенте загрузки по умолчанию). h ^ = (h >>> 20) ^ (h >>> 12); вернуть H ^ (h >>> 7) ^ (h >>> 4);} static int indexfor (int h, int length) {return h & (длина-1);}Метод hash () пересчитывает значение хэша ключа и использует относительно сложные битовые операции. Я не знаю конкретную логику. В любом случае, это определенно лучший метод, который может уменьшить конфликты или что -то в этом роде.
Indexfor () ниже представляет собой индекс элемента в таблице хэш на основе значения хэша. Как правило, в хэш -таблице вы используете значения хэша для модуляции длины таблицы. Когда длина (то есть емкость)-это мощность 2, H & (длина-1)-тот же эффект. Более того, мощность 2 должна быть равномерным числом, затем после вычитания 1, это нечетное число, и последний бинар должен быть 1. Тогда последний бит H & (длину-1) может быть 1 или 0, который может быть равномерно хэшировать. Если длина является нечетным числом, то длина-1-равномерное число, а последний бит-0. В настоящее время последний бит H & (Length-1) может составлять только 0, и все полученные подписки-равномерная, поэтому половина пространства потрачена впустую. Следовательно, емкость в HashMap должна быть мощностью 2. Вы можете видеть, что по умолчанию по умолчанию_иниат_Капейность = 16 и максимальная_КАПАЗИТ = 1 << 30 оба похожи на это.
Объект входа
Пары ключевых значений в HashMap инкапсулируются в объекты входа, который является внутренним классом в 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; } public final k getKey () {return Key; } public final v getValue () {return Value; } public final v setValue (v newValue) {v oldValue = value; value = newValue; вернуть OldValue; } public final boolean equals (Object o) {if (! (o encessOf 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; } public final int hashcode () {return (key == null? 0: key.hashcode ()) ^ (value == null? 0: value.hashcode ()); } public final String toString () {return getKey () + "=" + getValue (); } void recordAccess (hashmap <k, v> m) {}}Реализация этого класса проста и легко понять. Такие методы, как getKey (), getValue (), предусмотрены для вызова. Чтобы определить равенство, необходимо, чтобы как ключ, так и значение были равны.
Поместите операцию
Поместите первым, прежде чем получить его, поэтому сначала посмотрите на метод put ():
public v put (k key, v value) {if (key == null) return putfornullkey (value); int hash = hash (ключ); int i = indexfor (hash, table.length); for (intry <k, v> e = table [i]; e! = null; e = e.next) {объект k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldvalue = e.value; e.value = значение; e.recordaccess (это); вернуть OldValue; }} modcount ++; AddEntry (хэш, ключ, значение, i); вернуть null;}В этом методе сначала определите, является ли ключ нулевой. Если да, вызовите метод putfornullkey (), что означает, что HashMap позволяет ключу быть нулевым (на самом деле, значение может быть). Если не null, вычислите значение хэша и получите индекс в таблице. Затем перейдите в соответствующий связанный список, чтобы запросить, существует ли тот же ключ. Если он уже существует, значение будет напрямую обновлено. В противном случае, вызов AddEntry () метод для вставки.
Взгляните на метод Putfornullkey ():
private v putfornullkey (v value) {for (intry <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) {v oldValue = e.value; e.value = значение; e.recordaccess (это); вернуть OldValue; }} modcount ++; AddEntry (0, NULL, значение, 0); вернуть null;}Можно видеть, что когда ключ является нулевым, значение будет обновлено, если оно будет существовать, в противном случае AddEntry () будет вызвана для вставки.
Ниже приводится реализация метода AddEntry ():
void AddEntry (int hash, k -ключ, v Значение, int bucketIndex) {if ((size> = threshold) && (null! = table [bucketindex])) {resize (2 * table.length); хэш = (null! = ключ)? хэш (ключ): 0; bucketindex = indexfor (hash, table.length); } createEntry (хэш, ключ, значение, bucketIndex);} void createEntry (int hash, k -ключ, v Значение, int bucketIndex) {intpirt <K, v> e = table [bucketIndex]; Таблица [BucketIndex] = Новая запись <> (хэш, ключ, значение, E); размер ++;}Сначала определите, будет ли расширить емкость (расширяющаяся емкость пересчет значения индекса и скопируйте элемент), затем вычислите индекс массива и, наконец, вставьте элемент, используя метод вставки заголовка в createentry ().
Получите операцию
public v get (object key) {if (key == null) return getFornullKey (); Inpit <K, v> intry = getEntry (key); return null == запись? null: entry.getValue ();} private v getFornullKey () {for (entry <k, v> e = table [0]; e! = null; e = e.next) {if (e.key == null) return e.value; } return null;} окончательная запись <k, v> getEntry (ject key) {int hash = (key == null)? 0: хэш (ключ); for (inpit <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;}Это проще, чем put (). Вам также необходимо определить, является ли ключ нулевым, а затем запрос обхода связанного списка.
Оптимизация производительности
HashMap - это эффективная и универсальная структура данных, которую можно увидеть повсюду в каждой программе Java. Давайте сначала представим некоторые базовые знания. Как вы также можете знать, HashMap использует методы HashCode () и Equals () ключа для разделения значений на разные ведра. Количество ведра обычно немного больше, чем количество записей на карте, так что каждое ведро будет включать меньше значений (предпочтительно). При поиске через клавиши мы можем быстро найти ведро (используя HashCode (), чтобы модуть количество ведер) и объекта, который мы ищем в постоянное время.
Вы уже должны знать все это. Вы также можете знать, что хэш -столкновения могут оказать катастрофическое влияние на производительность HashMap. Если несколько значений hashcode () попадают в одно и то же ведро, эти значения хранятся в связанном списке. В худшем случае все клавиши сопоставлены в одно и то же ведро, поэтому хэшмап дегенерирует в связанный список - время поиска от O (1) до O (n). Давайте сначала проверим производительность HashMap в Java 7 и Java 8 при нормальных обстоятельствах. Чтобы контролировать поведение метода HashCode (), мы определяем класс ключа следующим образом:
Ключ класса реализует сопоставимые <key> {private final int value; key (int value) {this.value = value;}@переопределение int compareto (key o) {return integer.compare (this.value, o.value);}@overridepublic boolean equals (object o) {if this o) return true; if (o == nUll o.getClass ()) return false; key key = (key) o; return value == key.value;}@overdepublic int hashcode () {return value;}}Реализация класса ключевого класса довольно стандартная: она переписывает метод Equals () и обеспечивает довольно приличный метод HashCode (). Чтобы избежать чрезмерного GC, я кэшировал об неизменное ключевое объект вместо того, чтобы начать создавать его снова каждый раз:
Ключ класса реализует сопоставимые <Key> {открытый класс класса {public Static Final int max_key = 10_000_000; Приватный статический конечный ключ [] keys_cache = new Key [max_key]; static {for (int i = 0; i <max_key; ++ i) {keys_cache [i] = new Ceail (i);} public Static of at at quept at vitue of at at vitued of (int artact)}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} Keys_cache [value];}Теперь мы можем начать тестирование. Наш эталон использует непрерывные значения ключей для создания хэшмапов разных размеров (множитель для 10, от 1 до 1 миллиона). В тесте мы также будем использовать клавиши для поиска и измерения времени, которое необходимо для хэшмапов разных размеров:
Импорт com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper.simplebenchmark; public class mapbenchmark extends simplebenchmark {private hashmap <ключ, Integer> map; @paramprivate int mapsize; @overrideprotected void setup () throws exection {map = nefficate; Hashmap <> (mapsize); for (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void timemapget (int reps) {for (int i = 0; i <reps; i ++) {map.get (keys.of (i % mapsize);Интересно, что в этом простой hashmap.get () Java 8 на 20% быстрее Java 7. Общая производительность также довольно хороша: хотя в Hashmap есть миллион записей, один запрос занял только менее 10 наносекунд, что составляет около 20 циклов процессора на моей машине. Очень шокирует! Но это не то, что мы хотим измерить.
Предположим, что есть плохой ключ, он всегда возвращает одно и то же значение. Это худший сценарий, и вы вообще не должны использовать HashMap:
Ключ класса реализует сопоставимые <Key> {//...@overridePublic int hashcode () {return 0;}}Результаты Java 7 ожидаются. По мере роста размер хэшмапа, накладные расходы метода get () становится больше и больше. Поскольку все записи находятся в сверхточном связанном списке в одном и том же ведре, поиск в среднем в одной записи требует прохождения половины списка. Следовательно, из фигуры можно увидеть, что его сложность времени - O (n).
Тем не менее, Java 8 работает намного лучше! Это кривая бревна, поэтому его производительность лучше на порядок. Несмотря на худший сценарий суровых хэш -столкновений, этот же эталон обладает временной сложностью в JDK8 O (logn). Если вы посмотрите на кривую JDK 8, это будет яснее. Это логарифмическое линейное распределение:
Почему существует такое отличное улучшение производительности, хотя здесь используется большой символ O (Big O описывает асимптотическую верхнюю границу)? Фактически, эта оптимизация была упомянута в JEP-180. Если запись в ведре слишком велика (в настоящее время treeify_threshold = 8), HashMap динамически заменит ее на специальную реализацию TreeMap. Это приведет к лучшим результатам, O (logn), неплохому O (n). Как это работает? Записи, соответствующие ключу, у которого есть конфликты впереди, просто добавляются в связанный список, и эти записи можно найти только через проезд. Однако после превышения этого порога HashMap начинает обновлять список до двоичного дерева, используя значение хэша в качестве переменной ветви дерева. Если два значения хэш не равны, а указывают на одно и то же ведро, более крупное будет вставлено в правую поддерево. Если значения хэша равны, HashMap надеется, что значение ключа лучше всего реализовано сопоставимым интерфейсом, чтобы его можно было вставить по порядку. Это не обязательно для ключа HashMap, но, конечно, это лучше всего, если он реализован. Если этот интерфейс не будет реализован, вы не должны ожидать достижения улучшения производительности в случае серьезных хеш -столкновений.
Каково использование этого улучшения производительности? Например, злонамеренная программа, если она знает, что мы используем алгоритм хеширования, она может отправить большое количество запросов, что приведет к серьезным хэш -столкновению. Затем постоянный доступ к этим ключам может значительно повлиять на производительность сервера, что приводит к отказу в атаке обслуживания (DOS). Прыжок от O (n) к O (LOGN) в JDK 8 может эффективно предотвратить аналогичные атаки, а также немного повысить предсказуемость производительности HashMap. Я надеюсь, что это улучшение в конечном итоге убедит вашего босса согласиться перейти на JDK 8.
Среда, используемая для теста: Intel Core I7-3635QM @ 2,4 ГГц, 8 ГБ памяти, жесткий диск SSD, используя параметры JVM по умолчанию, работая в 64-битной системе Windows 8.1.
Суммировать
Основная реализация HashMap аналогична выше, и, наконец, сделано резюме: