Sabemos que uma tabela de hash é uma estrutura de dados muito eficiente, e um excelente design da função de hash pode fazer as operações de adição, exclusão, modificação e pesquisa nela atingem o nível O (1). O Java nos fornece uma estrutura de hash pronta, ou seja, a classe HashMap. No artigo anterior, introduzi a classe Hashmap e sabia que todos os seus métodos não eram sincronizados, por isso não é seguro em um ambiente multithread. Para esse fim, o Java nos fornece outra classe de hashtable, que é muito simples e grosseira ao lidar com a sincronização de vários threads, ou seja, para bloquear todos os seus métodos usando a palavra-chave sincronizada com base no hashmap. Embora esse método seja simples, leva a um problema, ou seja, apenas um thread pode operar a tabela de hash ao mesmo tempo. Mesmo que esses threads estejam apenas lendo operações, eles devem ser filmados, o que afeta bastante o desempenho em ambientes multithread altamente competitivos. O concorrente introduzido neste artigo é resolver esse problema. Ele usa bloqueios segmentados para gritar os bloqueios, para que vários threads possam operar a tabela de hash ao mesmo tempo, o que melhora bastante o desempenho. A figura a seguir é um diagrama esquemático de sua estrutura interna.
1. Quais variáveis de membro o ConcurrentHashMap tem?
// Capacidade de inicialização padrão estática final int default_initial_capacity = 16; // fator de carga padrão float final estático default_load_factor = 0.75f; // nível de concorrência padrão estático estático final Int default_concurrency_level = 16; // Definir a capacidade máxima final do máximo de máxima_capacity = 1 << 30; Min_segment_table_capacity = 2; // O número máximo de segmentos bloqueia o final estático int max_segments = 1 << 16; // Número de tentativas antes de bloquear o final estático int tentativas_before_lock = 2; // máscara valor do bloqueio do segmento Final segmento;
Antes de ler este artigo, acredito que os leitores não conseguem entender o significado e a função específicos dessas variáveis de membros, mas os leitores são aconselhados a ler pacientemente. O papel dessas variáveis de membros será introduzido um por um nos cenários específicos posteriormente. Aqui, os leitores precisam apenas deixar um olhar familiar para essas variáveis de membros. No entanto, ainda existem algumas variáveis que precisamos conhecer agora. Por exemplo, a matriz do segmento representa o conjunto de bloqueios de segmento, o nível de simultaneidade representa o número de bloqueios de segmento (o que também significa quantos threads podem operar ao mesmo tempo), a capacidade de inicialização representa a capacidade de todo o contêiner e o fator de carga representa o nível de quão total os elementos do contêiner podem atingir.
2. Qual é a estrutura interna do bloqueio do segmento?
// segmento de bloqueio de segmento estático segmento <k, v> Estende o reentrantlock implementa serializável {// Máximo do número de rotação estática final int max_scan_retries = runtime.getRuntime (). 64: 1; // HAST TABLE HASHENTRIA VOLÁVEL DA TABLE <K, V> []; // Número total de elementos transitórios int contam; // número de modificações transitórias int modcount; // limiar de elemento limiar de transiente int; // fator de carga Final de cargas float de carga; // omita o seguinte conteúdo ...}O segmento é uma classe interna estática do ConcurrentHashmap, você pode ver que ele herda do Reentrantlock, por isso é essencialmente uma trava. Ele mantém uma matriz de hashentry (tabela de hash) internamente e garante que todos os métodos de adição, exclusão, modificação e pesquisa da matriz sejam seguros para threads. A implementação específica será discutida mais adiante. Todas as operações sobre a adição, exclusão, modificação e verificação do sapão concorrente podem ser confiadas ao segmento; portanto, o concorrente pode garantir que seja seguro em um ambiente multitreado. Além disso, como segmentos diferentes são bloqueios diferentes, os multithreads podem operar diferentes segmentos ao mesmo tempo, o que significa que os multithreads podem operar simultaneamente ao mesmo tempo, o que pode evitar os defeitos do hashtable e melhorar bastante o desempenho.
3. O que o concorrente inicializou?
// Core Constructor @suppresswarnings ("desmarcado") public ConcurrentHashMap (int InitialCapacity, Float LoadFactor, int ConcurrencyLEvel) {if (! (LoadFactor> 0) || InitialCapacity <0 || Concurrencyvel <= 0) {Throw New IllegalarGumentException; } // Verifique se o nível de simultaneidade não é maior que o limite se (ConcurrencyLevel> max_segments) {ConcurrencyLevel = max_segments; } int sshift = 0; int ssize = 1; // Verifique se o ssize é uma potência de 2 e é o número mais próximo maior ou igual ao nível de simultaneidade enquanto (ssize <concorrência em nível) {++ sshift; ssize << = 1; } // Calcule o valor de mudança do segmento bloqueando this.segmentShift = 32 - sshift; // calcule o valor da máscara do bloqueio do segmento this.segmentMask = ssize - 1; // A capacidade inicial total não pode ser maior que o valor limite se (InitialCapacity> MAXIMUM_CAPACIDADE) {InitialCapacity = Maximum_Capacity; } // Obtenha a capacidade inicial de cada bloqueio de segmento int c = InitialCapacidade /ssize; // A soma da capacidade de bloqueio segmentada não é menor que a capacidade total inicial se (c * ssize <InitialCapacidade) {++ c; } int cap = min_segment_table_capacity; // Verifique se a tampa é uma potência de 2 e é o número mais próximo maior ou igual a C enquanto (cap <c) {cap << = 1; } // Crie um novo segmento de modelo de objeto de segmento <k, v> s0 = novo segmento <k, v> (loadFactor, (int) (cap * loadFactor), (hashentry <k, v> []) nova hashentry [cap]); // Crie uma nova matriz de bloqueio de segmento do segmento de tamanho especificado <k, v> [] ss = (segmento <k, v> []) novo segmento [ssize]; // Use inseguro para atribuir o elemento 0º da matriz insefe.putOrderEdObject (SS, SBASE, S0); this.segments = ss;}O ConcurrentHashMap possui vários construtores, mas o que é publicado acima é o seu construtor principal e outros construtores completam a inicialização, chamando -o. O construtor principal precisa passar em três parâmetros, a saber, a capacidade inicial, o fator de carregamento e o nível de simultaneidade. Ao introduzir variáveis de membro anterior, podemos saber que a capacidade inicial padrão é 16, o fator de carregamento é de 0,75F e o nível de simultaneidade é 16. Agora vemos o código do construtor principal. Primeiro, calculamos o ssize através do nível concorrido de entrada. SSize é o comprimento da matriz do segmento. Deve-se garantir que seja uma potência de 2. Dessa maneira, o subscrito do segmento bloqueado na matriz pode ser calculado por Hash & ssize-1. Como o nível concorrente recebido não pode ser garantido como uma potência de 2, ele não pode ser usado diretamente como o comprimento da matriz de segmentos. Portanto, precisamos encontrar um poder de 2 mais próximo do nível concorrência e usá -lo como o comprimento da matriz. Se o ConcurrencyLevel = 15 for passado agora, o código acima poderá calcular ssize = 16 e sshift = 4. Em seguida, você pode calcular imediatamente o segmentshift = 16 e o segmentMask = 15. Observe que o segmentshift aqui está o valor de mudança do bloqueio do segmento e o segmentMask é o valor da máscara do bloqueio do segmento. Esses dois valores são usados para calcular o subscrito de bloqueio de segmento na matriz, sobre a qual falaremos abaixo. Após calcular o número de bloqueios de segmento, a capacidade de cada bloqueio de segmento pode ser calculada com base na capacidade total de entrada e seu valor C = InitialCapacidade/SSize. A capacidade do bloqueio do segmento é o comprimento da matriz de hashentry e também deve ser garantido que seja uma potência de 2. O valor de c calculado acima não pode garantir isso, portanto, não é usado diretamente como o comprimento da matriz de hashentry. Você precisa encontrar outro poder de 2 mais próximo de C, atribuir esse valor ao CAP e depois usar o CAP como o comprimento da matriz de hashentry. Agora que temos ssize e limite, podemos criar um novo segmento de matriz de bloqueio de segmento [] e uma matriz de elementos hashentry []. Observe que, diferentemente do JDK1.6, apenas a matriz do segmento foi criada no JDK1.7 e não foi inicializada. A operação de inicializar o segmento foi deixada para a operação de inserção.
4. Como localizar bloqueios e localizar elementos?
// Obter bloqueios de segmento com base no código de hash @suppresswarnings ("desmarcado") segmento privado <k, v> segmentforhash (int h) {long u = (((h >>> segmentshift) e segmentMask) << sshift) + sbase; return (segmento <k, v>) unsefe.getObjectVolatile (segmentos, u);} // obtenha elemento baseado no código de hash @suppresswarnings ("desmarcado") estático final <k, v> hashentry <k, v> entrada (segmento <k, v> seg, int h) {hhhhentny; return (seg == null || (tab = seg.table) == null)? null: (hashentry <k, v>) insegu.getObjectVolatile (tab, ((long) ((tab.length - 1) & h)) << tshift) + tbase);} No JDK1.7, o inseguro é usado para obter elementos de matriz, então aqui estão mais alguns códigos para calcular compensações dos elementos da matriz do que o JDK1.6. Não prestaremos atenção a esses códigos por enquanto. Agora precisamos saber apenas os dois pontos a seguir:
um. Calcule o subscrito do segmento bloqueado na matriz através do código de hash: (h >>> segmentshift) e segmentMask.
b. Calcule o subscrito de elementos na matriz pelo código de hash: (tab.length - 1) & h.
Agora, vamos supor que os dois parâmetros passados para o construtor sejam InitialCapacity = 128, ConcurrencyLevel = 16. De acordo com o cálculo, podemos obter ssize = 16, sshift = 4, segmentShift = 28, segmentMask = 15. Da mesma forma, o comprimento da matriz de hashentry em cada bloqueio de segmento é calculado como 8, portanto, tab.length-1 = 7. Com base nesses valores, explicamos como localizar bloqueios e elementos de segmento com base no mesmo código de hash através da figura abaixo.
Pode -se observar que o bloqueio do segmento e o posicionamento do elemento são determinados pelo código de hash do elemento. O bloqueio do segmento de posicionamento é o alto valor do código de hash (a partir de 32 bits), e o elemento de posicionamento é o baixo valor do código de hash. Agora há uma pergunta. Eles começam a partir da extremidade esquerda dos 32 bits e da extremidade direita dos 32 bits. Haverá conflitos em algum momento? Podemos encontrar o maximum_capacity = 1 << 30, max_segments = 1 << 16 na variável de membro, o que significa que o número total de bits usados para o posicionamento de travas de segmento e elementos de posicionamento não excede 30 e o número de bits usados para posicionamento do segmento não excede 16, portanto, há pelo menos 2 bits de esquerda; portanto, não haverá conflitos.
5. Como encontrar elementos especificamente?
// obtenha valuepublic v get (chave de objeto) {segmento <k, v> s; Hashentry <k, v> [] guia; // Calcule o código de hash usando a função hash int h = hash (chave); // Calcule o índice do bloqueio do segmento com base no código de hash lonns u = (((h >>> segmentshift) e segmentMask) << sshift) + sbase; // Obtenha o bloqueio do segmento e a tabela de hash correspondente if ((s = (segmento <k, v>) insefa.getObjectVolatile (segmentos, u))! = Null && (tab = s.table)! (Hashentry <k, v>) insegure.getObjectVolatile (TAB, ((longa) ((Tab.Length - 1) e H)) << TSHIFT) + TBASE); // Siga o valor do elemento correspondente de acordo com a chave e hash e retorne o valor se ((k = e.key) == key || (e.hash == h && key.equals (k))) {return e.value; }}} retornar null;}No JDK1.6, o método GET de bloqueio de segmentos de acesso a elementos de matriz por meio de subscritos, enquanto no JDK1.7, os elementos da matriz são lidos pelo método GetObjectVolatile da UNSAGE. Por que fazer isso? Sabemos que, embora a referência da matriz de hashentry mantida pelo objeto de segmento seja do tipo volátil, as referências do elemento na matriz não são do tipo volátil; portanto, as modificações multithreading para os elementos da matriz são inseguros e podem ler objetos que ainda não foram construídos na matriz. No JDK1.6, a segunda leitura de bloqueio é garantida como segura e, no JDK1.7, a leitura do método GetObjectVolatile da UNSAGE é também para garantir isso. A leitura dos elementos da matriz usando o método getObjectVolatile requer primeiro a obtenção do deslocamento do elemento na matriz. Aqui, de acordo com o código de hash, o deslocamento do bloqueio do segmento na matriz é U e, em seguida, o deslocamento U é usado para tentar ler o bloqueio do segmento. Como a matriz de bloqueio do segmento não é inicializada durante a construção, um valor nulo pode ser lido, portanto, um julgamento é necessário primeiro. Depois de confirmar que o bloqueio do segmento e sua tabela de hash internos não estão vazios, os elementos da matriz de hashentry são lidos pelo código de hash. De acordo com o diagrama de estrutura acima, você pode ver que o nó do cabeçalho da lista vinculado é obtido no momento. Em seguida, atravesse e pesquise na lista vinculada do começo ao fim. Se o valor correspondente for encontrado, ele será retornado, caso contrário, será retornado nulo. O exposto acima é todo o processo de encontrar elementos.
6. Como implementar o elemento de inserção?
// Adicione pares de valores-chave ao conjunto (substitua se houver) @suppresswarnings ("desmarcado") public V put (K-Key, V valor) {segmento <k, v> s; // O valor aprovado não pode estar vazio se (value == null) lançar novo nullPointerException (); // Calcule o código de hash usando a função hash int hash = hash (chave); // Calcule o subscrito do bloqueio do segmento com base no código de hash int j = (hash >>> segmentshift) e segmentMask; // Tente obter o bloqueio do segmento com base no subscrito if ((s = (segmento <k, v>) unsafe.getObject (segmentos, (j << sshift) + sbase)) == null) {// se o bloqueio de segmento obtido estiver vazio, construa a s = secursegment (j); } // Chame o método de put do bloqueio do segmento Retorno s.put (chave, hash, valor, false);} // Adicione um par de valores-chave ao conjunto (adicione se ele não existir) @suppresswarnings ("desmarcado") public v Putifabsent (K-Key, V value) {segmento <k, v> s; // O valor aprovado não pode estar vazio se (value == null) lançar novo nullPointerException (); // calcule o código de hash com hash = hash (chave); // Calcule o subscrito do bloqueio do segmento com base no código de hash int j = (hash >>> segmentshift) e segmentMask; // Tente obter o bloqueio do segmento com base no subscrito if ((s = (segmento <k, v>) unsefe.getObject (segmentos, (j << sshift) + sbase)) == null) {// constructe a s = surresegment (j); } // calendário O método de put do retorno de bloqueio do segmento S.put (chave, hash, valor, true);}Existem dois métodos no concorrente para adicionar pares de valor-chave. Se existir, será substituído quando adicionado através do método put. O método ifabsent é adicionado através do método put ifabsent, ele não será substituído. Ambos os métodos chamam o método de put de trava de segmento para concluir a operação, mas o último parâmetro passado é diferente. No código acima, podemos ver que, primeiro, calculamos o subscrito do bloqueio do segmento na matriz com base no código de hash da chave e, em seguida, usamos o método GetObject de classe insegura para ler o bloqueio do segmento de acordo com o subscrito. Como os elementos da matriz de segmentos não são inicializados ao construir o sapão concorrente, um valor nulo pode ser lido e um novo bloqueio de segmento será criado através do método de segurança. Depois de obter o bloqueio do segmento, chame seu método de put para concluir a operação de adição. Vamos dar uma olhada em como operá -lo.
// Adicione os pares do valor da tecla final V PUT (K Key, int hash, V Valor, Boolean Onlyifabsent) {// Tente adquirir o bloqueio, se falhar, spin hashentry <k, v> node = TryLock ()? nulo: scanndlockForput (chave, hash, valor); V OldValue; tente {hashentry <k, v> [] tab = tabela; // Calcule o subscrito do elemento INCID = (TAB.Length - 1) & Hash; // Obtenha o nó do cabeçalho da lista vinculada com base na hashentry subscrita <k, v> primeiro = entrada (tab, índice); for (hashentry <k, v> e = primeiro ;;) {// transf a lista vinculada para encontrar o elemento e if (e! = null) {k k; if ((k = e.Key) == key || (e.hash == hash && key.equals (k)))) {OldValue = E.Value; // Decida se deve substituir o valor antigo com base nos parâmetros if (! Somentefabsent) {e.value = value; ++ modCount; } quebrar; } e = e.next; // Se não for encontrado, adicione um nó à lista vinculada} else {// Insira o nó do nó no cabeçalho da lista vinculada se (node! = Null) {node.setNext (primeiro); } else {node = new Hashentry <k, v> (hash, chave, valor, primeiro); } // Depois de inserir o nó, sempre adicione 1 int c = contagem + 1; // Se o elemento exceder o limite, expanda a capacidade if (c> limite && tab.length <maximum_capacity) {rehash (node); // Caso contrário, substitua o subscrito especificado da tabela de hash com o nó} else {setEntryat (guia, índice, nó); } ++ modCount; contagem = c; OldValue = nulo; quebrar; }}} finalmente {desbloqueio (); } Retornar OldValue;}Para garantir a segurança do encadeamento, coloque as operações em bloqueios segmentados, precisam ser bloqueados, para que o encadeamento adquira o bloqueio no início e continue a executar se a aquisição for bem -sucedida. Se a aquisição falhar, ligue para o método ScanndlockForput para girar. Durante o processo de rotação, verifique a tabela de hash para encontrar a chave especificada. Se a chave não existir, uma nova hashentry será criada, para que não haja necessidade de criá -la novamente após a obtenção do bloqueio. Para fazer algumas coisas enquanto aguardam a fechadura, não perderá tempo em vão. Isso mostra as boas intenções do autor. Explicaremos o método de rotação específico em detalhes posteriormente. Agora, puxe o foco de volta primeiro. Após o thread adquirir com sucesso o bloqueio, ele obterá o elemento do subscrito especificado com base no subscrito calculado. Neste momento, o nó do cabeçalho da lista vinculado é obtido. Se o nó do cabeçalho não estiver vazio, a lista vinculada será percorrida e pesquisada. Depois de encontrá -lo, decida se deve substituí -lo com base no valor do parâmetro único. Se a travessia não for encontrada, uma nova hashentry apontará para o nó do cabeçalho. Neste momento, se uma hashentry for criada durante a rotação, aponte diretamente o próximo ao nó atual. Se o spin não for criado, uma nova hashentry será criada aqui e apontará para o nó do cabeçalho. Depois de adicionar elementos à lista vinculada, verifique se o número total de elementos excede o limite. Se exceder, ligue para a Rehash para expansão. Se não o exceder, consulte diretamente o elemento subscrito correspondente da matriz ao nó recém -adicionado. O método setEntryat altera a referência do elemento da matriz chamando o método PutOrderEdObject da UNSAFE, que garante que outros threads possam ler o valor mais recente ao ler.
7. Como implementar a exclusão de elementos?
// exclua o elemento especificado (exclua diretamente após encontrar o elemento correspondente) public v remover (chave do objeto) {// use a função hash para calcular o código de hash int hash = hash (chave); // adquire o índice do bloqueio do segmento com base no segmento de código de hash <k, v> s = segmentforhash (hash); // Calend o método Remover do retorno de bloqueio do segmento S == NULL? nulo: s.remove (chave, hash, nulo);} // Exclua o elemento especificado (remove o valor igual ao valor fornecido) Public boolean Remover (chave do objeto, valor do objeto) {// use a função de hash para calcular o código de hash int hash = hash (key); Segmento <k, v> s; // pode garantir que o bloqueio do segmento não esteja vazio antes de chamar o valor de retorno do método Remover! = Null && (s = segmentforhash (hash))! = Null && s.remove (chave, hash, valor)! = Null;}O ConcurrentHashMap fornece duas operações de exclusão, uma é excluí -lo diretamente depois de encontrá -lo, e o outro é compará -lo primeiro e depois excluí -lo depois de encontrá -lo. Ambos os métodos de exclusão são encontrar o bloqueio de segmento correspondente com base no código de hash da chave e, em seguida, preencher a operação de exclusão chamando o método de remoção do bloqueio do segmento. Vamos dar uma olhada no método de remoção de bloqueio de segmento.
// Exclua o elemento especificado Final V Remova (chave do objeto, int hash, valor do objeto) {// Tente adquirir o bloqueio, se falhar, gire se (! Trylock ()) {scanndlock (chave, hash); } V OldValue = null; tente {hashentry <k, v> [] tab = tabela; // Calcule o subscrito do elemento INCID = (TAB.Length - 1) & Hash; // Obtenha o elemento da matriz de acordo com o subscrito (link list cabeçalho) hashentry <k, v> e = entradas (tab, índice); Hashentry <k, v> pred = null; // transfira a lista vinculada para encontrar o elemento a ser excluído enquanto (e! = Null) {k k; // Em seguida, aponta para o nó sucessor da hashentry do nó atual <k, v> next = e.next; // Pesquise o nó correspondente com base na chave e hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {v v = e.value; // Pule o valor passado se não for igual a V, e exclua -o em outros casos se (value == null || value == v || value.equals (v)) {// se pred está vazio, significa que o nó a ser excluído é o nó do cabeçalho se (pred == null) {// reset the headers; } else {// Defina a sucessão do nó pred no próximo nó pred.setNext (a seguir); } ++ modCount; --contar; // Registre o valor do elemento deleção OldValue = V; } quebrar; } // Se E não for o nó que você está procurando, aponte a referência predr que ele preve = e; // Verifique o próximo nó e = a seguir; }} finalmente {desbloqueio (); } Retornar OldValue;}Ao excluir elementos nos bloqueios do segmento, você precisa adquirir primeiro o bloqueio. Se a aquisição falhar, chame o método Scanndlock para girar. Se a aquisição for bem -sucedida, execute a próxima etapa. Primeiro calcule o subscrito da matriz e depois obtenha os elementos da matriz de hashentry através do subscrito. Aqui, o nó do cabeçalho da lista vinculado é obtido. Em seguida, Traversal e pesquise na lista vinculada. Antes disso, use o próximo ponteiro para gravar o nó sucessor do nó atual e compare a chave e o hash para ver se é o nó que você está procurando. Nesse caso, realize o próximo julgamento se. Se o valor estiver vazio ou o valor for igual ao valor atual do nó, ele entrará na instrução IF para exclusão, caso contrário, será ignorado diretamente. Existem duas situações ao executar uma operação de exclusão em uma instrução IF. Se o nó atual for um nó de cabeçalho, defina diretamente o próximo nó como o nó do cabeçalho. Se o nó atual não for um nó de cabeçalho, defina o sucessor do nó pred no próximo nó. O nó pred aqui representa o antecessor do nó atual. Cada vez, antes de verificar o próximo nó, o PESS é apontado para o nó atual, o que garante que o nó Pred seja sempre o antecessor do nó atual. Observe que, diferentemente do JDK1.6, no JDK1.7, a próxima variável do objeto de hashentry não é final, para que você possa excluir o elemento modificando diretamente o valor referenciado pelo próximo. Como a próxima variável é do tipo volátil, o thread de leitura pode ler imediatamente o valor mais recente.
8. Como os elementos de substituição são implementados especificamente?
// Substitua o elemento especificado (operação CAS) Public boolean Substitua (K -Key, v OldValue, v newValue) {// Use a função de hash para calcular o código de hash int hash = hash (key); // Verifique se o OldValue e o NewValue não estão vazios se (OldValue == null || newValue == null) lança nova nullPointerException (); // Obtenha o índice do bloqueio do segmento com base no segmento de código de hash <k, v> s = segmentforhash (hash); // chamando o método de substituição do bloqueio do segmento retorna s! = Null && s.Replace (chave, hash, antigo, newValue);} // Substitua a operação do elemento (operação CAS) Substitua boolean final (Key k, Int hash, s spin se (! Trylock, v newValue) {// Tente (/), a tecla), se spin, spanock (! } booleano substituído = false; tente {hashentry <k, v> e; // Pesquise o nó do cabeçalho diretamente através do hash e, em seguida, atravessa a lista vinculada para (e = EntryForHash (this, hash); e! = Null; e = e.next) {k k; // Pesquise o nó a ser substituído com base na chave e hash if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {// se o valor atual especificado estiver correto, substitua se (antigoValue.Equals (e.value)) {e.value = newValue; ++ modCount; substituído = true; } // Caso contrário, se nenhuma operação for executada, retorne a quebra; }}} finalmente {desbloqueio (); } retornar substituído;}O concorrente também fornece duas operações de substituição, uma é substituir diretamente após a descoberta, e a outra é comparar primeiro e depois substituir (operação CAS). A implementação dessas duas operações é aproximadamente a mesma, exceto que a operação do CAS possui uma camada adicional de operações de comparação antes de substituir, por isso precisamos apenas entender brevemente uma das operações. Aqui usamos operações do CAS para análise, que ainda é uma rotina antiga. Primeiro, encontre o bloqueio do segmento correspondente com base no código de hash da chave e, em seguida, chame seu método de substituição. Depois de inserir o método de substituição no bloqueio do segmento, você precisa adquirir o bloqueio primeiro. Se a aquisição falhar, gire -a. Se a aquisição for bem -sucedida, prossiga para a próxima etapa. Primeiro, obtenha o nó do cabeçalho da lista vinculada de acordo com o código de hash e depois atravesse e pesquise de acordo com a chave e o hash. Depois de encontrar o elemento correspondente, compare se o antigo valor fornecido é o valor atual. Caso contrário, desista da modificação e, nesse caso, substitua -o pelo novo valor. Como o campo de valor do objeto de hashentry é do tipo volátil, ele pode ser substituído diretamente.
9. O que exatamente você fez ao girar?
// Spin esperando para adquirir a hashentry privada de bloqueio (Operação) <k, v> scanandlockforput (K -Key, int hash, V Value) {// Obtenha o nó do cabeçalho de acordo com a hashentry do código de hash <k, v> primeiro = entrada (isto, hash); Hashentry <k, v> e = primeiro; Hashentry <k, v> node = null; Int Bettries = -1; // gire while (! Trylock ()) {hashentry <k, v> f; if (tentativas <0) {// Se o nó do cabeçalho estiver vazio, crie um novo nó if (e == null) {if (node == null) {node = new Hashentry <k, v> (hash, chave, valor, null); } tentativas = 0; // Caso contrário, atravesse a lista vinculada para localizar o nó} else if (key.equals (e.Key)) {retries = 0; } else {e = e.next; } // EXATIVAS Adicionar 1 aqui sempre e determine se ele excede o valor máximo} else if (++ Bettries> max_scan_retries) {Lock (); quebrar; // Quando as tentativas são números uniformes, determine se o primeiro mudou} else if ((tentativas & 1) == 0 && (f = EntryForHash (this, hash))! = Primeiro) {e = primeiro = f; tentativas = -1; }} retornar node;} // spin esperando para adquirir bloqueio (remover e substituir as operações) private void scanndlock (chave do objeto, int hash) {// Obtenha o nó do cabeçalho da lista vinculada de acordo com a hashentry do código de hash <k, v> primeiro = entradas (this, hash); Hashentry <k, v> e = primeiro; Int Bettries = -1; // gire while (! Trylock ()) {hashentry <k, v> f; if (experimentas <0) {// transfira a lista vinculada para localizar o nó se (e == null || key.equals (e.key)) {experimentas = 0; } else {e = e.next; } // EXATIVAS Adicionar 1 aqui sempre e determine se ele excede o valor máximo} else if (++ Bettries> max_scan_retries) {Lock (); quebrar; // Quando as tentativas são números uniformes, determine se o primeiro mudou} else if ((tentativas & 1) == 0 && (f = EntryForHash (this, hash))! = Primeiro) {e = primeiro = f; tentativas = -1; }}}Como mencionamos anteriormente, coloque, remova e substitua as operações em bloqueios segmentados, exigem que o bloqueio seja adquirido primeiro. Somente após a obtenção com sucesso da trava, a próxima operação pode ser executada. Se a aquisição falhar, o spin será executado. A operação de rotação também é adicionada no JDK1.7. Para evitar suspensão e despertar frequentes de threads, ele pode melhorar o desempenho durante operações simultâneas. O ScanndlockForput é chamado no método PUT, e o scanndlock é chamado nos métodos Remover e Substituir. Os dois métodos de rotação são aproximadamente os mesmos, aqui analisamos apenas o método ScanndlockForput. Primeiro de tudo, você deve obter o nó do cabeçalho da lista vinculada com base no código de hash. Em seguida, o thread entrará no loop while para executar. A única maneira de sair do loop é adquirir com êxito a trava, e o thread não será suspenso durante esse período. Quando o loop é apenas inserido, o valor das tentativas é -1. Neste momento, o thread não tentará adquirir o bloqueio imediatamente. Em vez disso, primeiro encontrará o nó correspondente à chave (se não for encontrada, uma nova será criada) e, em seguida, definirá as tentativas para 0. Em seguida, tentará adquirir o bloqueio repetidamente. O valor das tentativas correspondentes também será adicionado 1 de cada vez, até que o número máximo de tentativas exceda o número máximo de tentativas. Se o bloqueio não tiver sido obtido, o método de bloqueio será chamado para bloquear e obter. Durante a tentativa de adquirir o bloqueio, ele verificará se o nó do cabeçalho foi alterado todas as outras vezes (as tentativas são uniformes). Se for alterado, redefine as tentativas de volta para -1 e repita o processo agora. É isso que o tópico faz ao girar. Deve -se notar que, se o nó da cabeça tiver sido detectado para ser alterado durante a rotação, o tempo de rotação da rosca será estendido.
10. Quais operações são feitas ao expandir a tabela de hash?
// hash novamente @suppresswarnings ("desmarcado") Realé de vazio privado (hashentry <k, v> node) {// Obtenha a referência à antiga tabela de hash Hashentry <k, v> [] OldTable = tabela; // obtenha a capacidade da tabela antiga de hash int antiga = OldTable.Length; // Calcule a capacidade da nova tabela de hash (2 vezes a tabela antiga de hash) int newCapacity = OldCapacity << 1; // calcule o novo limite do elemento limite = (int) (newCapacity * LoadFactor); // Crie uma nova hashentry da matriz de hashentry <k, v> [] newTable = (hashentry <k, v> []) nova hashentry [newcapacity]; // gerar novo valor de máscara int sizemask = newcapacity - 1; // Tranquilidade através de todos os elementos da tabela antiga para (int i = 0; i <OldCapacity; i ++) {// Obtenha o nó de cabeçalho da lista vinculada hashentry <k, v> e = OldTable [i]; if (e! = null) {hashentry <k, v> next = e.next; // Calcule o índice do elemento na nova tabela int idx = e.hash & sizemask; // o próximo está vazio para indicar que existe apenas um nó na lista vinculada se (next == null) {// coloque o nó diretamente na nova tabela newTable [idx] = e; } else {hashentry <k, v> lastrun = e; int lastIdx = idx; // Posicione o nó LASTRUN e coloque diretamente o nó após o lastrun na nova tabela para (hashentry <k, v> last = next; last! = Null; last = last.next) {int k = last.hash & sizemask; if (k! = lastIdX) {lastIdx = k; lastrun = last; }} newTable [lastIdX] = lastrun; // transmitir os elementos antes do nó LASTRUN da lista vinculada, copie -os para a nova tabela por sua vez para (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] = nova hashentry <k, v> (h, p.key, v, n); }}}}} // Calcule o subscrito do nó de entrada na nova tabela int nodeIndex = node.hash & sizemask; // Adicione o nó recebido ao nó do cabeçalho do link link Node.setNext (newTable [NodeIndex]); // Troque a nova tabela elemento de subscrito especificado com o nó de entrada newTable [nodeIndex] = node; // apontar a referência da tabela de hash para a nova tabela de tabela = newTable;}O método Rehash é chamado no método put. Sabemos que, quando o método put for colocado, o novo elemento será criado e adicionado à matriz de hash. Quanto maior ocorra a possibilidade de conflitos de hash, maior o desempenho da tabela de hash também diminuirá. Portanto, toda vez que a operação de put, ele verificará se o número total de elementos excede o limite. Se exceder o limite, o método Rehash será chamado para expandir a capacidade. Como o comprimento da matriz não pode mais ser alterado depois de determinado, uma nova matriz precisa ser criada para substituir a matriz original. A partir do código, você pode saber que a matriz recém -criada é o dobro do comprimento da matriz original (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版本。
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.