Boa noite!
Antes de mais nada peço desculpas pela postagem gigante.
Sou iniciante em java e estou lendo o curso do Caelum que é muito bom. Na parte de Collections fiquei um pouco confuso e fui procurar outras explicações na internet e acabei me deparando com mais dúvidas. Se os mais experientes ajudarem eu ficarei grato.
Fiz um pequeno programa para comparar performance de várias implementaçoes da Collections e para minha surpresa, os resultados não são como esperados. ArrayList por exemplo é mais rápido do que LinkedList em todas operações que eu tentei e pelo que eu entendei isso não deveria acontecer.
package br.com.collections.teste.performance;
public class Temporizador {
private long start;
private long end;
public void Start() {
start = System.currentTimeMillis();
}
public long End() {
end = System.currentTimeMillis();
return end -= start;
}
}
package br.com.collections.teste.performance;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class MyArrayList {
Collection<Integer> al = new ArrayList<Integer>();
public void Insere(int inc) {
for (int loop = 0 ; loop < inc ; loop++) {
al.add(loop);
}
}
public void Consulta(int inc) {
if (inc > al.size()) {
return;
}
for (int loop = 0 ; loop < inc ; loop++) {
al.contains(loop);
}
}
public void Remove(int inc) {
al.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > al.size()) {
return;
}*/
Iterator<Integer> it = al.iterator();
while (it.hasNext()) {
if (it.next() == inc) {
return;
}
}
}
}
package br.com.collections.teste.performance;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
public class MyLinkedList {
Collection<Integer> ll = new LinkedList<Integer>();
public void Insere(int inc) {
for (int loop = 0; loop < inc ; loop++) {
ll.add(loop);
}
}
public void Consulta(int inc) {
if (inc > ll.size()) {
return;
}
for(int loop = 0; loop < inc; loop++) {
ll.contains(loop);
}
}
public void Remove(int inc) {
ll.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > ll.size()) {
return;
}*/
Iterator<Integer> it = ll.iterator();
while (it.hasNext()) {
if (it.next() == inc) {
return;
}
}
}
}
package br.com.collections.teste.performance;
import java.util.Collection;
import java.util.Enumeration;
import java.util.Iterator;
import java.util.Vector;
public class MyVector {
Collection<Integer> vtr = new Vector<Integer>();
public void Insere(int inc) {
for (int loop = 0; loop < inc ; loop++) {
vtr.add(loop);
}
}
public void Consulta(int inc) {
if (inc > vtr.size()) {
return;
}
for(int loop = 0; loop < inc; loop++) {
vtr.contains(loop);
}
}
public void Remove(int inc) {
vtr.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > ll.size()) {
return;
}*/
Enumeration e = ((Vector<Integer>) vtr).elements();
while(e.hasMoreElements()) {
if (e.nextElement() == (Integer) inc) {
return;
}
}
}
}
package br.com.collections.teste.performance;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
public class MyLinkedList {
Collection<Integer> ll = new LinkedList<Integer>();
public void Insere(int inc) {
for (int loop = 0; loop < inc ; loop++) {
ll.add(loop);
}
}
public void Consulta(int inc) {
if (inc > ll.size()) {
return;
}
for(int loop = 0; loop < inc; loop++) {
ll.contains(loop);
}
}
public void Remove(int inc) {
ll.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > ll.size()) {
return;
}*/
Iterator<Integer> it = ll.iterator();
while (it.hasNext()) {
if (it.next() == inc) {
return;
}
}
}
}
package br.com.collections.teste.performance;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
public class MyHashSet {
Collection<Integer> hs = new HashSet<Integer>();
/* @Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((hs == null) ? 0 : hs.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
MyHashSet other = (MyHashSet) obj;
if (hs == null) {
if (other.hs != null)
return false;
} else if (!hs.equals(other.hs))
return false;
return true;
}*/
public void Insere(int inc) {
for (int loop = 0 ; loop < inc ; loop++) {
hs.add(loop);
}
}
public void Consulta(int inc) {
if (inc > hs.size()) {
return;
}
for (int loop = 0 ; loop < inc ; loop++) {
/*if (hs.contains(loop)) {
System.out.println("Encontrou: ");
return;
}*/
hs.contains(loop);
}
}
public void Remove(int inc) {
hs.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > al.size()) {
return;
}*/
Iterator<Integer> it = hs.iterator();
while (it.hasNext()) {
int tmp = it.next();
if (tmp == inc) {
//System.out.println("Encontrou: " + tmp);
return;
}
}
}
}
package br.com.collections.teste.performance;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class MyHashMap {
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
public void Insere(int inc) {
for (int loop = 0 ; loop < inc ; loop++) {
hm.put(loop, loop);
}
}
public void Consulta(int inc) {
if (inc > hm.size()) {
return;
}
for (int loop = 0 ; loop < inc ; loop++) {
/*if (hs.contains(loop)) {
System.out.println("Encontrou: ");
return;
}*/
hm.containsKey(loop);
}
}
public void Remove(int inc) {
hm.remove(inc);
}
public void IteratorFindOneEntry(int inc) {
/*if (inc > al.size()) {
return;
}*/
Set<Integer> KeySet = hm.keySet();
for(Integer i : KeySet) {
if (i == inc) {
return;
}
}
}
}
-
A performance do LinkedList deveria ser melhora em algumas operações do que ArrayList? Ainda, o Vector muitos lugares dizem ser ultrapassado e lento por ser sincronizado, mas para inserir os valores ele foi o mais rápido de todos. O que eu estou fazendo de errado?
-
Eu fiquei muito confuso com o hashcode() e li bastante a resposito, a conclusão que eu cheguei é que o algoritmo tem como objetivo evitar as colisões (por exemplo em HashSet) na indexação e não melhorar a performance, certo? Caso negativo, pode me explicar com exemplos (pq eu sou bem anta mesmo).
-
Na pratica é impossível evitar colisões e a qualidade e tamanho do hascode influenciam, pelo que eu entendi o Set começa com 16 posições (0 até 15) e usa o hashcode() da Key e o tamanho da tablea index para achar como distribuir. Se ele achar um valor com a mesmo hashcode e mesma key, ele substitui o valor. Então a minha dúvida é, quão comum é uma colisão na pratica e dados serem trocados por um valor errado? A questão de sobescrever o valor (V -> Value) não deveria ser validado? Eu imaginava que ambos valores fossem importantes. Talvez eu não entenda muito bem a utilização dessa forma de armazenamento com os exemplos que vi na internet.
ref. https://www.javatpoint.com/working-of-hashmap-in-java
- Tentando entender o hashcode() achei essa explicação de hashmap
E vi essa parte
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20 ) ^ (h >>> 12 );
return h ^ (h >>> 7 ) ^ (h >>> 4 );
Eu não sabia o que o >>> fazia, então achei nesse link abaixo uma explicação que é para evitar overflow já que o java não aceita unsigned inteeiro.
Eu entendi que o número que você passar na frente do >>> ele vai adicionar em zeros a direita e remover o mesmo montante de bits do final. O que eu não entendi é qual o problema do inteiro unsigned e pq isso resolve a conta corretamente. Alguem pode me explicar por favor?
Agradecido.
