Основываясь на ваших комментариях, я думаю, что на самом деле все, что вам нужно, это настроенный ArrayList.
На дополнительном примечании , основанном на ваших комментариях к другим ответам, кажется, что вам нужно сделать много произвольного доступа по index , а не по параметру, То есть вы указали, что хотите получить Edge по порядку, в котором он был добавлен, а не указав уникальные параметры, и что вы можете захотеть получить доступ к этому порядку крайне непоследовательным образом. Для случая произвольного доступа производительность этой структуры данных будет лучше, чем для предложенного выше пользовательского набора, , поскольку платит высокую начальную стоимость за время вставки O (N), где N растет с размером набора; однако, когда вы делаете произвольный доступ , вы получаете такое же большое O (1) по индексу времени поиска, которое предлагает ArrayList. Для сравнения, для пользовательского набора, даже если вы расширяете LinkedHashSet для поддержания порядка доступа, вы платите O (1) время вставки, но O (N), чтобы перебирать записи по порядку, произвольный доступ время.
Обычно вы платите за ограничение уникальности и забываете об этом позже. В случае набора вы платите ограничение времени доступа позже. Конечно, это еще не конец истории, безусловно, есть решение, которое может удовлетворить оба мира. Предположим, что мы храним больше данных (ах, память по сравнению с процессором / временем), и в структуре данных ниже вместо поиска по списку, чтобы выяснить, есть ли у нас рассматриваемый Edge, мы также поддерживаем внутренний набор. Когда мы идем на вставку, мы сначала пытаемся найти край в наборе (O (1)), когда край не найден, мы добавляем его в набор и в список. Теперь нам нужно сохранить дополнительный Set (это стоимость памяти), чтобы избежать потери времени за просмотр нашего Списка во время вставок.
Пока все хорошо, но теперь нам нужно также определить хеш-функцию, которая генерирует уникальные хэш-коды для того, что вы считаете уникальным. Другими словами, мы хотим убедиться, в общих чертах: hashCode(Edge a) != hashCode(Edge b), где a != b должно удерживаться для некоторого невероятно большого пространства a и b, отличающихся в некотором смысле, который вы определяете. Учитывая, что вы определили такую функцию, вы все же должны заплатить стоимость памяти для хранения набора, но, возможно, это не так уж плохо, если вы действительно заботитесь о стоимости вставки.
Вот простая концепция List, она легко модифицируется, чтобы также поддерживать Set, и вы бы изменили функцию contains ниже, чтобы проверять Set, а не проверять поиск в List, если вы хотите использовать гибридный подход.
public class EdgeArrayList extends ArrayList<Edge>{
@Override
public boolean add(Edge e){
if(contains(e)){
return false;
}
super.add(e);
return true;
}
@Override
public boolean contains(Object o){
if(!(o instanceof Edge))
return false;
Edge e = (Edge) o;
for(Edge item : this){
if(item.source == e.source &&
item.destination == e.destination &&
item.weight == e.weight){
return true;
}
}
return false;
}
}
Тогда использование будет таким, как вы предлагаете, где края, уже содержащиеся в EdgeArrayList, просто не будут добавлены:
EdgeArrayList foo = new EdgeArrayList();
foo.add(new Edge(0, 0, 0));
foo.add(new Edge(0, 0, 0));
В конце этого foo содержит только первый экземпляр Edge со всеми параметрами, установленными в 0 (я проверял это, это действительно работает).
Здесь есть некоторые подводные камни - проверка того, что новый Edge отсутствует в списке, приведет к попаданию O (N) в порядке размера текущего списка N .