Como um HashSet oferece operação de adição de tempo constante?

Eu estava lendo os javadocs no HashSet quando me deparei com a interessante declaração:

Esta classe oferece desempenho de tempo constante para as operações básicas (adicionar, remover, conter e tamanho)

Isso me confunde muito, pois não entendo como é possível obter desempenho de tempo constante, O (1), para uma operação de comparação. Aqui estão os meus pensamentos:

Se isso for verdade, não importa quantos dados eu esteja despejando no meu HashSet, poderei acessar qualquer elemento em tempo constante. Ou seja, se eu colocar 1 elemento no meu HashSet, levará a mesma quantidade de tempo para encontrá-lo, como se eu tivesse um googolplex de elementos.

No entanto, isso não seria possível se eu tivesse um número constante de buckets ou uma função de hash consistente, pois para qualquer número fixo de buckets, o número de elementos nesse bucket aumentará linearmente (embora lentamente, se o número for grande). suficiente) com o número de elementos no conjunto.

Então, a única maneira de isso funcionar é ter uma função de hash alterada toda vez que você insere um elemento (ou algumas vezes). Uma função simples de hash que nunca colisão satisfaria essa necessidade. Um exemplo de brinquedo para seqüências de caracteres poderia ser: Pegue o valor ASCII das sequências e concatená-las juntas (porque a adição pode resultar em um conflito).

No entanto, essa função hash e qualquer outra função hash desse tipo provavelmente falhará em seqüências ou números grandes o suficiente, etc. O número de buckets que você pode formar é imediatamente limitado pela quantidade de espaço de pilha / heap que você tem, etc. , ignorar locais na memória não pode ser permitido indefinidamente; portanto, você precisará preencher as lacunas.

Mas se, em algum momento, houver um recálculo da função hash, isso poderá ser tão rápido quanto encontrar um polinômio que passe pelos pontos N ou O (nlogn).

Assim chega minha confusão. Embora eu acredite que o HashSet possa acessar elementos no tempo O (n / B), onde B é o número de buckets que decidiu usar, não vejo como um HashSet poderia executar funções de adição ou obtenção em O ( 1 vez.

Nota:Esta postagem eesta postagem ambos não abordam as preocupações que listei ..