Mude para a function de hash do HashMap no Java 8

Em java 8 java.util.Hashmap notei uma mudança de :

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 

para :

 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 

Aparece a partir do código que a nova function é um XOR mais simples dos 16 bits inferiores com o 16 superior deixando os 16 bits superiores inalterados, ao contrário de várias mudanças diferentes na implementação anterior, e dos comentários que isso é menos eficaz em alocar os resultados de funções hash com um alto número de colisões em bits menores para diferentes buckets, mas economiza ciclos de CPU fazendo menos operações.

A única coisa que vi nas notas de lançamento foi a mudança de listas vinculadas para trees balanceadas para armazenar chaves em colisão (o que achei que poderia ter mudado a quantidade de tempo que fazia sentido calcular um bom hash), eu estava especificamente interessado em ver se houve algum impacto esperado no desempenho dessa alteração em grandes mapas hash. Existe alguma informação sobre esta alteração, ou alguém com um melhor conhecimento das funções hash tem uma ideia das implicações desta alteração (se houver, talvez eu apenas tenha entendido mal o código) e se houve alguma necessidade de gerar hash códigos de uma maneira diferente para manter o desempenho ao mudar para o Java 8?

Como você observou: há uma melhoria de desempenho significativa no HashMap no Java 8, conforme descrito no JEP-180 . Basicamente, se uma cadeia hash ultrapassar um certo tamanho, o HashMap irá (sempre que possível) substituí-lo por uma tree binária balanceada. Isso faz com que o “pior cenário” comportamento de várias operações O(log N) vez de O(N) .

Isso não explica diretamente a mudança para o hash . No entanto, eu suporia que a otimização no JEP-180 significa que o impacto no desempenho devido a uma function hash mal distribuída é menos importante e que a análise de custo-benefício para o método hash é alterada; ou seja, a versão mais complexa é menos benéfica em média . (Tenha em mente que quando o método hashcode do tipo de chave gera códigos de alta qualidade, então a ginástica na versão complexa do método hash é uma perda de tempo.)

Mas isso é apenas uma teoria. O raciocínio real para a mudança de hash é, provavelmente, confidencial da Oracle.

Quando eu executei diffs de implementação de hash, vejo diferença de tempo em nano segundos como abaixo (não ótimo, mas pode ter algum efeito quando o tamanho é enorme ~ 1million +) –

7473 ns – java 7

3981 ns– java 8

Se estamos falando de chaves bem formadas e hashmap de tamanho grande (~ milhões), isso pode ter algum impacto e isso se deve à lógica simplificada.

Como a documentação Java diz que a ideia é lidar com a situação em que a implementação antiga da lista Linked realiza O (n) em vez de O (1). Isso acontece quando o mesmo código hash é gerado para um grande dataset sendo inserido no HashMap.

Este não é um cenário normal embora. Para lidar com uma situação em que, depois que o número de itens em um hash for aumentado além de um determinado limite, esse bucket mudará de usar uma linked list de inputs para uma tree binária. No caso de colisões hash altas, isso melhorará o desempenho da pesquisa de O (n) para O (log n), o que é muito melhor e resolve o problema de desempenho.