Кто-то сказал, что HashSet обеспечивает постоянную производительность при добавлении, удалении, содержании и размере.
Фактический оператор в JavaDocs: «Этот класс обеспечивает постоянную производительность по времени для основных операций (добавление, удаление, содержание и размер), при условии, что хеш-функция правильно распределяет элементы между сегментами ».
Это означает, что вы можете получить медленное время добавления при добавлении чего-либо в набор, если у него есть плохо реализованный метод hashCode.
Следующий код демонстрирует, что может произойти в зависимости от вашей реализации hashCode.
public void testHashSetAddition() {
for(int mod=10; mod <= 100; mod=mod+10 ) {
Set s = new HashSet();
long start = new Date().getTime();
for(int i=0; i<100000; i++) {
s.add(new Foo(i % mod));
}
long end = new Date().getTime();
System.out.println("Mod: " + mod + " - " + (end - start) + "ms");
}
}
class Foo {
private int hc;
public Foo(int i) {
this.hc = i;
}
public int hashCode() {
return hc;
}
}
Результаты были следующими:
Mod: 10 - 22683ms
Mod: 20 - 14200ms
Mod: 30 - 10486ms
Mod: 40 - 8562ms
Mod: 50 - 7761ms
Mod: 60 - 6740ms
Mod: 70 - 5778ms
Mod: 80 - 5268ms
Mod: 90 - 4716ms
Mod: 100 - 3966ms
Затем выполните точно такой же тест для ArrayList:
public void testAddingToArrayList() {
for(int mod=100; mod >= 10; mod=mod-10 ) {
List l = new ArrayList();
long start = new Date().getTime();
for(int i=0; i<100000; i++) {
l.add(new Foo(i % mod));
}
long end = new Date().getTime();
System.out.println("Mod: " + mod + " - " + (end - start) + "ms");
}
}
Дает:
Mod: 100 - 50ms
Mod: 90 - 30ms
Mod: 80 - 40ms
Mod: 70 - 30ms
Mod: 60 - 30ms
Mod: 50 - 40ms
Mod: 40 - 20ms
Mod: 30 - 30ms
Mod: 20 - 30ms
Mod: 10 - 30ms