Implementação HashMap em Java. Como funciona o cálculo do índice de bucket?

Eu estou olhando para a implementação do HashMap em Java e estou preso em um ponto.
Como a function indexFor é calculada?

 static int indexFor(int h, int length) { return h & (length-1); } 

obrigado

Não é calcular o hash , é calcular o balde .

A expressão h & (length-1) faz um pouco AND em h usando length-1 , que é como uma máscara de bits, para retornar apenas os bits de baixa ordem de h , tornando assim uma variante super-rápida de h % length .

O próprio hash é calculado pelo método hashCode() do object que você está tentando armazenar.

O que você vê aqui é calcular o “bucket” para armazenar o object com base no hash h . Idealmente, para evitar colisões, você teria o mesmo número de buckets que o valor máximo possível de h – mas isso poderia exigir muita memory. Portanto, você geralmente tem um número menor de depósitos com risco de colisão.

Se h é, digamos, 1000, mas você só tem 512 baldes em sua matriz subjacente, você precisa saber onde colocar o object. Normalmente, uma operação mod em h seria suficiente, mas isso é muito lento. Dada a propriedade interna do HashMap que o array subjacente sempre tem o número de buckets iguais a 2^n , os engenheiros da Sun poderiam usar a idéia de h & (length-1) , ele faz um bit a bit AND com um número consistindo em todos os 1 ‘ s, praticamente lendo apenas os n bits mais baixos do hash (que é o mesmo que fazer h mod 2^n , apenas muito mais rápido).

Exemplo:

  hash h: 11 1110 1000 -- (1000 in decimal) length l: 10 0000 0000 -- ( 512 in decimal) (l-1): 01 1111 1111 -- ( 511 in decimal - it will always be all ONEs) h AND (l-1): 01 1110 1000 -- ( 488 in decimal which is a result of 1000 mod 512) 

Está calculando o balde do mapa de hash onde a input (par de valor-chave) será armazenada. O ID do hashvalue/buckets length é o valor de hashvalue/buckets length .

Um mapa hash consiste em baldes; os objects serão colocados nesses blocos com base no ID do intervalo.

Qualquer número de objects pode, na verdade, se encheckboxr no mesmo bloco com base em seu valor de hash code / buckets length intervalos. Isso é chamado de “colisão”.

Se muitos objects caírem no mesmo intervalo, durante a pesquisa, o método equals () será chamado para desambiguar.

O número de colisões é indiretamente proporcional ao tamanho do balde.

A resposta acima é muito boa, mas eu quero explicar mais porque o Java pode usar indexFor para criar index

Exemplo, eu tenho um HashMap como este (este teste é em Java7, vejo Java8 mudar HashMap muito, mas eu acho que essa lógica ainda é muito bom)

 // Default length of "budget" (table.length) after create is 16 (HashMap#DEFAULT_INITIAL_CAPACITY) HashMap hashMap = new HashMap<>(); hashMap.put("A",1); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5 hashMap.put("B",2); // hash("B")=70, indexFor(hash,table.length)=70&(16-1) = 6 hashMap.put("P",3); // hash("P")=85, indexFor(hash,table.length)=85&(16-1) = 5 hashMap.put("A",4); // hash("A")=69, indexFor(hash,table.length)=69&(16-1) = 5 hashMap.put("r", 4);// hash("r")=117, indexFor(hash,table.length)=117&(16-1) = 5 

Você pode ver o índice de input com a chave "A" e o object com a chave "P" e o object com a chave "r" tem o mesmo índice ( = 5 ). E aqui está o resultado da debugging depois que eu executo o código acima

insira a descrição da imagem aqui

A tabela na imagem está aqui

 public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { transient HashMap.Entry[] table; ... } 

=> Eu vejo
Se o índice for diferente , uma nova input será adicionada à tabela
Se o índice for o mesmo e o hash for o mesmo , o novo valor será atualizado
Se o índice for o mesmo e o hash for diferente , a nova input apontará para a input antiga (como uma LinkedList ). Então você sabe porque Map.Entry tem campo next

 static class Entry implements java.util.Map.Entry { ... HashMap.Entry next; } 

Você pode verificá-lo novamente lendo o código no HashMap .

Como agora, você pode pensar que o HashMap nunca precisará alterar o tamanho (16) porque indexFor() sempre retorna o valor <= 15, mas não está correto.
Se você olhar para o código HashMap

  if (this.size >= this.threshold ...) { this.resize(2 * this.table.length); 

HashMap irá resize tabela (comprimento da tabela dupla) quando size > = threadhold

O que é threadhold ? threadhold é calculado abaixo

 static final int DEFAULT_INITIAL_CAPACITY = 16; static final float DEFAULT_LOAD_FACTOR = 0.75F; ... this.threshold = (int)Math.min((float)capacity * this.loadFactor, 1.07374182E9F); // if capacity(table.length) = 16 => threadhold = 12 

Qual é o size ? size é calculado abaixo.
Naturalmente, o size aqui não é table.length .
Sempre que você colocar uma nova input no HashMap HashMap precisará criar uma nova input (observe que o HashMap não cria uma nova input quando a chave é a mesma, apenas sobrescreve o novo valor da input existente) e depois o size++

 void createEntry(int hash, K key, V value, int bucketIndex) { ... ++this.size; } 

Espero que ajude