Реализация метода удаления API коллекции
Я взглянул на API коллекции Java. Интерфейс Collection определяет метод удаления следующим образом:
public interface Collection<E> {
// other methods
boolean add(E e);
boolean remove(Object o);
}
Вы можете видеть, что параметр метода удаления имеет тип Object вместо типа элемента коллекции E. Я понимаю логику этого дизайнерского решения: я предпочитаю получить ложь, а не ClassCastException. Это также освобождает клиентский код от приведения объектов перед вызовом этого метода.
Однако странность заключается в реализации метода удаления в некоторых коллекциях. Возьмем, к примеру, реализацию ArrayList:
public class ArrayList<E> extends AbstractList<E> {
//Partial listing
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i])) //heeeeeeeeer!!!!!!!!!
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
}
Здесь реализация вызывает метод равенства для внешнего объекта o, а не для «доверенных» элементов коллекции. Не безопаснее ли вместо этого вызвать метод равенства для элементов коллекции (es[i].equals(o))? Например, если o — это какой-то вредоносный объект, который не соответствует контракту равенства, метод удаления может удалить случайные элементы из коллекции:
class MalObject {
@Override
public boolean equals(Object o) {
return true;
}
}
В текущей реализации удаления вызов list.remove(malObject) будет случайным образом удалять элементы из списка.
Я не вижу очевидной причины, почему бы вместо этого не вызвать метод eequals для элементов коллекции. В чем причина этой реализации, есть ли в этом какая-то польза?
Ответы 1
Ваш вопрос предполагает, что элементы внутри коллекции являются «доверенными», а элемент, который вы передаете методу удаления, является «вредоносным».
Ты придумываешь всякую ерунду. Слово «злонамеренный» здесь бессмысленно. Если вы на самом деле имеете в виду: этот объект создан сущностью, которая намеревается заставить вашу машину действовать против вашего желания, то вы уже проиграли, JVM вообще не защищена; если объект «превратился в кучу», созданный вредоносным объектом, то все. Все кончено. Например, тривиально, что при использовании HashSet или HashMap эти коллекции должны вызывать .hashCode() на предоставленном объекте, чтобы функционировать, и это также может с тем же успехом форматировать ваши дисководы.
Таким образом, есть два варианта:
- Вы имели в виду «злонамеренный» как «ненадежный». В этом случае этот вопрос является спорным: вы уже скомпрометированы, переключение вызова
equalsне будет иметь ни малейшего значения; ты такой же скомпрометированный. - Вы имели в виду другое. В этом случае: что вы имели в виду и объясните, почему
o«более вредоносен», чем элементы в коллекции.
Не безопаснее ли вызывать метод равенства для элементов коллекции?
Тогда это было бы «нет», если только я не упустил какую-то ключевую мысль, а вы имели в виду другое. Ни один из них не безопаснее другого; для целей безопасности совершенно не важно, каким образом вы вызываете эти методы.
В текущей реализации удаления вызов list.remove(malObject) будет случайным образом удалять элементы из списка.
Нет, это удалит первый проверенный элемент из списка. Для коллекций без определенного порядка это все еще верно, но какой объект «проверяется первым», не определено. Для всех остальных первый объект удаляется. Это идентично обратному сценарию: если объекты в списке имеют это глупое определение equals, произойдет то же самое. А спецификация Коллекции всего этого требует.
В чем причина этой реализации, есть ли в этом какая-то польза?
Да, есть. Для начала он сохраняет нулевую проверку: коллекции могут, если в конкретной реализации не указано иное, содержать нулевое значение. Определение remove рассматривает null как имеющее значение и согласованность семантического равенства (в отличие от SQL, где NULL всегда определяется как представление «неизвестного», а NULL = NULL является NULL (что ложно), а не TRUE) - Вызов list.remove(null) в списке с ["Foo", null, "Bar", "Baz", null] результаты в списке содержат ["Foo", "Bar", "Baz", null] — этого требует спецификация. Следовательно, эта проверка if будет сводиться к следующему:
if (es[i] != null && es[i].equals(o)) а это больше работы.
Даже без этой проверки на ноль делать наоборот медленнее. Предполагая, что требуется несколько итераций, прежде чем объект будет найден (или, если объекта вообще нет в коллекции, итерация по всем элементам коллекции), каждый раз вызывается один и тот же метод равенства (а именно, метод один из o). Это может быть быстрее в зависимости от миллиона деталей (анализ производительности невероятно сложен, поскольку он зависит от миллиона факторов, которые трудно изолировать). Вероятно, это не будет иметь большого значения, но если это имеет значение, то в пользу того, чтобы каждый раз вызывать одну и ту же реализацию равенства.
@MohamedNasser все объекты должны соответствовать контракту. Вот почему это называется контрактом. Неразумно предполагать, что o с большей вероятностью сломается equals, чем любой e. Если у вас загружены классы с ошибками и поломками, случаются плохие вещи. Замена equals волшебным образом не исчезнет. Хотя у o.equals(es[i]) есть преимущества в производительности, они на самом деле очень незначительны; в основном просто не имеет значения, как именно equals написано. Если ваш код правильный, это не имеет значения. Если у вас нет кода, у вас большие проблемы.
Под «доверенным» я подразумеваю тип элемента коллекции E, известный во время компиляции. Мы верим, что метод равенства E соответствует контракту, поэтому кажется безопаснее вызывать методы равенства для них, а не для o, которое может быть чем угодно. Тем не менее, теперь я понимаю, почему вызов o.equals(es[i]) может быть лучше и эффективнее. Спасибо.