Дизайн и оптимизация HashMap | Написание темы

Эта статья участвовала в третьем треке "написание темы" тренировочного лагеря для создателей Nuggets. Подробнее см.:Dig Li Project | Идет третий этап тренировочного лагеря создателя, «написание» личного влияния.

📖Предисловие

手执烟花以谋生心怀诗意以谋爱

Независимо от того, запишу я это или нет, в бесконечных годах прошлого и будущего все равно будут люди, которые поднимутся, некоторые падут, некоторые станут героями, некоторые выступят в роли клоунов, некоторые встанут, и некоторые будут потеряны. Но все, что вам нужно сделать, это: «Будьте дисциплинированы в процветании, исцеляйте себя в падении, не отказывайтесь от своей совести на пути к заработку, не теряйте самой серьезности на пути к любви, на этот раз я». м стою на ветру, пуская всюду туман».

🚀`HashMap`принципы дизайна

1. HashMap设计思路：

Карта — это контейнер, который хранит данные в парах ключ-значение, аHashMapключ-значениеKeyизhashcodevalue для организации хранилища таким образом, чтобы ключ-значениеkeyДоступ к данным.
Для пар ключ-значениеHashMapВнутри он будет инкапсулирован в соответствующийEntryобъект, то естьEntryОбъект — это организация пар ключ-значение;
Для каждого объекта,JVMсоздастhashcodeстоимость.HashMapхранить пары ключ-значениеEntry, согласно сKeyизhashcodeзначение в определенном отношении отображения определяет, какая пара ключ-значение должна бытьEntryсохранить вHashMapгде в
когда прошелKeyКогда значение принимает данные, то согласноKeyстоило тогоhashcodeа также内部映射条件, прямо кKeyсоответствующийValueгде хранится значение, что может быть очень эффективноValueзначение выносится.

💖`HashMap`Дизайн хэш-функции для

hashФункция состоит в том, чтобы стать первымkeyизhashcode, является 32-битнымintзначение, то пустьhashcodeСтаршие 16 бит и младшие 16 бит объединяются XOR. делать

Также называемая функцией возмущения, есть две причины для такой конструкции.

быть как можно нижеhashСтолкновение, чем более рассредоточено, тем лучше;
Алгоритм должен быть максимально эффективным, потому что это высокочастотная операция, поэтому используются битовые операции;

👏 Что такое хэш?

    Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的 `输入`，通过散列算法变换成固定长度的 `输出`，该输出就是散列值。ok，这样的定义可能比较抽象。咱们结合上面提到的方案二的例子一句一句解释。

Например, имя человека является входом произвольной длины. Z-Zhangsan 11; L-Li Si 22; W-Wang Wu 33
Затем перейдите прямо в категорию Z, чтобы найти его, и отправьте в душу. Но если есть много людей, чьи имена начинаются на Z, например, Z-Zhao Liu 44, Z-Zhou Qi 55, когда у меня больше телефонных номеров, мне нужно найти их много раз. —— Я делаю классификацию по заглавной букве имени.Этот метод деления можно рассматривать как алгоритм хеширования.
Наконец, разделите книгу по инициалам и запишите номера телефонов - вывод фиксированной длины, т.е. у меня есть все телефонные звонки во всех 26 категориях. Тогда эти 26 букв являются хеш-значением.

🐱‍🏍 `HashMap`структуры данных (JDK 1.8)

В этой статье говоритсяJDK1.8Версия, использующая массив + связанный список красно-черное дерево внутри

существуетJdk1.8серединаHashMapВнесены некоторые изменения в реализацию优化, давайте посмотрим на эти изменения:数据结构的存储由数组+链表的方式, который меняется на数组+链表+红黑树的存储方式, когда длина связанного списка превышает阈值（8）когда будет链表转换为红黑树. Производительность была дополнительно улучшена.
Массив: диапазон хранения массива непрерывен, что занимает много памяти, поэтому сложность пространства очень велика. Но временная сложность бинарного поиска массива невелика, O(1), характеристики массива: легко адресовать, трудно вставлять и удалять; Сложность пространства: относится к пространству памяти, необходимому для выполнения алгоритма. Временная сложность: количество вычислительных усилий, необходимых для выполнения алгоритма.
Связанный список: интервал хранения связанного списка является дискретным, а использование памяти относительно свободное, поэтому пространственная сложность невелика, но временная сложность очень велика, достигая O (N). Характеристики связанного списка: трудно адресовать, легко вставлять и удалять.
Красно-черное дерево:

😎`JDK1.8`правильно`HashMap`Каковы основные оптимизации?

Массив + связанный список изменен на массив + связанный список или красно-черное дерево;
Метод вставки связанного списка был изменен с метода вставки головы на метод вставки хвоста, Проще говоря, при вставке, если в позиции массива уже есть элемент, 1.7 добавит новый элемент Элементы помещаются в массив, и исходный узел используется в качестве узла-преемника нового узла 1.8 Пройдите по связанному списку и поместите элемент в конец связанного списка;
При расширении 1.7 необходимо повторно хэшировать элементы в исходном массиве и найти их в новом массиве.1.8 использует более простую логику суждения. Редактировать, позиция без изменений или индекс + старый размер емкости;
При вставке 1.7 сначала решить, требуется ли расширение, а затем вставить, 1.8 сначала вставить, а затем решить, требуется ли расширение после вставки;

✨Почему эти оптимизации

предотвратитьhashКонфликт, длина связанного списка слишком велика, а временная сложность изменена сO(n)УронитьO(logn) ;
Поскольку метод вставки заголовка 1.7 приведет к тому, что связанный список будет перевернут, когда метод вставки заголовка будет развернут, и в многопоточной среде будет создан цикл; Поток A вставляет узел B, а также вставляется поток B. Когда мощности недостаточно, он начинает расширяться и перезапускаетсяhash, поместите элемент, используйте метод заголовка, Узел B, пройденный позже, помещается в головку, которая образует кольцо, как показано на следующем рисунке:

1.7 вызов расширенияtransfer код следующим образом:

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	for (Entry<K,V> e : table) {
		while(null != e) {
			Entry<K,V> next = e.next;
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			} 
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i]; //A线程如果执行到这一行挂起，B线程开始进行扩容
			newTable[i] = e;
			e = next;
		}
	}
}

Почему 1.8 не нужно переустанавливать при расширении емкости?hashВы можете напрямую определить местоположение исходного узла в новых данных.
- Это связано с тем, что расширение должно удвоить размер исходного массива, а маска, используемая для вычисления позиции массива, — это всего лишь еще одна единица в старшем порядке. Как насчет решения?
- Длина до расширения равна 16, двоичный файл n-1, используемый для вычисления (n-1) и хэша, равен 0000 1111, а двоичный файл после расширения до 32 имеет больше старших битов. 1 это 0001 1111.
- Поскольку это операция &, 1 и любое число & являются самими собой, поэтому есть два случая, как показано на следующем рисунке: Старший четвертый бит исходного хэш-кода данных равен 0 и случай, когда старший бит равен 1;
- Старший бит четвертой цифры равен 0, значение повторного хеширования остается неизменным, четвертая цифра равна 1, а значение повторного хэширования больше исходного на 16 (емкость старого массива)

🎉 Наконец-то

Дополнительные справочные сообщения в блоге см. здесь:Блог Чен Юнцзя
Друзья, которым нравятся блогеры, могут подписаться, поставить лайк и продолжать обновлять, хе-хе!

📖Предисловие

🚀HashMapпринципы дизайна

💖HashMapДизайн хэш-функции для