Ao aplicar HashMap em um ambiente java multithread, existem principalmente as seguintes opções: Use o java.util.Hashtable thread-safe como alternativa Use o método java.util.Collections.synchronizedMap para agrupar o objeto HashMap existente como thread. -seguro. Use a classe java.util.concurrent.ConcurrentHashMap como alternativa, que tem um desempenho muito bom.
Todos os métodos acima usam bloqueios mutex mais ou menos nos detalhes específicos de implementação. Os bloqueios mutex causarão bloqueio de thread, reduzirão a eficiência operacional e poderão causar uma série de problemas, como impasse e inversão de prioridade.
CAS (Compare And Swap) é uma função fornecida pelo hardware subjacente, que pode atomizar a operação de julgar e alterar um valor.
Operações atômicas em Java
No pacote java.util.concurrent.atomic, Java nos fornece muitos tipos atômicos convenientes, que são inteiramente baseados em operações CAS.
Por exemplo, se quisermos implementar um contador público global, podemos:
Copie o código do código da seguinte forma:
privateAtomicInteger contador =newAtomicInteger(3);
publicvoidaddCounter() {
para(;;) {
intoldValue = counter.get();
intnovoValor = valorantigo +1;
if(counter.compareAndSet(oldValue, newValue))
retornar;
}
}
Entre eles, o método compareAndSet verifica se o valor existente do contador é oldValue. Em caso afirmativo, ele é definido como o novo valor newValue. A operação é bem-sucedida e true é retornado, caso contrário, a operação falha e false é retornado.
Ao calcular o novo valor do contador, se outros threads alterarem o valor do contador, compareAndSwap falhará. Neste ponto, precisamos apenas adicionar uma camada de loop externa e continuar tentando esse processo, então, eventualmente, aumentaremos com sucesso o valor do contador em 1. (Na verdade, AtomicInteger já definiu os métodos incrementAndGet e decrementAndGet para as operações +1/-1 comumente usadas. Só precisamos simplesmente chamá-los no futuro)
Além de AtomicInteger, o pacote java.util.concurrent.atomic também fornece os tipos AtomicReference e AtomicReferenceArray, que representam referências atômicas e matrizes de referência atômica (matrizes de referências), respectivamente.
Implementação de lista vinculada sem bloqueio
Antes de implementar um HashMap sem bloqueio, vamos primeiro dar uma olhada no método de implementação relativamente simples de uma lista vinculada sem bloqueio.
Tomemos a operação de inserção como exemplo:
Primeiro precisamos encontrar o nó A na frente da posição a ser inserida e o nó B atrás dela.
Em seguida, crie um novo nó C e faça com que seu próximo ponteiro aponte para o nó B. (Ver Figura 1)
Finalmente, faça com que o próximo ponteiro do nó A aponte para o nó C. (Ver Figura 2)
Porém, durante a operação, é possível que outros threads tenham inserido diretamente alguns nós em A e B (assumidos como D). Se não fizermos nenhum julgamento, isso poderá causar a perda de nós inseridos por outros threads. (Veja a Figura 3) Podemos usar a operação CAS para determinar se o próximo ponteiro do nó A ainda aponta para B ao atribuir um valor. Se o próximo ponteiro do nó A mudar, tente novamente toda a operação de inserção. O código aproximado é o seguinte:
Copie o código do código da seguinte forma:
privatevoidlistInsert (cabeça do nó, nó c) {
para(;;) {
Nó a = findInsertionPlace(head), b = a.next.get();
c.próximo.set(b);
if(a.next.compareAndSwap(b,c))
retornar;
}
}
(O próximo campo da classe Node é do tipo AtomicReference<Node>, que é uma referência atômica apontando para o tipo Node)
A operação de pesquisa de uma lista vinculada sem bloqueio não é diferente daquela de uma lista vinculada comum. A operação de exclusão requer encontrar o nó A na frente do nó a ser excluído e o nó B atrás dele, e usar a operação CAS para verificar e atualizar o próximo ponteiro do nó A para que aponte para o nó B.
Dificuldades e avanços do HashMap sem bloqueio
O HashMap possui principalmente quatro operações básicas: inserção, exclusão, pesquisa e ReHash. Uma implementação típica de HashMap usa um array, e cada elemento do array é uma lista vinculada de nós. Para esta lista vinculada, podemos usar os métodos de operação mencionados acima para realizar operações de inserção, exclusão e pesquisa, mas a operação ReHash é mais difícil.
Conforme mostrado na Figura 4, durante o processo ReHash, uma operação típica é percorrer cada nó da tabela antiga, calcular sua posição na nova tabela e, em seguida, movê-lo para a nova tabela. Durante este período precisamos manipular o ponteiro três vezes:
O próximo ponteiro do ponto A para D
Próximo ponteiro do ponto B para C
Próximo ponteiro do ponto C para E
Essas três operações de ponteiro devem ser concluídas ao mesmo tempo para garantir a atomicidade da operação de movimentação. Mas não é difícil ver que a operação CAS só pode garantir que o valor de uma variável seja verificado e atualizado atomicamente por vez, e não pode atender à necessidade de verificar e atualizar três ponteiros ao mesmo tempo.
Portanto, podemos também mudar nosso pensamento. Como a operação de nós móveis é tão difícil, podemos manter todos os nós em um estado ordenado o tempo todo, evitando assim a operação móvel. Em uma implementação típica de HashMap, o comprimento do array sempre permanece 2i, e o processo de mapeamento do valor Hash para o subscrito do array simplesmente executa uma operação de módulo no comprimento do array (ou seja, apenas os últimos i bits do binário Hash são retido). Quando ReHash, o comprimento da matriz é duplicado para 2i+1, e cada nó na j-ésima lista de colar da matriz antiga é movido para o j-ésimo item na nova matriz ou movido para o j+2i-ésimo item na nova matriz, e sua A única diferença está no i+1º bit do valor Hash (se o i+1º bit for 0, ainda é o j-ésimo item, caso contrário, é o j+2º item).
Conforme mostrado na Figura 5, organizamos todos os nós em ordem crescente de acordo com a ordem invertida do valor Hash (como 1101->1011). Quando o tamanho da matriz é 8, 2 e 18 estão em um grupo; 3, 11 e 27 estão em outro grupo; No início de cada grupo é inserido um nó sentinela para facilitar as operações subsequentes. Para organizar corretamente o nó sentinela na frente do grupo, definimos o bit mais alto do Hash do nó normal (que se torna o bit mais baixo após a inversão) como 1, enquanto o nó sentinela não define esse bit.
Quando a matriz é expandida para 16 (ver Figura 6), o segundo grupo é dividido em um grupo contendo apenas 3 e um grupo contendo 11 e 27, mas a ordem relativa entre os nós não mudou. Desta forma, não precisamos mover nós durante o ReHash.
Detalhes de implementação
Como a cópia do array leva muito tempo durante a expansão, aqui adotamos o método de dividir o array inteiro em blocos e criá-lo preguiçosamente. Desta forma, quando um determinado subscrito é acessado, basta julgar se o bloco onde o subscrito está localizado foi estabelecido (caso contrário, crie-o).
Além disso, o tamanho é definido como o intervalo de subscritos usado atualmente e seu valor inicial é 2. Quando a matriz é expandida, o tamanho só precisa ser duplicado, a contagem é definida para representar o número total de nós atualmente incluídos no HashMap (; sem contar os nós sentinela).
Inicialmente, todos os itens da matriz, exceto o item 0, são nulos. O item 0 aponta para uma lista encadeada com apenas um nó sentinela, representando o ponto inicial de toda a cadeia. A imagem completa inicial é mostrada na Figura 7, na qual o verde claro representa o intervalo de subscritos atualmente não utilizado e as setas pontilhadas representam blocos que existem logicamente, mas não estão realmente estabelecidos.
Inicializar operação de subscrito
Itens nulos na matriz são considerados em estado não inicializado. Inicializar um determinado subscrito significa estabelecer seu nó sentinela correspondente. A inicialização é realizada recursivamente, ou seja, se seu subscrito pai não for inicializado, seu subscrito pai será inicializado primeiro. (O subscrito pai de um subscrito é o subscrito obtido pela remoção do bit binário mais alto.) O código aproximado é o seguinte:
Copie o código do código da seguinte forma:
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==nulo)
inicializeBucket(parentIdx);
Nó fictício =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
Entre eles, getBucket é um método encapsulado para obter o conteúdo de um determinado subscrito no array, e setBucket é o mesmo. listInsert irá inserir o nó fornecido em uma posição adequada a partir da posição especificada. Se um nó com o mesmo hash já existir na lista vinculada, ele retornará o nó existente, caso contrário, retornará o nó recém-inserido.
operação de inserção
Primeiro, use o tamanho do HashMap para modular o hashCode da chave para obter o subscrito do array que deve ser inserido.
Em seguida, determine se o subscrito é nulo e, se for nulo, inicialize o subscrito.
Construa um novo nó e insira-o na posição apropriada. Observe que o valor do hash no nó deve ser o valor do hashCode original após a inversão de bits e a definição da posição mais baixa como 1.
Adicione 1 ao contador de número de nó. Se houver muitos nós após adicionar 1, você só precisará alterar o tamanho para tamanho*2, o que significa expandir a matriz (ReHash).
Localizar operação
Encontre o índice do nó a ser encontrado na matriz.
Determine se o subscrito é nulo. Se for nulo, a falha de pesquisa será retornada.
Entre na lista vinculada a partir da posição correspondente e pesquise sequencialmente até que o nó a ser encontrado seja encontrado ou exceda o intervalo deste grupo de nós.
operação de exclusão
Encontre o índice do nó na matriz que deve ser excluído.
Determine se o subscrito é nulo e, se for nulo, inicialize o subscrito.
Encontre o nó a ser excluído e exclua-o da lista vinculada. (Observe que devido à existência do nó sentinela, qualquer elemento normal é referenciado apenas por seu único nó predecessor. Não há situação em que ele seja referenciado pelo nó predecessor e pelo ponteiro na matriz ao mesmo tempo, então há não há necessidade de modificar vários ponteiros ao mesmo tempo.)
Diminua o contador do número do nó em 1.