Explicação sobre listas e conjuntos de String

Olá!

Além de fazer o que o exercício pede, quis também fazer o mesmo teste criando listas e conjuntos de String.

Fiz as mesmas operações pedidas para inteiros, porém o resultado é diferente do esperado. As buscas em um conjunto de String foi mais lenta que numa lista de String.

Alguém pode me indicar o porquê disso?

Segue os tempos que obtive no console:

Tempo para criar lista de inteiros: 7 ms
Tempo para buscar na lista de inteiros: 784 ms
Tempo para criar lista de String: 1457 ms
Tempo para buscar na lista de String: 1966 ms
Tempo para criar conjunto de inteiros: 10 ms
Tempo para buscar no conjunto de inteiros: 5 ms
Tempo para criar conjunto de String: 2339 ms
Tempo para buscar no conjunto de String: 2009 ms
Tempo total lista de inteiros: 792 ms
Tempo total lista de String: 3423 ms
Tempo total conjunto de inteiros: 15 ms
Tempo total conjunto de String: 4348 ms

Para efeito de consulta, os métodos que utilizei para criar e buscar listas de String (e analogamente, conjuntos de String) seguem abaixo:

public void criaListaDeString( List< String > lista )
    {
        String aux = "a";
        long inicio, fim;

        inicio = System.currentTimeMillis();

        for( int i = 0; i < 30000; i ++ )
        {
            aux = aux + "a";
            lista.add( aux );
        }
        fim = System.currentTimeMillis();

        System.out.println( "Tempo para criar lista de String: " + ( fim - inicio ) + " ms" );
    }

public void confereListaDeString( List< String > lista )
    {
        String aux = "a";
        long inicio, fim;

        inicio = System.currentTimeMillis();

        for( int i = 0; i < 30000; i ++ )
        {
            aux = aux + "a";
            lista.add( aux );
        }
        fim = System.currentTimeMillis();

        System.out.println( "Tempo para buscar na lista de String: " + ( fim - inicio ) + " ms" );
    }

EDIT:

Somente após postar que percebi que as linhas estão trocadas de posição dentro do for. Alterei no meu código e o resultado foi esse:

Tempo para criar lista de inteiros: 6 ms
Tempo para buscar na lista de inteiros: 783 ms
Tempo para criar lista de String: 1433 ms
Tempo para buscar na lista de String: 2434 ms
Tempo para criar conjunto de inteiros: 10 ms
Tempo para buscar no conjunto de inteiros: 4 ms
Tempo para criar conjunto de String: 2039 ms
Tempo para buscar no conjunto de String: 2082 ms
Tempo total lista de inteiros: 790 ms
Tempo total lista de String: 3868 ms
Tempo total conjunto de inteiros: 14 ms
Tempo total conjunto de String: 4122 ms

agora sim o tempo de busca no conjunto de String está mais rápido (por pouco) que a busca na lista de String. Essa alteração na ordem influencia em que?

EDIT2:

Galera, notei meu erro. Para facilitar, fiz o velho "copia e cola" e esqueci de alterar o add para contains. Agora os resultados estão coerentes.

Tempo para criar lista de inteiros: 5 ms
Tempo para buscar na lista de inteiros: 783 ms
Tempo para criar lista de String: 1739 ms
Tempo para buscar na lista de String: 4307 ms
Tempo para criar conjunto de inteiros: 12 ms
Tempo para buscar no conjunto de inteiros: 4 ms
Tempo para criar conjunto de String: 1973 ms
Tempo para buscar no conjunto de String: 1745 ms
Tempo total lista de inteiros: 789 ms
Tempo total lista de String: 6046 ms
Tempo total conjunto de inteiros: 16 ms
Tempo total conjunto de String: 3718 ms