Bom, pesquisando na internet eu cheguei a conclusão que o hashset é mais rápido pra procurar os objetos dentro dele porque ele “categoriza” os objetos pelo hashcode.
A analogia que mais me deixou claro isso foi a de uma agenda de telefones aonde cada letra do alfabeto seria uma chave e cada registro seria um elemento a ser categorizado. A vantagem em fazer isso parece obvia, se eu precisar pesquisar um nome que começe com a letra D, eu posso pular todos os registros do A, do B e do C.
O problema é que li que o ideal ao se implementar um hashcode é evitar ao maximo hashcodes iguais pra que ela se torne eficiente. Ora pois, se eu tiver uma agenda e em cada letra da agenda só tiver um registro, qual a vantagem isso vai me dar ? eu vou gastar praticamente o mesmo tempo que eu gastaria caso os registro estivessem simplesmente listados em ordem alfabetica.
Isso me leva a crer que estou perdendo algum detalhe q é o que realmente torna o hashset mais rápido na pesquisa de elementos. O que seria ? porque é mais facil pro hashset comparar hashcodes pra me entregar o elemento do que pra uma arraylist comprar os proprios elementos ? seria porque fazer uma comparação entre tipos primitivos é mais rapido do que chamar o equals de cada elemento ?
O objetivo de uma hash table é transformar um objeto que é a key num INTEIRO de forma que vc possa acessar o seu valor muito rapidamente via uma array, assim:
array[keyAsAnInteger] = value;
O problema é que geralmente vc não tem como criar um array contendo o máximo valor da sua key. Ex:
Três itens:
3 = > "a"
343 => "b"
1.000.000.000 = "c"
Não tem cabimento vc criar um array de tamanho um bilhão para guardar 3 elementos, concorda?
Então a hash map usar o operador MODULO (resto) na key para que ele caiba no array alocado. E quando ela faz um MODULO, pode haver colisões, assim:
int[] array = new int[10];
33 % 10 = 3
13 % 10 = 3
Há várias maneiras de resolver uma colisão, mas geralmente elas são armazenadas linearmente na mesma posição numa lista encadedad e a consulta é LINEAR.
Logo no caso extremo um hash map de tamanho UM, ela se torna uma lista encadeada e qualquer get vai tomar O(n) onde n é o tamanho. O(n) significa que vai tomar um quantidade de tempo proporcional ao tamanho do hash map n, como um full table scan num banco de dados.
Por isso que há o REHASH, que é a EXPANSÃO do array quando a hash map fica muito cheia e as colisões começam a ser um problema de performance. O ideal é começar com um tamanho razoável para não ter que fazer REHASH.
Eu achava que a vantagem do Hashset era que ele organizava os elementos e isso facilitava a busca (que é justamente a vantagem de uma agenda telefonica, que organiza os elementos pra tonar a busca mais rapida) mas pelo que eu entendi a mamata é que ele não precisa procurar aonde está o elemento, ele simplesmente calcula a posição apartir do hashcode. Pensando dessa forma faz sentido que se houver muitas colisões vai haver uma perda de desempenho (afinal, alem de calcular a posição ele vai ter que checar qual dos elementos naquela posição é o que foi procurado e quanto menos elementos tiverem, melhor).
Eu achava que a vantagem do Hashset era que ele organizava os elementos e isso facilitava a busca (que é justamente a vantagem de uma agenda telefonica, que organiza os elementos pra tonar a busca mais rapida) mas pelo que eu entendi a mamata é que ele não precisa procurar aonde está o elemento, ele simplesmente calcula a posição apartir do hashcode. Pensando dessa forma faz sentido que se houver muitas colisões vai haver uma perda de desempenho (afinal, alem de calcular a posição ele vai ter que checar qual dos elementos naquela posição é o que foi procurado e quanto menos elementos tiverem, melhor).
Valeu galera !![/quote]
Só para complementar, existem estruturas de dados que trabalham assim. Nesse caso, eles mantém os elementos ordenados, de forma que é possível aplicar a busca binária para obter os elementos. É o caso da TreeSet.
