Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 66
Спасибо, было приятно убедится, что все происходит именно так, как и должно было :)
P.S. Местами шаблоны Java накладывают свои ограничения, например нельзя массив типа шаблона создать…
P.S. Местами шаблоны Java накладывают свои ограничения, например нельзя массив типа шаблона создать…
Что вы имеете ввиду, говоря «массив типа шаблона»? Generic?
Я говорю массив типа E создать нельзя, написав new E[len], как собственно и просто объект.
Ну с объектом всё понятно — во время компиляции же неизвестно, какой конструктор необходимо вызвать
Какой конструктор? Если не изменяет память, то при создании списка все элементы инициализируются значением null. А список хранит в себе ссылки на объекты, причем все наследуются от object. Так что хранить в списке можно и пользовательские типы
Когда вы пишите
MyClass[] arr = new MyClass[10];
10 раз вызовется стандартный конструктор класса MyClass. Поэтому нельзя создать объект типа E, неясно что вызывать!
MyClass[] arr = new MyClass[10];
10 раз вызовется стандартный конструктор класса MyClass. Поэтому нельзя создать объект типа E, неясно что вызывать!
Видимо, Вы программируете на чём-то отличном от Java. В Java new MyClass[10] создает только массив, объектов класса MyClass он не создаёт.
Просто речь в статье шла об ArrayList, я позволил себе предположить, что вы в своем комментарии именно его сократили до «массив». В остальном же полностью с вами согласен
Нет, элементы массива в Java при создании не создаются, инициализируются в null. Здесь скорее проблема в том, что тип массива также не может быть определён во время компиляции. В отличие от дженериков, которые чисто языковая фича, типы Object[] и String[] различны
Вы правы, товарищи, к вечеру меня потянуло путать с С++, глубоко извиняюсь за то, что привел в заблуждение!
elementData = (E[]) new Object[10];
Никакого приведения типа там нет и быть не может, массив так и остаётся Object[].
Там его нет, но быть может
Например вот такой идиотский класс:
Например вот такой идиотский класс:
public class Holder {
private T[] array;
public Holder() {
//noinspection unchecked
this.array = (T[]) new Object[1];
}
public void set(T element) {
array[0] = element;
}
public T get() {
return array[0];
}
public static void main(String[] args) {
Holder holder = new Holder();
holder.set("Hi");
System.out.println(holder.get());
}
}
вполне себе работает и выдает что нужноВаш //noinspection unchecked как раз и намекает на то, что в реальности никакого приведения типов не происходит. А если бы оно происходило то как раз бы ничего не работало:
String[] d = (String[]) new Object[1];
--> java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
В реальности — не происходит, конечно. Однако жить и работать с получившимся T[] гораздо проще, чем с Object[] — потому не совсем понятно, почему этого не сделали в ArrayList и прочих Collection
Наверное потому, что они появились раньше, чем дженерики, а потом переписывать уже никто не хотел.
Очевидно, что с появлением generic'ов они переписывали этот код. Соответственно, либо приведение каждый раз при создании массива, либо каждый раз при обращении. По-моему первый путь экономнее
Соответственно, либо приведение каждый раз при создании массива, либо каждый раз при обращении. По-моему первый путь экономнееКакое ещё приведение? Ни в первом ни во втором случае нет никакого приведения. И вообще никакого приведения не бывает с дженериками. В реальности array останется массивом Object и в том числе в байткоде. Вы как-то превратно понимаете что такое java-дженерики.
Я все прекрасно понимаю. Есть такая вещь — простота редактирования кода. Я имею ввиду «виртуальное» приведение — то, которое нужно компилятору
А, ок. Да, в случае исходников тут всё понятно — вроде как можно и правда переписать Object[] на T[], но резона, видимо, не было) Да и разницы было бы не много — в некоторых геттерах убралось бы «виртуальное приведение» (T[]). С точки зрения внешнего интерфейса и производительности всё останется идентичным.
Наверное потому, что в Sun старались писать хороший код? По-моему, код, в котором без особой на то нужды игнорируются предупреждения компилятора о типобезопасности generic-ов, не слишком хорош.
А return (T)elementData[index]; по вашему его не генерирует? Невозможно на Java написать генерик коллекцию на основе массива без type-safe warning'а к сожалению
Да, сглупил. Но всё же я остаюсь при своём мнении о «хорошести» кода. Альтернативный аргумент: операция (T) elementData[index] осталась бы корректна, если бы вместо T был реальный тип, а операция (T[]) new Object[capacity] возможна только для generic-типов. По-сути, когда мы пишем приводение к T[], мы на самом деле рассчитываем на то что эта операция не сработает, что несколько странно. В чуть-более сложной ситуации типа class MyCollection<T extends Number> это допущение сразу перестаёт работать:
Кстати, написать коллекцию без warning-ов можно, достаточно передать в конструктор Class<T>. Только это никому не нужно.
class A<T extends Number>:
(T[]) new Object[1];
--> java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.Number;
Кстати, написать коллекцию без warning-ов можно, достаточно передать в конструктор Class<T>. Только это никому не нужно.
Проще говоря, ArrayList ведёт себя как обычный массив. Единственно стоит учитывать, что при переполнении массив удваивается в размере.
Чуть интереснее с TreeMap/TreeSet (красно-чёрные деревья) и HashMap/HashSet (хэш-таблица в виде массива списков).
Чуть интереснее с TreeMap/TreeSet (красно-чёрные деревья) и HashMap/HashSet (хэш-таблица в виде массива списков).
Вам бы книги писать по программированию «для чайников»
Очень все красиво и наглядно.
Очень все красиво и наглядно.
Мне кажется надо продолжать. Особенно мне понравились итоги — краткие выводы: стоимость операций. Добавить еще и мотивацию, вроде: «Используй ArrayList везде, где невозможно обойтись массивом», вообще бы цены не было.
Спасибо, постараюсь учесть в будущих статьях
«Используй ArrayList везде, где невозможно обойтись массивом»По-моему, это не совсем верно. Поправьте, если ошибаюсь, но часто бывают ситуации, когда предпочтительней к примеру LinkedList.
И еще, мне кажется, говоря о коллекциях, стоит упомянуть итераторы.
Судя по недавнему обзору Сравнение потребления памяти у разных структур хранения данных LinkedList уж больно прожорлив по памяти
У LinkedList есть преимущество по скорости при наполнении элементами. При этом проход итератором по списку, подозреваю, будет одинаков.
Не ожидал, что LinkedList так много жрет памяти. Но при относительно больших по размеру объектах разница нивелируется, а учитывая, что ArrayList может выделить под новый элемент в полтора раза больше памяти, тогда он и «пожирней» может оказаться.
Не ожидал, что LinkedList так много жрет памяти. Но при относительно больших по размеру объектах разница нивелируется, а учитывая, что ArrayList может выделить под новый элемент в полтора раза больше памяти, тогда он и «пожирней» может оказаться.
У LinkedList есть преимущество по скорости при наполнении элементами.В большинстве типичных ситуаций это неверно. Тесты показывают, что LinkedList действительно эффективен становится только когда вам нужны операции вставки в середину/удаления из середины (что вполне ожидаемо). Если же вам это не нужно, то лучше использовать ArrayList. Даже если в конкретной ситауции они будет не лучше LL, то будет отставать совсем незначительно.
Ясно. Можно линк на тесты?
Не совсем те тесты, но сойдет:
http://jdevel.wordpress.com/2011/03/01/arraylist-vs-linkedlist/
http://jdevel.wordpress.com/2011/03/01/arraylist-vs-linkedlist/
Добавить еще и мотивацию, вроде: «Используй ArrayList везде, где невозможно обойтись массивом», вообще бы цены не было.
Скорее так — «Если не требуется вставка/удаление в середину коллекции — всегда использовать ArrayList. А если вставка/удаление в середину необходимы — нужно профилировать и сравнивать производительность с LinkedList.»
Prefer interfaces to abstract classes [1]:
List list = new ArrayList();
Ибо:
1. Existing classes can be easily retrofitted to implement a new interface.
2. Interfaces are ideal for defining mixins.
3. Interfaces allow the construction of nonhierarchical type frameworks.
4. Interfaces enable safe, powerful functionality enhancements via the wrapper class idiom.
Это справедливо для любого ООП-языка в-принципе.
___________________________________________________________
1. Effective Java: Programming Language Guide. Joshua Bloch. Publisher: Addison Wesley. First Edition June 01, 2001. ISBN: 0-201-31005-8, 272 pages, Item 16: Prefer interfaces to abstract classes
List list = new ArrayList();
Ибо:
1. Existing classes can be easily retrofitted to implement a new interface.
2. Interfaces are ideal for defining mixins.
3. Interfaces allow the construction of nonhierarchical type frameworks.
4. Interfaces enable safe, powerful functionality enhancements via the wrapper class idiom.
Это справедливо для любого ООП-языка в-принципе.
___________________________________________________________
1. Effective Java: Programming Language Guide. Joshua Bloch. Publisher: Addison Wesley. First Edition June 01, 2001. ISBN: 0-201-31005-8, 272 pages, Item 16: Prefer interfaces to abstract classes
Вы же просто общедоступный исходник прочли по строкам.
Хороших материалов по расходам памяти пока не встречал. Если что-то накопаю, обязательно укажу в след. статьях.
Было уже про память тут
Наверное, стоит добавить, что при удалении элемента (remove) текущая величина capacity не уменьшается. То есть если натолкать в ArrayList методами add() 100500 чисел, то его capacity после этого будет не меньше 100500 и останется таким даже если для всех элементов сделать remove(). Это может привести к своеобразным утечкам памяти. Иногда может оказаться полезным метод trimToSize() или запись вида «a = new ArrayList<T>()» для освобождения старого буфера для ссылок в «a».
Еще можно отметить, что если вы создаете ArrayList и знаете, что положите в него не менее n элементов, то немного эффективнее будет создать его как a = new ArraysList<Integer>(n), чтобы буфер не перераспределялся log n раз.
Еще можно отметить, что если вы создаете ArrayList и знаете, что положите в него не менее n элементов, то немного эффективнее будет создать его как a = new ArraysList<Integer>(n), чтобы буфер не перераспределялся log n раз.
А как же Navigable*(Set|Map) в иерархии классов на первой картинке?
Разве карты относятся к коллекциям?
NavigableSet — да, упущен. А вот NavigableMap (как и SortedMap и, собственно, Map) — не являются Collection-ами.
Не являются коллекциями — значит их реализации в стандартной библиотеке Java не имплементируют Collection<E>? Ну тогда да, но это странное определение. Конечно же, все Map являются коллекциями. Просто их ветка на этом рисунке располагалась бы рядом. Просто почему-то их проигнорировали :(
Note also that the hierarchy consists of two distinct trees — a Map is not a true Collection.
download.oracle.com/javase/tutorial/collections/interfaces/index.html
Или я чего то не понимаю? Вы объясните. Я java изучаю недавно, так что без эмоций прошу.
Наследование коллекций в Java, то что я всегда не понимал…
Недостаток ArrayList в том, что он оперирует объектами, и для примитивов его использовать очень неэффективно, хотя в реальной жизни это часто требуется. Вот пара библиотек, которые оперируют коллекциями из примитивов:
trove.starlight-systems.com/
pcj.sourceforge.net/
trove.starlight-systems.com/
pcj.sourceforge.net/
Если уж приводите ссылку на сорцы, почему бы не ссылаться на свежую версию и в нормальном месте:
hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/ArrayList.java
hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/classes/java/util/ArrayList.java
>Элементы ArrayList могут быть абсолютно любых типов в том числе и null.
И Unboxed-типы тоже? int, например?
И Unboxed-типы тоже? int, например?
Чуть выше Throwable написал — ArrayList оперирует объектами.
Добавлять вы можете любой тип, другой вопрос как он их хранит.
Добавлять вы можете любой тип, другой вопрос как он их хранит.
Есть желание сериализировать и десериализировать ArrayList.
Можно ли его тупо сбрасывать в поток путем
out.writeObject(massiv);
и восстанавливать как
massiv=(ArrayList)in.readObject()?
Можно ли его тупо сбрасывать в поток путем
out.writeObject(massiv);
и восстанавливать как
massiv=(ArrayList)in.readObject()?
Можно, если ваши объекты в списке Serializable, т.е. если мы можете сериализовать ваш объект YourObоject, то можете спокойно кидать в out.writeObject(ArrayList), а потом List massiv = (List)in.readObject().
Другой вопрос в производительности. Я сам не специалист, но есть ощущение что она очень даже хромает. Т.е. у меня большая коллекция таким образом грузится как — то уж очень долго… Думаю переписывать, чтобы вытягивать объекты по очереди и склыдвать уже в новую коллекцию, надеюсь будет быстрее, а будет ли и стоит ли не знаю… Я это, на хлеб этим не зарабатываю если что, тапками не кидайтесь :)
Другой вопрос в производительности. Я сам не специалист, но есть ощущение что она очень даже хромает. Т.е. у меня большая коллекция таким образом грузится как — то уж очень долго… Думаю переписывать, чтобы вытягивать объекты по очереди и склыдвать уже в новую коллекцию, надеюсь будет быстрее, а будет ли и стоит ли не знаю… Я это, на хлеб этим не зарабатываю если что, тапками не кидайтесь :)
Большое спасибо! Пишите ещё! Это как раз тот случай, когда знать хочется и надо и полезно, но не настолько чтобы самому копаться в исходниках, а Ваша статья как раз то что нужно и по объёму и по уровню детализации :)
Великолепная статья. Ваш подход к изложению материала удобен.
(Зачем нужен, плюсы, минусы и т.д.) Кратко, лаконично.
(Зачем нужен, плюсы, минусы и т.д.) Кратко, лаконично.
Если места в массиве не достаточно, новая емкость рассчитывается по формуле (oldCapacity * 3) / 2 + 1Где вы это взяли? В методе grow() вот что написано:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}int newCapacity = oldCapacity + (oldCapacity >> 1);
То есть oldCapacity = oldCapacity + (oldCapacity / 2);
Пример: если вместимость была 10, то станет 15 (10 + (10/2) = 15).
И я проверил только что с помощью рефлексии, именно так это и работает. 10 —> 15 —> 22, и так далее.
habrahabrovec Не забывайте, что статье почти 8 лет. В Java 6 реализация выглядела именно так как описано в статье, посмотреть можно тут
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных в картинках. ArrayList