Мы знаем, что хэш -таблица является очень эффективной структурой данных, и отличная конструкция хэш -функции может сделать операции с добавлением, удалением, модификацией и поиском на уровне O (1). Java предоставляет нам готовую хэш-структуру, то есть класс HashMap. В предыдущей статье я представил класс HashMap и знал, что все его методы не были синхронизированы, поэтому он не безопасен в многопоточной среде. С этой целью Java предоставляет нам еще один хэштибельный класс, который очень прост и груб при обработке многопоточной синхронизации, то есть для блокировки всех его методов, используя синхронизированное ключевое слово на основе HashMap. Хотя этот метод прост, он приводит к проблеме, то есть только один поток может одновременно управлять хэш -таблицей. Даже если эти потоки являются только операциями по чтению, они должны быть в очереди, что значительно влияет на производительность в высококонкурентных многопоточных средах. Concurrenthashmap, представленный в этой статье, предназначен для решения этой проблемы. Он использует сегментированные блокировки для мелкозернистых замков, так что несколько потоков могут одновременно использовать хэш-таблицу, что значительно повышает производительность. Следующий рисунок представляет собой схематическую диаграмму его внутренней структуры.
1. Какие переменные члена имеют concurrenthashmap?
// По умолчанию емкость инициализации по умолчанию Static Final int default_initial_capacity = 16; // Статический коэффициент загрузки по умолчанию. Min_segment_table_capacity = 2; // максимальное количество блокировки сегмента Статическое окончательное окончательное значение int max_segments = 1 << 16; // Количество повторных перезагрузков перед блокировкой статической конечной int int int_before_lock = 2; // Значение маски финального блокировки сегмента
Прежде чем читать эту статью, я считаю, что читатели не могут понять конкретное значение и функцию этих переменных членов, но читателям рекомендуется терпеливо читать. Роль этих переменных членов будет введена один за другим в конкретных сценариях позже. Здесь читатели должны оставить знакомый взгляд на эти переменные участника. Тем не менее, есть еще некоторые переменные, которые нам нужно знать сейчас. Например, массив сегмента представляет собой набор блокировки сегмента, уровень параллелизма представляет количество блокировки сегмента (что также означает, сколько потоков может работать одновременно), способность инициализации представляет собой способность всего контейнера, а коэффициент загрузки представляет уровень полного элемента контейнера.
2. Какова внутренняя структура блокировки сегмента?
// сегмент блокировки Статический окончательный сегмент класса <K, V> extends Reentrantlock реализует serializable {// максимальное количество спинового номера Статическое окончательное окончательное значение int max_scan_retries = runtime.getRuntime (). Доступные processors ()> 1? 64: 1; // таблица таблицы переходной таблицы. // общее количество элементов переходное количество int count; // количество модификаций Transient int modcount; // Порог элемента переходного порога int; // коэффициент загрузки конечный float loadfactor; // Опустите следующий контент ...}Сегмент является статическим внутренним классом concurrenthashmap, вы можете видеть, что он наследует от reentrantlock, так что это по сути замок. Он владеет массивом Hashentry (хэш-таблицей) внутри) и гарантирует, что все методы добавления, удаления, изменения и поиска массива являются потоковыми. Конкретная реализация будет обсуждаться позже. Все операции по добавлению, удалению, изменению и проверке concurrenthashmap могут быть поручены сегменту, поэтому concurrenthashmap может гарантировать, что он безопасен в многопоточной среде. Кроме того, поскольку разные сегменты представляют собой разные замки, многопоточные чтения могут одновременно использовать различные сегменты, что означает, что многопоточные чтения могут одновременно работать с concurrenthashmap, что может избежать дефектов хэштата и значительно повысить производительность.
3. Что инициализировалось concurrenthashmap?
// Core Constructor @SuppressWarnings ("unchecked") public concurrenthashmap (int initialCapacity, float loadFactor, int complornestlevel) {if (! (Loadfactor> 0) || initialCapacity <0 || complunrencyLevel <= 0) {Throw newallalArgumentException (); } // Убедитесь, что уровень параллелизма не превышает предел if (complornuencelevel> max_segments) {complornuencelevel = max_segments; } int sshift = 0; int ssize = 1; // Убедитесь, что SSIZE - это сила 2, и является наиболее близким числом, больше или равным уровню параллелизма, в то время как (ssize <comproundencelevel) {++ sshift; ssize << = 1; } // Рассчитайте значение сдвига сегмента блокировки this.segmentshift = 32 - sshift; // Рассчитать значение маски блокировки сегмента this.segmentMask = ssize - 1; // Общая начальная емкость не может быть больше предельного значения, если (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Получить начальную емкость каждого сегмента блокировки int c = initialCapacity /ssize; // Сумма сегментированной блокировки не меньше, чем начальная общая емкость, если (c * ssize <initialCapacity) {++ c; } int cap = min_segment_table_capacity; // Убедитесь, что CAP - это мощность 2, и является наиболее близким числом, больше или равным C, в то время как (cap <c) {cap << = 1; } // Создать новый сегмент шаблона объекта сегмента <K, v> s0 = новый сегмент <K, v> (loadfactor, (int) (cap * LoadFactor), (Hashentry <K, v> []) Новая Хашентрика [CAP]); // Создать новый массив блокировки сегмента указанного размера <K, v> [] ss = (сегмент <k, v> []) новый сегмент [ssize]; // Использование небезопасно, чтобы назначить 0 -й элемент массива небезопасно.putorderedObject (ss, sbase, s0); this.segments = ss;}Concurrenthashmap имеет несколько конструкторов, но то, что опубликовано выше, является его основным конструктором, а другие конструкторы завершают инициализацию, вызывая ее. Конструктор ядра должен пройти в три параметра, а именно на начальную емкость, коэффициент загрузки и уровень параллелизма. При введении переменных элементов ранее мы можем знать, что начальная емкость по умолчанию составляет 16, коэффициент загрузки составляет 0,75F, а уровень параллелистики составляет 16. Теперь мы видим код конструктора Core. Во -первых, мы рассчитываем SSIZE через входящее параллелизинг. SSIZE - это длина массива сегмента. Это должно быть гарантированно, чтобы быть мощностью 2. Таким образом, подписание сегмента, заблокированного в массиве, может быть рассчитана с помощью Hash & ssize-1. Поскольку входящий параллелизиален не может быть гарантированно будет мощностью 2, его нельзя использовать непосредственно в качестве длины массива сегмента. Поэтому нам нужно найти мощность 2, наиболее близкую к параллелию, и использовать ее в качестве длины массива. Если сейчас проходит параллельное вещество = 15, приведенный выше код может рассчитать ssize = 16 и sshift = 4. Далее вы можете немедленно рассчитать SegmentShift = 16 и SegmentMask = 15. Обратите внимание, что SegmentShift здесь - это значение сдвига блокировки сегмента, а SegmentMask - это значение маски блокировки сегмента. Эти два значения используются для вычисления подписки блокировки сегмента в массиве, о котором мы поговорим ниже. После расчета количества блокировки сегмента SSIZE, емкость каждого блокировки сегмента может быть рассчитана на основе общей входящей емкости и ее значения C = initialCapacity/ssize. Емкость блокировки сегмента - это длина матрицы гастризма, и она также должна быть гарантированно будет мощностью 2. Значение C, рассчитанное выше, не может гарантировать это, поэтому C не может быть использован непосредственно как длину матрицы сборничества. Вам нужно найти еще одну мощность 2 ближайших к C, присвоить это значение CAP, а затем использовать CAP в качестве длины матрицы Hashentry. Теперь, когда у нас есть SSIZE и CAP, мы можем создать новый сегмент массива блокировки сегмента [] и хитрия массива элементов []. Обратите внимание, что в отличие от JDK1.6, только сегментный массив был создан в JDK1.7, и он не был инициализирован. Работа инициализации сегмента была оставлена на операцию вставки.
4. Как найти замки и найти элементы?
// Получить блокировки сегмента на основе хэш -кода @suppresswarnings ("unchecked") Частный сегмент <K, v> segmentforhash (int h) {long u = (((h >>> segmentshift) & segmentmask) << sshift) + sbase; return (сегмент <K, v>) unceabe.getObjectVolatile (сегменты, u);} // Получить элемент на основе хэш -кода @suppresswarnings ("uncemed") Статический финал <K, v> Hashentry <K, v> intryforhash (сегмент <K, v> seg, int h) {hashentry <K, v> v> [v> [v> [v> wab; return (seg == null || (tab = seg.table) == null)? NULL: (Hashentry <K, V>) unceabe.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase);} В JDK1.7 небезопасно используется для получения элементов массива, поэтому вот несколько кодов для расчета смещений элементов массива, чем JDK1.6. Мы не будем обращать внимание на эти коды на данный момент. Теперь нам нужно знать только следующие два момента:
а Рассчитайте индекс сегмента, заблокированного в массиве через хэш -код: (H >>> SegmentShift) и сегмент.
беременный Рассчитайте индекс элементов в массиве с помощью хэш -кода: (tab.length - 1) & h.
Теперь давайте предположим, что два параметра, передаваемые в конструктор, являются исходными. Согласно расчету, мы можем получить ssize = 16, sshift = 4, segmentshift = 28, segmentmask = 15. Точно так же длина матрицы хашинтрии в каждом блоке сегмента рассчитывается как 8, так что Tab.length-1 = 7. Основываясь на этих значениях, мы объясняем, как найти блокировки и элементы сегмента на основе одного и того же хэш -кода на рисунке ниже.
Можно видеть, что блокировка сегмента и позиционирование элемента определяется хэш -кодом элемента. Замок сегмента позиционирования - это высокое значение хеш -кода (начиная с 32 бит), а элемент позиционирования - низкое значение хэш -кода. Теперь есть вопрос. Они начинаются с левого конца 32-битного и правого конца 32-битного. Будут ли конфликты в какой -то момент? Мы можем найти Maximum_capacity = 1 << 30, max_segments = 1 << 16 в переменной элемента, что означает, что общее количество битов, используемых для блокировки сегмента позиционирования и элементов позиционирования, не превышает 30 битов, а количество битов, используемых для блокировки сегмента позиционирования, не превышает 16, поэтому осталось по меньшей мере 2 бита, поэтому не будет конфликта.
5. Как найти элементы специально?
// Получить ValuePublic v get (объект ключа) {segment <K, v> s; Hashentry <K, V> [] Tab; // Рассчитать хэш -код, используя хэш -функцию int h = hash (key); // Рассчитайте индекс блокировки сегмента на основе хеш -кода Long U = (((H >>> SegmentShift) и сегментамак) << sshift) + sbase; //Get the segment lock and the corresponding hash table if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null && (tab = s.table) != null) { //Get the header node of the linked list according to the hash code, and then traverse the linked list for (HashEntry<K,V> e = (Hashentry <K, V>) небезопасно. // Следуйте значению соответствующего элемента в соответствии с ключом и хэшем и возвращает значение if ((k = e.key) == Ключ || (e.hash == h && key.equals (k))) {return e.value; }}} return null;}В JDK1.6 метод GET сегмента блокировки доступа к массивам с помощью подписчиков, в то время как в JDK1.7 элементы в массиве читаются с помощью метода GetObjectVoLatile от Uncee. Зачем это? Мы знаем, что, хотя ссылка на матрицу гастризму, удерживаемое объектом сегмента, имеет летучие типа, элементы ссылки в массиве не имеют летучих типов, поэтому изменения многопоточных чтений на массивные элементы небезопасны и могут читать объекты, которые еще не были построены в массиве. В JDK1.6 второе чтение блокировки гарантированно будет безопасно, и в JDK1.7 метод чтения через небезопасность GetObjectVolatile также для этого. Элементы массива считывания с использованием метода getObjectVolatile требуют сначала получения смещения элемента в массиве. Здесь, в соответствии с хэш -кодом, смещение блокировки сегмента в массиве - U, а затем смещение U используется, чтобы попытаться прочитать блокировку сегмента. Поскольку массив блокировки сегмента не инициализируется во время строительства, может быть рассмотрено нулевое значение, поэтому сначала требуется решение. После подтверждения того, что блокировка сегмента и его внутренняя хэш -таблица не являются пустыми, элементы массива Hashentry читаются через хэш -код. Согласно структурной диаграмме выше, вы можете видеть, что в настоящее время получается заголовок связанного списка. Затем пройдите и найдите связанный список от начала до конца. Если соответствующее значение будет найдено, оно будет возвращено, в противном случае оно будет возвращено нулевым. Вышеуказанное - весь процесс поиска элементов.
6. Как реализовать элемент вставки?
// Добавить пары клавиш значения в набор (замените, если есть) @suppresswarnings ("unchecked") public v Put (k Key, v Значение) {segment <K, v> s; // передаваемое значение не может быть пустым, если (значение == null) бросить новый nullpointerexception (); // Рассчитать хэш -код с помощью хэш -функции int hash = hash (key); // Рассчитайте подписку блокировки сегмента на основе хэш -кода int j = (хэш >>> segmentShift) & SegmentMask; // Попробуйте получить блокировку сегмента на основе подписки if (s = (segment <k, v>) uncefe.getObject (сегменты, (j << sshift) + sbase)) == null) {// Если полученный блокировка сегмента пуста, конструкция a s = espuresegment (j); } // Вызовите метод PUT блокировки сегмента return s.put (key, hash, value, false);} // Добавить пару клавиш значения в набор (добавить, если его не существует) @suppresswarnings ("unchecked") public v putifabsent (k-ключ, v value) {segret <K, v> s; // передаваемое значение не может быть пустым, если (значение == null) бросить новый nullpointerexception (); // Рассчитать хэш -код с помощью хэша = хэш (ключ); // Рассчитайте подписку блокировки сегмента на основе хэш -кода int j = (хэш >>> segmentShift) & SegmentMask; // Попробуйте получить блокировку сегмента на основе подписки if (s = (segment <k, v>) uncafe.getObject (сегменты, (j << sshift) + sbase)) == null) {// Конструкция a s = avuresegment (j); } // Календарь метод POT озадачивания блокировки сегмента S.Put (ключ, хэш, значение, true);}В concurrenthashmap есть два метода, чтобы добавить пары клавиш. Если он существует, он будет перезаписан при добавлении метода POT. Метод ifabsent добавляется с помощью метода Put Ifabsent, он не будет перезаписан. Оба метода вызывают метод полока блокировки сегмента, чтобы завершить операцию, но последний переданный параметр отличается. В приведенном выше коде мы видим, что сначала мы рассчитываем индекс блокировки сегмента в массиве на основе хэш -кода клавиши, а затем используем метод GetObject Class для чтения блокировки сегмента в соответствии с SPED. Поскольку элементы в массиве сегментов не инициализируются при конструировании concurrenthashmap, можно прочитать нулевое значение, и с помощью метода Encureshage будет создана новое блокировка сегмента. После получения блокировки сегмента вызовите его метод полока, чтобы завершить операцию добавления. Давайте посмотрим, как это управлять им.
// Добавить пары значений ключа окончательный v (k -ключ, int hash, v Значение, Boolean onyifabsent) {// Попробуйте приобрести блокировку, если он сбой, спиновое управление <k, v> node = trylock ()? null: scanandlockforput (ключ, хэш, значение); V OldValue; try {Hashentry <K, v> [] tab = table; // Рассчитайте подписку элемента int index = (tab.length - 1) & hash; // Получение узла заголовка связанного списка на основе дистрихнизации индекса <K, v> First = intrintAt (Tab, Index); for (Hashentry <K, v> e = first ;;) {// transf связанный список, чтобы найти элемент, и if (e! = null) {k k; if ((k = e.key) == key || (e.hash == hash && key.equals (k)))) {oldvalue = e.value; // Решите, следует ли заменить старое значение на основе параметров, если (! Только ifabsent) {e.value = value; ++ modcount; } перерыв; } e = e.next; // Если не найдено, добавьте узел в связанный список} else {// Вставить узел узла в заголовок связанного списка if (node! = Null) {node.setnext (первое); } else {node = new Hashentry <K, v> (хэш, ключ, значение, первое); } // После вставки узла всегда добавляйте 1 int c = count + 1; // Если элемент превышает порог, разверните емкость, если (c> threshold && tab.length <maximum_capacity) {rehash (node); // В противном случае замените указанный индекс хэш -таблицы на узле узла} else {setEntryat (вкладка, index, node); } ++ modcount; count = c; OldValue = NULL; перерыв; }}} наконец {unlock (); } вернуть OldValue;}Чтобы обеспечить безопасность потока, необходимо заблокировать операции в сегментированные замки, поэтому поток приобретет блокировку в начале и продолжит выполнять, если приобретение будет успешным. Если приобретение не удается, вызовите метод Scanandlockforput, чтобы вращаться. Во время процесса спина сканируйте хэш -таблицу, чтобы найти указанный ключ. Если ключа не существует, будет создано новое хетринг, так что нет необходимости создавать его снова после получения блокировки. Чтобы сделать что -то в ожидании замка, он не будет тратить время напрасно. Это показывает добрые намерения автора. Мы подробно объясним конкретный метод спина позже. Теперь сначала потяните фокус. После того, как поток успешно получает блокировку, он получит элемент указанного индекса на основе вычисленного подписка. В настоящее время получается узлом заголовка связанного списка. Если узел заголовка не является пустым, связанный список будет пройден и поиск. После того, как он обнаружил, решите, заменить ли его на основе значения параметра только. Если обход не найден, новое гастстер будет указывать на узел заголовка. В настоящее время, если во время спина создается хетрировка, то прямо укажите его рядом с текущим узлом заголовка. Если спин не создан, здесь будет создано новое хетринг и укажет на узл заголовка. После добавления элементов в связанный список проверьте, превышает ли общее количество элементов порог. Если он превышает, позвоните в повторный размер для расширения. Если он не превышает его, непосредственно обратитесь к соответствующему элементу индекса массива к недавно добавленному узлу. Метод SetEntRyat изменяет ссылку на элемент массива, вызывая метод PutOrderEdObject, который гарантирует, что другие потоки могут прочитать последнее значение при чтении.
7. Как реализовать удаление элементов?
// Удалить указанный элемент (удалить непосредственно после поиска соответствующего элемента) public v Remove (объект клавиша) {// Использовать функцию хэш для вычисления хэш -кода int hash = hash (key); // Приобретение индекса блокировки сегмента на основе сегмента хеш -кода <K, v> s = segmentForhash (hash); // Каленать метод удаления возврата блокировки сегмента S == NULL? null: s.remove (key, hash, null);} // Удалить указанный элемент (удаляет значение, равное данному значению) public boolean remove (ключ объекта, значение объекта) {// Использовать функцию хэша для вычисления хэш -кода int hash = hash (ключ); Сегмент <K, V> s; // может убедиться, что блокировка сегмента не является пустой перед вызовом ответного значения метода удаления! = Null && (s = segmentForHash (hash))! = Null && S.Remove (Key, hash, значение)! = Null;}Concurrenthashmap предоставляет две операции по удалению, одна - удалить его сразу после поиска, а другая - сначала сравнить его, а затем удалить его после поиска. Оба эти метода удаления должны найти соответствующую блокировку сегмента на основе хэш -кода ключа, а затем завершить операцию удаления, вызывая метод удаления блокировки сегмента. Давайте посмотрим на метод удаления блокировки сегмента.
// Удалить указанный элемент окончательный v удалить (ключ объекта, int hash, значение объекта) {// Попробуйте получить блокировку, если он сбой, спин if (! Trylock ()) {scanandlock (key, hash); } V OldValue = null; try {Hashentry <K, v> [] tab = table; // Рассчитайте подписку элемента int index = (tab.length - 1) & hash; // Получить элемент массива в соответствии с Hashentry Node) Hashentry <K, v> e = entrytat (Tab, Index); Hashentry <K, v> pred = null; // Передача связанного списка, чтобы найти элемент, который будет удален, пока (e! = Null) {k k; // Следующее указывает на узел преемника текущего узла узла <k, v> next = e.next; // Поиск соответствующего узла на основе ключа и hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {v v = e.value; // Пропустите значение, передаваемое, если не равное v, и удалить его в других случаях, если (значение == null || value == v || value.equals (v)) {// Если предсчитай пуст, это означает, что узел, который должен быть удален, является узлом заголовка, если (nadex == null) {// reset the node node подсчета Linked Setentryat (tab, index); } else {// Установить последовательность Node Node на Next Node Pred.SetNext (Далее); } ++ modcount; --считать; // Записать значение удаления элемента OldValue = v; } перерыв; } // Если e не тот узел, который вы ищете, укажите Pred ссылку на него Pred = e; // Проверьте следующий узел E = Далее; }} наконец {unlock (); } вернуть OldValue;}При удалении элементов в блокировках сегментов вам нужно сначала получить замок. Если приобретение не удается, вызовите метод Scanandlock для вращения. Если приобретение успешно, выполните следующий шаг. Сначала вычислите индекс массива, а затем получите элементы массивы Hashentry через индекс. Здесь получен узлом заголовка связанного списка. Далее, проезд и поиск в связанном списке. Перед этим используйте следующий указатель, чтобы записать узел преемника текущего узла, а затем сравните ключ и хэш, чтобы увидеть, является ли это узелом, который вы ищете. Если так, выполните следующее, если суждение. Если значение пустое или значение равно текущему значению узла, оно введет оператор IF для удаления, в противном случае оно будет пропущено напрямую. Есть две ситуации при выполнении операции удаления в операторе IF. Если текущий узел является узлом заголовка, тогда напрямую установите следующий узел в качестве узла заголовка. Если текущий узел не является узлом заголовка, тогда установите преемника Pred Node на следующий узел. Узел Pred здесь представляет предшественника текущего узла. Каждый раз перед проверкой следующего узла, Pred указывает на текущий узел, который гарантирует, что Pred Node всегда является предшественником текущего узла. Обратите внимание, что в отличие от JDK1.6, в JDK1.7, следующая переменная объекта Hashentry не является окончательной, поэтому вы можете удалить элемент, непосредственно изменяя значение, на которое ссылается следующее. Поскольку следующая переменная имеет нестабильный тип, поток для чтения может немедленно прочитать последнее значение.
8. Как конкретно реализуются элементы замены?
// заменить указанный элемент (операция CAS) общедоступный логический заменитель (k -ключ, v oldvalue, v newvalue) {// Использовать функцию хэш для расчета хэш -кода int hash = hash (key); // Убедитесь, что OldValue и NewValue не пустые, если (OldValue == null || newValue == null) бросить новый nullpointerException (); // Получить индекс блокировки сегмента на основе сегмента хэш -кода <K, V> s = segmentForhash (hash); // Вызов метода замены блокировки сегмента возвращает S! = NULL && S.Replace (Key, Hash, OldValue, NewValue);} // Заменить операцию элемента (операция CAS) окончательный логический замен } boolean заменил = false; try {Hashentry <K, V> e; // Поиск узла заголовка непосредственно через хэш, а затем пройти связанный список для (e = intrintForHash (this, hash); e! = Null; e = e.next) {k k; // Поиск узела, который будет заменен на основе ключа и хэш if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {// Если указанное текущее значение правильное, замените if (oldvalue.equals (e.value)) {e.value = newvalue; ++ modcount; заменил = true; } // В противном случае, если операция не выполнена, вернуть перерыв; }}} наконец {unlock (); } return заменил;}Concurrenthashmap также предоставляет две операции замены, одна из них заключается в замене сразу после поиска, а другая - сначала, а затем заменить (операция CAS). Реализация этих двух операций примерно одинакова, за исключением того, что операция CAS имеет дополнительный уровень операций сравнения перед заменой, поэтому нам нужно лишь кратко понять одну из операций. Здесь мы используем операции CAS для анализа, который все еще является старой рутиной. Сначала найдите соответствующую блокировку сегмента на основе хэш -кода ключа, а затем вызовите его метод замены. После входа в метод замены в блокировке сегмента необходимо сначала получить блокировку. Если приобретение не удается, поверните его. Если приобретение успешно, перейдите к следующему шагу. Во -первых, получить узлом заголовка связанного списка в соответствии с хэш -кодом, а затем пройдите и найдите в соответствии с ключом и хэшем. После поиска соответствующего элемента сравните, является ли данное OldValue текущим значением. Если нет, отдайте модификацию, и если да, замените ее новым значением. Поскольку поле значения объекта Hashentry имеет летучие типа, его можно заменить напрямую.
9. Что именно вы делали при вращении?
// Спин ожидание, чтобы приобрести блокировку (PUT) Частно -хашенрийский <K, V> SCANANDLOCKFORPUT (k Key, int hash, v Значение) {// Получить узл заголовка в соответствии с хэш -кодовым хэдитриком <K, v> First = entryforhash (это, хэш); Хашентрит <K, v> e = первое; Hashentry <K, v> node = null; int retries = -1; // спин while (! Trylock ()) {Hashentry <K, V> f; if (retries <0) {// Если узел заголовка пуст, создайте новый узел if (e == null) {if (node == null) {node = new Hashentry <K, v> (hash, key, value, null); } retries = 0; // в противном случае пересечь связанный список, чтобы найти узел} else if (key.equals (e.key)) {retries = 0; } else {e = e.next; } // relies Добавить 1 здесь каждый раз и определить, превышает ли оно максимальное значение} else if (++ retries> max_scan_retries) {lock (); перерыв; // Когда повторные цифры являются ровными числами, определите, изменился ли первый} else if ((retries & 1) == 0 && (f = intrintforhash (this, hash))! = First) {e = first = f; RETRIES = -1; }} return node;} // Спин ожидание для получения блокировки (удалить и заменить операции) Private void scanandlock (объект Key, int hash) {// Получить узлом заголовка связанного списка в соответствии с хэш -кодом Hashentry <K, V> First = intrintForhash (this, hash); Хашентрит <K, v> e = первое; int retries = -1; // спин while (! Trylock ()) {Hashentry <K, V> f; if (relies <0) {// Передача связанного списка, чтобы найти узел if (e == null || key.equals (e.key)) {retries = 0; } else {e = e.next; } // relies Добавить 1 здесь каждый раз и определить, превышает ли оно максимальное значение} else if (++ retries> max_scan_retries) {lock (); перерыв; // Когда повторные цифры являются ровными числами, определите, изменился ли первый} else if ((retries & 1) == 0 && (f = intrintforhash (this, hash))! = First) {e = first = f; RETRIES = -1; }}}Как мы упоминали ранее, поместите, удаляют и заменяют операции в сегментированных замках, требуют приобретения блокировки в первую очередь. Только после успешного получения блокировки можно выполнить следующую операцию. Если приобретение не удастся, SPIN будет выполнен. Работа спина также добавлена в JDK1.7. Чтобы избежать частого приостановки и пробуждения потоков, это может улучшить производительность во время одновременных операций. Scanandlockforput вызывается в методе PUT, а Scanandlock вызывается в методах удаления и замены. Два метода вращения примерно одинаковы, здесь мы анализируем только метод Scanandlockforput. Прежде всего, вы должны получить узлом заголовка связанного списка на основе хэш -кода. Затем поток введите цикл WHILE, чтобы выполнить. Единственный способ выйти из петли - это успешно приобрести замок, и поток не будет приостановлен в течение этого периода. Когда цикл только что введен, значение RESRIES составляет -1. В настоящее время поток не попытается немедленно приобрести блокировку. Вместо этого он сначала найдет узел, соответствующий ключу (если он не найден, будет создан новый), а затем установит повторные изделия на 0. Затем он попытается приобрести блокировку снова и снова. Соответствующее значение повторения также будет добавлено 1 каждый раз, пока максимальное количество попыток превысит максимальное количество попыток. Если блокировка не была получена, метод блокировки будет вызван для блокировки и получения. Во время попытки приобрести блокировку, он проверит, изменялся ли узел заголовка каждый раз (повторные ресурсы даже). Если это изменено, сбросьте повторные переписи до -1, а затем повторите процесс только сейчас. Это то, что делает нить при вращении. Следует отметить, что если узел головного узела был обнаружен для изменения во время вращения, время вращения потока будет расширено.
10. Какие операции выполняются при расширении хэш -таблицы?
// снова хэш @suppresswarnings ("unchecked") private void rehash (хашентрика <k, v> node) {// Получить ссылку на старую хэш -хашентрику <K, v> [] oldtable = таблица; // Получить емкость старой хеш -таблицы int oldCapacity = oldtable.length; // Рассчитать емкость новой хэш -таблицы (в 2 раза больше старой хэш -таблицы) int newcapacity = oldCapacity << 1; // Рассчитать новый порог порога нового элемента = (int) (newCapacity * LoadFactor); // Создать новое хантристское массив Hashentry Hashentry <K, V> [] newtable = (Hashentry <K, v> []) Новая хашенрия [newcapacity]; // генерировать новое значение маски int sizemask = newcapacity - 1; // спокойствие через все элементы старой таблицы для (int i = 0; i <OldCapacity; i ++) {// Получить узлом заголовка связанного списка Hashentry <K, v> e = oldtable [i]; if (e! = null) {Hashentry <K, v> next = e.next; // Рассчитать индекс элемента в новой таблице int idx = e.hash & sizemask; // Далее пусто, чтобы указать, что в связанном списке есть только один узел, если (next == null) {// Поместите узел непосредственно в новую таблицу [idx] = e; } else {Hashentry <K, v> lastrun = e; int lastidx = idx; // позиционировать узел Lastrun и непосредственно поместите узел после Lastrun в новую таблицу для (Hashentry <K, V> Last = Next; Last! = Null; last = last.next) {int k = last.hash & sizemask; if (k! = lastidx) {asticidx = k; lastrun = последний; }} newtable [lastidx] = lastrun; // транспорт элементы перед ластрунским узлом связанного списка, скопируйте их в новую таблицу, в свою очередь, для (Hashentry <K, v> p = e; p! = Lastrun; p = p.next) {v v = p.value; int h = p.hash; int k = h & sizemask; Hashentry <K, v> n = newtable [k]; Newtable [k] = Новый Хашентрит <K, V> (H, P.Key, V, N); }}}}} // Вычислять индекс входящего узла в новой таблице int nodeIndex = node.hash & sizemask; // Добавить входящий узел в узл заголовка связанного списка Node.setNext (newtable [nodeindex]); // обмениваться новой таблицей, указанным элементом индекса с новичком входящего узла [nodeindex] = node; // Укажите ссылку на таблицу хэш на новую таблицу таблицы = newtable;}Метод перефразирования вызывается в методе POT. Мы знаем, что когда будет установлен метод POT, новый элемент будет создан и добавлен в хэш -массив. Чем больше возникает возможность хэш -конфликтов, тем больше производительность хеш -таблицы также снизится. Поэтому каждый раз, когда операция пута будет проверять, превышает ли общее количество элементов порог. Если он превышает порог, метод перефразирования будет вызван для расширения емкости. Поскольку длина массива больше не может быть изменена после его определения, необходимо создать новый массив, чтобы заменить исходный массив. Из кода вы можете знать, что недавно созданный массив в два раза превышает длину исходного массива (OldCapacity << 1). After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
Выше всего содержание этой статьи. Я надеюсь, что это будет полезно для каждого обучения, и я надеюсь, что все будут поддерживать Wulin.com больше.