Qual é o volume de memória alocado dentro do HashSet para armazenar dois elementos, um com hashCode 0 e outro com 1000000?

Em Java, HashSet é implementado com base em HashMap, onde os elementos são armazenados como chaves. Dentro do HashMap, é utilizado um array de buckets (tabela), cujo tamanho é sempre uma potência de dois, por padrão 16.

Ao adicionar o primeiro elemento, o HashSet aloca um array de 16 buckets. Cada bucket é nulo ou uma lista ligada (ou uma árvore, se houver muitos elementos).

Para dois elementos com hashCode 0 e 1000000:

• O índice do bucket é calculado como hash & (table.length - 1).
• Para hashCode 0, o índice será 0.
• Para hashCode 1000000 (em binário), o índice será 1000000 & 15.

O número 1000000 em binário termina em 0, portanto o índice será 0.

Assim, ambos os elementos cairão no mesmo bucket (índice 0), e dentro desse bucket haverá uma lista ligada de dois elementos.

Uso de memória:

• Array de buckets: 16 referências (cada uma de 4 ou 8 bytes dependendo da JVM).
• Dois objetos Node (elementos internos do HashMap), cada um contendo chave, valor (para HashSet, um valor fictício), referência ao próximo elemento e hash.

No total, é alocado um array de 16 elementos e dois objetos Node, ligados em uma cadeia em um bucket.

Exemplo:

HashSet<Integer> set = new HashSet<>();
set.add(0);       // hashCode = 0
set.add(1000000); // hashCode = 1000000

Ambos os elementos estarão no bucket com índice 0, o que pode levar à degradação do desempenho na busca.