QA (rus)

ArrayList (Implementation class)
Пожалуй, самая часто используемая коллекция. ArrayList инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов.
Так как ArrayList использует массив, то время доступа к элементу по индексу минимально (В отличии от LinkedList). При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево, при этом реальный размер массива (его емкость, capacity) не изменяется. Если при добавлении элемента, оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент Java ArrayList represents an automatic re-sizable array and used in place of array. Since we can not modify size of an array after creating it, we prefer to use ArrayList in Java which re-size itself automatically once it gets full. ArrayList in Java implements List interface and allow null. Java ArrayList also maintains insertion order of elements and allows duplicates opposite to any Set implementation which doesn’t allow duplicates.
ArrayList is not synchronized and should not be shared between multiple threadsArrayList stringList = new ArrayList(); //Generic ArrayList to Store only String objects stringList.add(“Item”); //no error because we are storing String
stringList.add(new Integer(2)); //compilation error
int size = stringList.size();
get value: for, foreach, arraylistwithdata.get(int i)
set value: stringList.set(0,”Item2″);
stingList.clear();
ArrayList stringList = Arrays.asList(new String[]{“One”, “Two”, “Three”); //this is not read only List you can still update value of existing elements: Link
HashMap
основан на хэш-таблицах, реализует интерфейс Map (что подразумевает хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. Данная реализация не дает гарантий относительно порядка элементов с течением времени. Хорошая статья http://habrahabr.ru/post/128017/HashMap accept null while Hashtable doesn’t, HashMap is not synchronized, HashMap is fast and so on along with basics like its stores key and value pairs.
Since hashcode is same, bucket location would be same and collision will occur in HashMap, Since HashMap use LinkedList to store object, this entry (object of Map.Entry comprise key and value ) will be stored in LinkedListНовоявленный объект hashmap, содержит ряд свойств:
table — Массив типа Entry[], который является хранилищем ссылок на списки (цепочки) значений;
loadFactor — Коэффициент загрузки. Значение по умолчанию 0.75 является хорошим компромиссом между временем доступа и объемом хранимых данных;
threshold — Предельное количество элементов, при достижении которого, размер хэш-таблицы увеличивается вдвое. Рассчитывается по формуле (capacity * loadFactor);
size — Количество элементов HashMap-а;
HashMap(capacity) и HashMap(capacity, loadFactor)hashmap.put(“0”, “zero”); // put value
При добавлении элемента, последовательность шагов следующая:
Сначала ключ проверяется на равенство null. Если это проверка вернула true, будет вызван метод putForNullKey(value) (вариант с добавлением null-ключа рассмотрим чуть позже).
Далее генерируется хэш на основе ключа. Для генерации используется метод hash(hashCode), в который передается key.hashCode().
С помощью метода indexFor(hash, tableLength), определяется позиция в массиве, куда будет помещен элемент.
Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Хэш и ключ нового элемента поочередно сравниваются с хэшами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается.
Если же предыдущий шаг не выявил совпадений, будет вызван метод addEntry(hash, key, value, index) для добавления нового элемента.Read more: http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html#ixzz2rJyD3xNM
HashSet (Implementation)
коллекция, не позволяющая хранить одинаковые объекты(как и любой Set, например, хорошо подходит для стран, уберет дубли даже из цифр). HashSet инкапсулирует в себе объект HashMap (то-есть использует для хранения хэш-таблицу).
Как большинство читателей, вероятно, знают, хеш-таблица хранит информацию, используя так называемый механизм хеширования, в котором содержимое ключа используется для определения уникального значения, называемого хеш-кодом. Этот хеш-код затем применяется в качестве индекса, с которым ассоциируются данные, доступные по этому ключу. Преобразование ключа в хеш-код выполняется автоматически — вы никогда не увидите самого хеш-кода. Также ваш код не может напрямую индексировать хеш-таблицу. Выгода от хеширования состоит в том, что оно обеспечивает константное время выполнения методов add(), contains(), remove() и size() , даже для больших наборов.
Если Вы хотите использовать HashSet для хранения объектов СВОИХ классов, то вы ДОЛЖНЫ переопределить методы hashCode() и equals(), иначе два логически-одинаковых объекта будут считаться разными, так как при добавлении элемента в коллекцию будет вызываться метод hashCode() класса Object (который скорее-всего вернет разный хэш-код для ваших объектов).
Важно отметить, что класс HashSet не гарантирует упорядоченности элементов, поскольку процесс хеширования сам по себе обычно не порождает сортированных наборов. Если вам нужны сортированные наборы, то лучшим выбором может быть другой тип коллекций, такой как класс TreeSet.public void onClick(View v) {
HashSet myHashSet = new HashSet();
myHashSet.add(“Россия”);
myHashSet.add(“Франция”);
myHashSet.add(“Гондурас”);
myHashSet.add(“Кот-Д’Ивуар”); // любимая страна всех котов// Получим размер HashSet
textViewInfo.setText(“Размер HashSet = ” + myHashSet.size());
}// Конвертируем HashSet в массив
String[] myArray = {};
myArray = myHashSet.toArray(new String[myHashSet.size()]);// Выводим массив в ListView
final ListView lView = (ListView) findViewById(R.id.listView1);
adapter = new ArrayAdapter(this,
android.R.layout.simple_list_item_1, myArray);
lView.setAdapter(adapter);
}Если сортировка для вас важна, то используйте TreeSet.
public void onClick(View v) {
SortedSet stringset = new TreeSet();
stringset.add(“Россия”);
stringset.add(“Франция”);
stringset.add(“Гондурас”);
stringset.add(“Кот-Д’Ивуар”); // любимая страна всех котовtextViewInfo.setText(stringset.toString());
}
Iterator
Представленный в релизе JDK 1.2 языка Java интерфейс java.util.Iterator обеспечивает итерацию контейнерных классов. Каждый Iterator реализует методы next() и hasNext() и дополнительно может поддерживать метод remove(). Итераторы создаются соответствующими контейнерными классами, как правило методом iterator().
Метод next() переводит итератор на следующее значение и возвращает указываемое значение итератору. При первоначальном создании итератор указывает на специальное значение, находящееся перед первым элементом, поэтому первый элемент можно получить только после первого вызова next(). Для определения момента, когда все элементы в контейнере были перебраны, используется тестовый метод hasNext(). Следующий пример демонстрирует простое использование итераторов:
Iterator iter = list.iterator();
//Iterator iter = list.iterator(); в J2SE 5.0
while (iter.hasNext())
System.out.println(iter.next());
Для коллекции типов, поддерживающей подобное, метод итератора remove() удаляет последний ‘посещенный’ элемент из контейнера. Почти все остальные типы модификации контейнера во время итерации являются небезопасными.
Кроме того, для java.util.List существует java.util.ListIterator со схожим API, но позволяющем прямую и обратную итерации, обеспечивая определение текущего индекса в списке и переход к элементу по его позиции.
В релиз J2SE 5.0 был представлен интерфейс Iterable для поддержки улучшенного цикла for (foreach) для переборки в коллекциях и массивах. Iterable определяет метод iterator(), возвращающий Iterator. Используя улучшенный цикл for прошлый пример можно переписать в виде
for (MyType obj : list)
System.out.print(obj);
LinkedHashMap
расширяет класс HashMap + реализует интерфейс Map,. Он создает связный список элементов в карте, расположенных в том порядке, в котором они вставлялись. Это позволяет организовать перебор карты в порядке вставки. То есть, когда происходит итерация по коллекционному представлению объекта класса LinkedHashMap, элементы будут возвращаться в том порядке, в котором они вставлялись. Вы также можете создать объект класса LinkedHashMap, возвращающий свои элементы в том порядке, в котором к ним в последний раз осуществлялся доступ.
Рекомендую так же прочитать http://habrahabr.ru/post/129037/Создание:
Map linkedHashMap = new LinkedHashMap();
Добавление: linkedHashMap.put(1, “obj1”);А теперь давайте рассмотрим пример когда свойство accessOrder имеет значение true. В такой ситуации поведение LinkedHashMap меняется и при вызовах методов get() и put() порядок элементов будет изменен — элемент к которому обращаемся будет помещен в конец: Map linkedHashMap = new LinkedHashMap(15, 0.75f, true)Differences:
-HashMap makes absolutely no guarantees about the iteration order. It can (and will) even change completely when new elements are added.
-TreeMap will iterate according to the “natural ordering” of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order.
-LinkedHashMap will iterate in the order in which the entries were put into the map
LinkedHashSet
поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. То есть, когда идет перебор объекта класса LinkedHashSet с применением итератора, элементы извлекаются в том порядке, в каком они были добавлены.A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.This class extends HashSet, but adds no members of its own.
LinkedHashSet maintains a linked list of the entries in the set, in the order in which they were inserted. This allows insertion-order iteration over the set.
That is, when cycling through a LinkedHashSet using an iterator, the elements will be returned in the order in which they were inserted.
The hash code is then used as the index at which the data associated with the key is stored. The transformation of the key into its hash code is performed automatically.HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, and contains methods have constant time complexity O(1).
TreeSet is implemented using a tree structure(red-black tree in algorithm book). The elements in a set are sorted, but the add, remove, and contains methods has time complexity of O(log (n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet(), etc.
LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1).
LinkedList (Implementation class)
Двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки («связки») на следующий и предыдущий узел списка. Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента).
PriorityQueue
единственная прямая реализация интерфейса Queue (не считая LinkedList, который больше является списком, чем очередью).
Эта очередь упорядочивает элементы либо по их натуральному порядку (используя интерфейс Comparable), либо с помощью интерфейса Comparator, полученному в конструкторе.
TreeMap
расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена.
http://www.quizful.net/post/Java-TreeMap
TreeSet
коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n)HashSet:
class offers constant time performance for the basic operations (add, remove, contains and size).
it does not guarantee that the order of elements will remain constant over time
iteration performance depends on the initial capacity and the load factor of the HashSet.
It’s quite safe to accept default load factor but you may want to specify an initial capacity that’s about twice the size to which you expect the set to grow.
TreeSet:
guarantees log(n) time cost for the basic operations (add, remove and contains)
guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via it’s constructor)
doesn’t offer any tuning parameters for iteration performance
offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc
Important points:Both guarantee duplicate-free collection of elements
It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
None of these implementation are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.
So choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.
e.g. Set s = new TreeSet(hashSet);
WeakHashMap
коллекция, использующая слабые ссылки для ключей (а не значений). Слабая ссылка (англ. weak reference) — специфический вид ссылок на динамически создаваемые объекты в системах со сборкой мусора. Отличается от обычных ссылок тем, что не учитывается сборщиком мусора при выявлении объектов, подлежащих удалению. Ссылки, не являющиеся слабыми, также иногда именуют «сильными».
http://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%B0%D0%B1%D0%B0%D1%8F_%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B0Elements in a weak hashmap can be reclaimed by the garbage collector if there are no other strong references to the object, this makes them useful for caches/lookup storage.
Weak reference are not restricted to these hash tables, you can use WeakReference for single objects. They are useful to save resource, you can keep a reference to something but allow it to be collected when nothing else references it. (BTW, a string reference is a normal java reference). There are also weak references which tend not to be as readily collected as soft references (which don’t tend to hang about for long after the last strong reference disappears)

Advertisements

Java terms (Collections)

Aside

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s