Java: otimize hashset para detecção de duplicata em grande escala

Eu estou trabalhando em um projeto onde estou processando muitos tweets; O objetivo é remover as duplicatas enquanto as processo. Eu tenho os IDs de tweets, que vêm como strings do formato"166471306949304320"

Eu tenho usado umHashSet<String> para isso, o que funciona bem por um tempo. Mas no momento em que chego a cerca de 10 milhões de itens, estou drasticamente atolado e, eventualmente, recebo um erro de GC, presumivelmente a partir da reformulação. Eu tentei definir um tamanho / carga melhor com

tweetids = new HashSet<String>(220000,0.80F);

e isso deixa um pouco mais longe, mas ainda é terrivelmente lento (em torno de 10 milhões está demorando 3x para processar). Como posso otimizar isso? Dado que eu tenho uma idéia aproximada de quantos itens devem estar no conjunto até o final (neste caso, cerca de 20-22 milhões) devo criar um HashSet que rehashes apenas duas ou três vezes, ou seria a sobrecarga para tal conjunto incorrer em muitas penalidades de tempo? As coisas funcionariam melhor se eu não estivesse usando uma String, ou se eu definir uma função HashCode diferente (que, neste caso, de uma instância específica de uma String, não tenho certeza de como fazer)? Esta parte do código de implementação está abaixo.

tweetids = new HashSet<String>(220000,0.80F); // in constructor
duplicates = 0;
...
// In loop: For(each tweet)
String twid = (String) tweet_twitter_data.get("id");
// Check that we have not processed this tweet already
if (!(tweetids.add(twid))){
    duplicates++;
    continue; 
}

SOLUÇÃO

Graças às suas recomendações, resolvi-o. O problema era a quantidade de memória necessária para as representações hash; primeiro,HashSet<String> foi simplesmente enorme e desnecessário porque oString.hashCode() é exorbitante para esta escala. Em seguida, tentei um Trie, mas ele caiu em pouco mais de 1 milhão de entradas; realocar as matrizes era problemático. Eu usei umHashSet<Long> para melhor efeito e quase conseguiu, mas a velocidade decaiu e finalmente caiu na última etapa do processamento (cerca de 19 milhões). A solução veio com a partida da biblioteca padrão e usandoTrove. Ele terminou 22 milhões de registros alguns minutos mais rápido do que não verificar as duplicatas. A implementação final foi simples e ficou assim:

import gnu.trove.set.hash.TLongHashSet;
...
    TLongHashSet tweetids; // class variable
... 
    tweetids = new TLongHashSet(23000000,0.80F); // in constructor
...
    // inside for(each record)
    String twid = (String) tweet_twitter_data.get("id");
    if (!(tweetids.add(Long.parseLong(twid)))) {
        duplicates++;
        continue; 
    }