Большинство разработчиков Java используют карту, особенно HashMap. HashMap - это простой, но мощный способ хранения и получения данных. Но сколько разработчиков знает, как работает HashMap внутри? Несколько дней назад я прочитал много исходного кода java.util.hashmap (включая Java 7 и Java 8), чтобы получить глубокое понимание этой основной структуры данных. В этом посте я объясню реализацию java.util.hashmap, опишу новые функции, добавленные в реализации Java 8, и обсуждать производительность, память и некоторые известные проблемы при использовании Hashmap.
Внутренняя хранение
Класс Java Hashmap реализует интерфейс <K, V>. Основные методы в этом интерфейсе включают:
V PUT (k клавиша, v Значение) v get (клавиша объекта) v Удалить (клавиша объекта) Boolean содержит (клавиша объекта)
HashMap использует внутреннюю запись класса <K, V> для хранения данных. Этот внутренний класс-простая пара ключей с двумя дополнительными данными:
Ссылка на другую запись, так что HashMap может хранить объекты, такие как списки ссылок.
Значение хэша, используемое для представления ключа. Хранение этого значения может предотвратить восстановление хеш -значения, соответствующее ключу каждый раз, когда он необходим.
Вот часть кода для входа <K, V> под Java 7:
Статическая запись класса <K, V> реализует Map.Entry <K, v> {final K Key; v value; intry <K, v> next; int hash;…}HashMap сохраняет данные в несколько однонаправленных списков (иногда называемые ведрами или орбинами контейнеров). Все списки зарегистрированы в массиве входа (вход <K, v> [] массив), а длина по умолчанию этого внутреннего массива составляет 16.
На следующем рисунке описывается внутреннее хранилище экземпляра HashMap, которое содержит массив нулевых объектов. Каждый объект подключен к другому объекту, создавая таким образом связанный список.
Все ключи с одинаковым значением хэша будут размещены в одном и том же связанном списке (ведре). Ключи с разными хэшами могут оказаться в одном и том же ведре.
Когда пользовательские вызовы ставят (k -ключ, значение v) или get (ключ объекта), программа вычисляет индекс ведра, в котором должен быть объект. Затем программа будет итерация над соответствующим списком, чтобы найти объект входа с той же ключом (с использованием метода equals () ключа).
В случае вызова get () программа вернет объект записи, соответствующий значению (если объект записи существует).
Для вызова для полоки (k-ключа, v Значение), если объект входа уже существует, программа заменит значение новым значением, в противном случае программа создаст новую запись (ключ и значение в параметре) в заголовке одностороннего связанного списка.
Индекс ведра (связанный список) генерируется через 3 шага карты:
Сначала получите хэш -код ключа.
Программа повторяет хэш -код, чтобы заблокировать плохие хэш -функции для ключей, потому что это может поместить все данные на один и тот же индекс (ведро) внутреннего массива.
Программа принимает дублированный хеш -код и использует биту маски длины массива (минимум 1) для него. Эта операция гарантирует, что индекс не будет больше, чем размер массива. Вы можете думать об этом как о расчетной оптимизированной функции модуля.
Вот исходный код для генерации индекса:
// Функция «перефразировать» в Java 7, которая принимает хешкоду ключевого int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); вернуть H ^ (h >>> 7) ^ (H >>> 4);} // функция "rehash" в java 8, что непосредственно принимает ключевую конечную клавишу) {intul -key h hash (объект in h hah (объект) {intul) {intul) {intul) {intul) {intul)? 0: (h = key.hashcode ()) ^ (h >>> 16);} // функция, которая возвращает индекс из перефразированного хэшстатического int indexfor (int h, int length) {return h & (длина-1);}Чтобы работать более эффективно, размер внутреннего массива должен быть силой 2. Посмотрим, почему:
Предполагая, что длина массива составляет 17, значение маски составляет 16 (длина массива-1). Бинарное представление 16 составляет 0… 010000, так что для любого значения h результат «H & 16» составляет 16 или 0. Это означает, что массивы длины 17 могут применяться только к двум ведра: одно равно 0, а другое - 16, что не очень эффективно. Но если вы установите длину массива на мощность 2, например, 16, то побитовая индексация работает на «H & 15». Бинарное представление 15 составляет 0… 001111, а значение, выводное по формуле индекса, может варьироваться от 0 до 15, так что можно полностью использовать массив длины 16. Например:
Если H = 952, его двоичное представление равно 0..01110111000, а соответствующий индекс равен 0… 01000 = 8
Если H = 1576, его двоичное представление равно 0,011000101000, а соответствующий индекс равен 0… 01000 = 8
Если H = 12356146, его двоичное представление равно 0,0101111001000101010010, соответствующий индекс равен 0… 00010 = 2
Если H = 59843, его двоичное представление равно 0,01110100111000011, его соответствующий индекс равен 0… 00011 = 3
Этот механизм прозрачен для разработчика: если он выберет хэшмап длины 37, карта автоматически выберет следующее значение мощности, превышающее 37 (64) в качестве длины внутреннего массива.
Автоматически изменять размер
После получения индекса методы get (), put () или remove () будут доступны к соответствующему связанному списку, чтобы увидеть, существует ли объект входа для указанного ключа. Без модификации этот механизм может вызвать проблемы с производительностью, так как этот метод требует итерации по всему списку, чтобы увидеть, существует ли объект входа. Предположим, что длина внутреннего массива берет значение по умолчанию 16, и вам необходимо хранить 200 000 записей. В лучшем случае будет 125 000 объектов входа на список связанного списка (2 000 000/16). Методы get (), remove () и put () требуют 125 000 итераций каждый раз, когда они выполняются. Чтобы избежать этого, HashMap может увеличить длину внутреннего массива, что обеспечивает сохраняется лишь несколько входных объектов в связанном списке.
Когда вы создаете HashMap, вы можете указать начальную длину и Fultfactor через следующий конструктор:
</pre> public hashmap (int initialcapacity, float loadfactor) <pre>
Если вы не указываете параметры, значение исходной кости по умолчанию составляет 16, а значение по умолчанию по умолчанию - 0,75. Первоначальная капота представляет длину связанного списка внутреннего массива.
Когда вы используете метод POT (…), чтобы добавить новую пару клавишных значений на карту, метод проверяет, должна ли увеличение длины внутреннего массива. Чтобы достичь этого, карта хранит 2 данные:
Размер карты: он представляет количество записей в HashMap. Мы обновляем значение, когда вставляем или удаляем его в хэшмап.
Порог: он равен длине внутреннего массива*LoadFactor, и этот порог также будет обновляться в одно и то же время каждый раз, когда длину внутренней массивы регулируется.
Перед добавлением нового объекта входа метод POT (…) проверяет, превышает ли размер текущей карты, чем порог. Если он больше, чем порог, он создает новый массив с вдвое больше текущего внутреннего массива. Поскольку размер нового массива изменился, функция индекса (то есть результат работы бита, который возвращает «хэш -значение ключа и (длина массива -1)») также изменяется. Изменение размера массива создает два новых ведра (связанные списки) и переназначает все существующие объекты ввода в ведро. Целью регулировки размера массива является уменьшение размера связанного списка, тем самым сокращая время выполнения POT (), REAME () и GET () Методы. Для всех входных объектов, соответствующих ключам с одинаковым значением хэша, они выделяются на одно и то же ведро после изменения размера. Однако, если значения хэш двух входных объектов различны, но они были на одном ведре раньше, то после регулировки нет никакой гарантии, что они все еще находятся на одном ведре.
Это изображение описывает ситуацию в внутренних массивах до погашения и после регулировки. Перед настройкой длины массива, чтобы получить объект Entry E, карта необходимо обратить внимание на связанный список, содержащий 5 элементов. После регулировки длины массива тот же метод get () должен только пройти связанный список, содержащий 2 элемента, поэтому скорость выполнения метода get () после регулировки длины массива увеличивается в 2 раза.
Безопасность нити
Если вы уже очень хорошо знакомы с HashMap, вы определенно знаете, что это не безопасно нить, но почему? Например, предположим, что у вас есть поток для писателя, который будет вставлять только существующие данные в карту, поток считывателя, который будет считывать данные с карты, так почему это не работает?
Поскольку в соответствии с механизмом автоматического изменения размера, если поток пытается добавить или получить объект, карта может использовать старое значение индекса, так что новое ведро, в котором находится объект входа, не будет найдено.
В худшем случае, когда 2 потока вставляют данные одновременно, 2 вызовы put () начнутся одновременно, а массив автоматически изменит размер. Поскольку два потока изменяют связанный список одновременно, возможно, что карта выходит во внутреннем цикле связанного списка. Если вы попытаетесь получить данные из списка с внутренним циклом, метод get () никогда не закончится.
Hashtable обеспечивает реализацию безопасной потока, которая предотвращает появление вышеупомянутого. Однако, поскольку все операции с синхронными CRUD очень медленные. Например, если вызовы потока 1 получают (key1), то вызовы потока 2 get (key2), и вызовы 2 потока 2 get (key3), а затем в указанное время только 1 поток может получить свое значение, но все 3 потока могут одновременно получить доступ к этим данным.
Начиная с Java 5, у нас есть лучшая и защищенная от никота реализация Hashmap: concurrenthashmap. Для одновременной карты только синхронизируются только ведра, поэтому, если несколько потоков не используют одно и то же ведро или изменять размер внутреннего массива, они могут вызывать методы get (), rement () или put () одновременно. В многопоточном приложении этот подход является лучшим выбором.
Инвариантность облигаций
Почему это хорошая реализация, чтобы использовать строки и целые числа в качестве ключей к HashMap? Главным образом потому, что они неизменны! Если вы решите создать класс самостоятельно в качестве ключа, но вы не можете гарантировать, что класс неизменен, вы можете потерять данные внутри Hashmap.
Давайте посмотрим на следующие варианты использования:
У вас есть ключ, внутреннее значение которого - «1».
Если вы вставляете объект в хэшмап, его ключ - «1».
HashMap генерирует значения хэша из хэш -кода ключа (то есть «1»).
Карта хранит это хеш -значение в недавно созданной записи.
Вы меняете внутреннее значение ключа и меняете его на «2».
Значение хэш -ключа изменилось, но Hashmap не знает этого (потому что старое значение хэш хранится).
Вы пытаетесь получить соответствующий объект с помощью модифицированного ключа.
Карта вычисляет значение хэша нового ключа (то есть «2»), чтобы найти связанный список (ведро), где находится объект входа.
Случай 1: Поскольку вы изменили ключ, карта попытается найти объект входа в неправильное ведро, но он не найден.
Случай 2: Вам повезло, что ведро, сгенерированное модифицированным ключом, и ведро, сгенерированное старым ключом, одинаковы. Затем карта пройдет связанный список, и был найден объект входа с тем же ключом. Но чтобы найти ключ, карта сначала сравнит значение хэша ключа, вызывая метод equals (). Поскольку модифицированный ключ будет генерировать различные значения хэша (старые значения хэша хранятся в записи), то MAP не может найти соответствующий объект записи в связанном списке.
Вот пример Java, в котором мы вставляем две пары клавиш в карту, а затем я изменяю первую клавишу и пытаюсь получить два объекта. Вы обнаружите, что только второй объект, возвращенный с карты, первый объект был «потерян» в Hashmap:
public class mitablekeytest {public static void main (string [] args) {class mykey {integer i; public void seti (Integer i) {this.i = i;} public mykey (integer i) {this.i = i;}@overridepublic int int int () boble obj Mykey) {return i.equals (((mykey) obj) .i);} elsereturn false;}} map <mykey, string> mymap = new hashmap <> (); mykey key1 = new mykey (1); mykey key2 = new mykey (2); mymap.put (key1, "test" + 1); key1key1.seti (3); string test1 = mymap.get (key1); string test2 = mymap.get (key2); system.out.println ("test1 =" + test1 + "test2 =" + test2);}}Вывод вышеуказанного кода - "test1 = null test2 = test 2". Как мы и ожидаем, MAP не имеет возможности получить строку 1, соответствующую измененному ключу 1.
Улучшения в Java 8
В Java 8 внутренняя реализация в HashMap была сильно изменена. Действительно, Java 7 использует 1000 строк кода для его реализации, в то время как Java 8 использует 2000 строк кода. Большая часть того, что я описал ранее, все еще верна в Java 8, за исключением использования связанных списков для сохранения объектов ввода. В Java 8 мы все еще используем массивы, но он будет сохранен в узле, который содержит ту же информацию, что и предыдущий объект записи, а также использует связанный список:
Вот часть кода, который реализует узел в Java 8:
Статический класс узел <K, V> реализует Map.Entry <K, v> {final int hash; final k key; v value; node <k, v> next;Так в чем же большая разница по сравнению с Java 7? Ну, узел может быть расширен до TreeNode. TreeNode - это структура данных красного и черного дерева, которое может хранить больше информации, поэтому мы можем добавить, удалять или получить элемент под сложности O (log (n)). В следующем примере описывается вся информация, сохраненная TreeNode:
Статический окончательный класс TREENODE <K, V> Extends LinkedHashmap.Entry <K, V> {Final Int Hash; // унаследован от узла <K, v> final k -ключа; // унаследован от узла <k, v> v Значение; // унаследован от узла <K, v> узла <K, V> Далее; // Унаследован от узла <K, v> inpit <K, v> до, после; // унаследован от LinkedHashmap.Entry <K, v> parent; treeNode <K, v> слева; TreeNode <K, v> right; treeNode <K, v> prev; boolean red;Красные и черные деревья-это бинарные бинарные деревья. Его внутренний механизм гарантирует, что его длина всегда будет журналом (N), независимо от того, добавляем ли мы или удаляем узлы. Наиболее важным преимуществом использования этого типа дерева является то, что это тот случай, когда многие данные во внутренней таблице имеют одинаковый индекс (ведро). В настоящее время сложность поиска дерева является O (log (n)), а для связанного списка сложность O (n) для выполнения той же операции.
Как вы можете видеть, мы храним больше данных в дереве, чем связанные списки. Согласно принципу наследования, внутренняя таблица может содержать узел (связанный список) или TreeNode (красное и черное дерево). Oracle решает использовать эти две структуры данных в соответствии со следующими правилами:
- Для указанного индекса (ведра) во внутренней таблице, если количество узлов превышает 8, связанный список будет преобразован в красное и черное дерево.
- Для указанного индекса (ведра) во внутренней таблице, если количество узлов меньше 6, красное и черное дерево будет преобразовано в связанный список.
Это изображение описывает внутренний массив в хэшмапе Java 8, который содержит как дерево (ведро 0), так и связанные списки (ведро 1, 2 и 3). Ведро 0 - это структура дерева, потому что оно содержит более 8 узлов.
Память над головой
Java 7
Использование HashMap потребляет некоторую память. В Java 7 Hashmap инкапсулирует пары ключей в объекты ввода, объект входа содержит следующую информацию:
Ссылка на следующую запись предварительно рассчитанного значения хэша (целое число)
Ссылка на ключ и ссылка на значение
Кроме того, Hashmap в Java 7 использует внутренний массив объектов входа. Предположим, что HashMap Java 7 содержит N -элементы, а его внутренний массив обладает емкостью, тогда дополнительное потребление памяти связано:
sizeof (Integer)* n + sizeof (ссылка)* (3* n + c)
в:
Размер целого числа составляет 4 байта
Размер ссылки зависит от JVM, операционной системы и процессора, но обычно составляет 4 байта.
Это означает, что общие накладные расходы на память обычно составляют 16 * N + 4 * байты емкости.
Примечание. После автоматического изменения карты значение емкости является следующей наименьшей мощностью 2 больше, чем N.
Примечание: начиная с Java 7, HashMap принимает ленивый механизм загрузки. Это означает, что даже если вы указываете размер для HashMap, используемый внутренний массив (потребление 4*байтов емкости), который не выделяется в памяти, прежде чем мы впервые используем метод put ().
Java 8
В реализациях Java 8 вычислительное использование памяти становится более сложным, поскольку узел может хранить те же данные, что и вход, или добавлять 6 ссылок и логическое свойство (указывая, является ли это TreeNode).
Если все узлы являются просто узлами, то память, потребляемая Hashmap Java 8, такая же, как и Hashmap Java 7.
Если все узлы являются TreeNode, то память, потребляемая Java 8 Hashmap, становится:
N * sizeof (integer) + n * sizeof (boolean) + sizeof (ссылка) * (9 * n + емкость)
В большинстве стандартных JVMS результат вышеуказанной формулы составляет 44 * N + 4 * байты емкости.
Проблемы с производительностью
Асимметричная HashMap против сбалансированной HashMap
В лучшем случае методы get () и put () имеют сложность O (1). Однако, если вы не заботитесь о хэш -функции ключа, ваш put () и get () методы могут выполняться очень медленно. Эффективное выполнение методов put () и get () зависит от данных, выделяемых на различные индексы внутреннего массива (ведра). Если функция хэш ключа не разработана должным образом, вы получите асимметричный раздел (независимо от размера внутренних данных). Все методы put () и get () будут использовать самый большой связанный список, который будет медленно выполнять, поскольку он требует итерации по всем записям в связанном списке. В худшем случае (если большая часть данных находится на одном ведре), ваша сложность времени становится O (n).
Вот визуальный пример. Первый график описывает асимметричный HashMap, а второй график описывает выравниваемый HashMap.
Skewedhashmap
В этом асимметричном Hashmap потребуется время, чтобы запустить методы get () и put () на ведро 0. Получение записи K занимает 6 итераций.
В этом сбалансированном хэшмапе требуется всего 3 итерации, чтобы получить запись K. Эти два хэшмапа хранят одинаковое количество данных, а внутренние массивы имеют одинакового размера. Единственная разница - это хэш -функция ключа, которая используется для распространения записей по разным ведра.
Вот экстремальный пример, написанный на Java, в котором я использую хэш -функцию для размещения всех данных в один и тот же связанный список (ведро), а затем я добавил 200 000 000 деталей данных.
открытый тест класса {public static void main (string [] args) {class mykey {integer i; public mykey (integer i) {this.i = i;}@overiDepublic int hashcode () {return 1;}@overridepublic boolean equals (Object obj) {…}} date = new Date (mymeme); Hashmap <> (2_500_000,1); for (int i = 0; i <2_000_000; i ++) {mymap.put (new mykey (i), "test"+i);} date end = new Date (); System.out.println ("Duding (ms)"+(end.gettime ()-new.gettime (););Моя конфигурация машины-Core I5-2500K @ 3,6G, и для работы под Java 8U40 уходит более 45 минут (я остановил процесс через 45 минут). Если я запускаю тот же код, но я использую хэш -функцию так:
@OverridePublic int hashcode () {int key = 2097152-1; вернуть клавишу+2097152*i;}Для его запуска требуется 46 секунд, что намного лучше, чем раньше! Новая хэш -функция более разумна, чем старая хэш -функция при обработке хэш -разделов, поэтому вызов метода put () быстрее. Если вы запускаете один и тот же код сейчас, но используйте хэш -функцию ниже, он обеспечивает лучший хэш -раздел:
@OverridePublic int hashcode () {return i;}Теперь это займет всего 2 секунды!
Я надеюсь, что вы сможете понять, насколько важны хэш -функции. Если вы проведете тот же тест на Java 7, первое и второе будет хуже (потому что метод put () в Java 7 имеет сложность O (n), в то время как сложность в Java 8 имеет O (log (n)).
При использовании HashMap вам нужно найти хэш -функцию для ключей, которые могут распространять ключи до наиболее вероятного ведра. Для этого вам нужно избегать хэш -конфликтов. Строковой объект является очень хорошим ключом, потому что он имеет хорошую хэш -функцию. Целое число также хорошо, потому что его хэш - это его собственная ценность.
Изменение размера накладных расходов
Если вам нужно хранить большой объем данных, вы должны указать начальную емкость при создании HashMap, который должен быть близок к вашему желаемому размеру.
Если вы этого не сделаете, карта будет использовать размер по умолчанию, то есть 16, а значение факторной загрузки составляет 0,75. Первые 11 вызовов to put () будет очень быстрым, но 12 -й (16*0,75) вызов создаст новый внутренний массив с длиной 32 (и соответствующий связанный список/дерево), а метод 1 -й по 22 -й вызов () будет очень быстрым, но 23 -й (32*0,75) вызов воссоздает (снова) новый Array, и длину в Arr.Bleble. Затем операция внутреннего изменения размера будет запускается, когда метод put () называется 48 -й, 96 -й, 192 -й…. Если объем данных не является большим, операция по восстановлению внутреннего массива будет очень быстрой, но когда количество данных увеличено, потраченное время может варьироваться от секунд до минут. Указав желаемый размер карты во время инициализации, вы можете избежать потребления, вызванного изменением размера.
Но здесь также есть недостаток: если вы установите массив очень большим, например, 2^28, но вы просто используете 2 26 ведра в массиве, то вы будете тратить много памяти (около 2^30 байтов в этом примере).
в заключение
Для простых вариантов использования вам не нужно знать, как работает хэшмап, потому что вы не увидите разницу между O (1), O (n) и O (log (n)). Но всегда полезно понять механизм этой часто используемой структуры данных. Кроме того, это типичный вопрос для интервью для позиций разработчика Java.
Для больших объемов данных становится очень важным понимать, как работает хэшмап, и понимать важность хэш -функции для ключей.
Я надеюсь, что эта статья поможет вам глубоко понять реализацию HashMap.