Конкретные классы коллекций

java.util.ArrayList - этот класс расширяет AbstractList и весьма похож на класс Vector. Он также динамически расширяется, как Vector, однако его методы не являются синхронизированными, вследствие чего операции с ним выполняются быстрее. Для того, чтобы воспользоваться синхронизированной версией ArrayList, можно применить вот такую конструкцию:

List l = Collections.synchronizedList(new ArrayList(...)); public class Test { public Test() { } public static void main(String[] args) { Test t = new Test(); ArrayList al = new ArrayList(); al.add("First element"); al.add("Second element"); al.add("Third element"); Iterator it = al.iterator(); while(it.hasNext()) { System.out.println((String)it.next()); } System.out.println("\n"); al.add(2,"Insertion"); it = al.iterator(); while(it.hasNext()){ System.out.println((String)it.next()); } }}

Пример 14.15.

Результатом будет:

First elementSecond elementThird element Firts elementSecond elementInsertionThird element

Пример 14.16.

java.util.LinkedList - представляет собой реализацию интерфейса List. Он реализует все методы интерфейса List, помимо этого добавляются еще новые методы, которые позволяют добавлять, удалять и получать элементы в конце и начале списка. LinkedList является двухсвязным списком и позволяет перемещаться как от начала в конец списка, так и наоборот. LinkedList удобно использовать для организации стека.

public class Test { public Test() { } public static void main(String[] args) { Test test = new Test(); LinkedList ll = new LinkedList(); ll.add("Element1"); ll.addFirst("Element2"); ll.addFirst("Element3"); ll.addLast("Element4"); test.dumpList(ll); ll.remove(2); test.dumpList(ll); String element = (String)ll.getLast(); ll.remove(element); test.dumpList(ll); } private void dumpList(List list){ Iterator it = list.iterator(); System.out.println(); while(it.hasNext()){ System.out.println((String)it.next()); } }}

Пример 14.17.

Результатом будет:

Element3Element2Element1Element4 Element3Element2Element4 Element3Element2

Пример 14.18.

Классы LinkedList и ArrayList имеют схожую функциональность. Однако с точки зрения производительности они отличаются. Так, в ArrayList заметно быстрей (примерно на порядок) осуществляются операции прохода по всему списку (итерации) и получения данных. LinkedList почти на порядок быстрее выполняет операции удаления и добавления новых элементов.

java.util.Hashtable - расширяет абстрактный класс Dictionary. В JDK 1.2 класс Hashtable также реализует интерфейс Map. Hashtable предназначен для хранения объектов в виде пар ключ/значение. Из самого названия следует, что Hаshtable использует алгоритм хэширования для увеличения скорости доступа к данным. Для того, чтобы выяснить принципы работы данного алгоритма, рассмотрим несколько примеров.

Предположим, имеется массив строк, содержащий названия городов. Для того, чтобы найти элемент массива, содержащий название города, в общем случае требуется просмотреть весь массив, а если необходимо найти все элементы массива, то для поиска каждого, в среднем, потребуется просматривать половину массива. Такой подход может оказаться приемлемым только для небольших массивов.

Как уже отмечалось ранее, для того, чтобы увеличить скорость поиска, используется алгоритм хэширования. Каждый объект в Java унаследован от Object. Как уже отмечалось ранее, hash определено как целое число, которое уникально идентифицирует экземпляр класса Object и, соответственно, все экземпляры классов, унаследованных от Object. Это число возвращает метод hashCode(). Именно оно используется при сохранении ключа в Hashtable следующим образом: разделив длину массива, предназначенного для хранения ключей, на код, получаем некое целое число, которое служит индексом для хранения ключа в массиве array.length % hashCode().

Далее, если необходимо добавить новую пару ключ/значение, вычисляется новый индекс, и если этот индекс совпадает с уже имеющимся, то создается список ключей, на который указывает элемент массива ключей. Таким образом, при обратном извлечении ключа необходимо вычислить индекс массива по тому же алгоритму и получить его. Если ключ в массиве единственный, то используется значение элемента массива, если хранится несколько ключей, то необходимо обойти список и выбрать нужный.

Есть несколько соображений, относящихся к производительности классов, использующих для хранения данных алгоритм хэширования. В частности, размер массива. Если массив окажется слишком мал, то связанные списки будут слишком длинными и скорость поиска станет существенно снижаться, так как просмотр элементов списка будет такой же, как в обычном массиве. Чтобы этого избежать, задается некий коэффициент заполнения. При заполнении элементов массива, в котором хранятся ключи (или списки ключей) на эту величину, происходит увеличение массива и производится повторное реиндексирование. Таким образом, если массив окажется слишком мал, то он будет быстро заполняться и будет производиться операция повторного индексирования, которая отнимает достаточно много ресурсов. С другой стороны, если массив сделать большим, то при необходимости просмотреть последовательно все элементы коллекции, использующей алгоритм хэширования, придется обрабатывать большое количество пустых элементов массива ключей.

Начальный размер массива и коэффициент загрузки коллекции задаются при конструировании. Например:

Hashtable ht = new Hashtable(1000,0.60)

Существует также конструктор без параметров, который использует значения по умолчанию 101 для размера массива (в последней версии значение уменьшено до 11) и 0.75 для коэффициента загрузки.

Использование алгоритма хэширования позволяет гарантировать, что скорость доступа к элементам коллекции такого типа будет увеличиваться не линейно, а логарифмически. Таким образом, при частом поиске каких-либо значений по ключу имеет смысл задействовать коллекции, применяющие алгоритм хэширования.

java.util.HashMap - этот класс расширяет AbstractMap и весьма похож на класс Hashtable. HashMap предназначен для хранения пар объектов ключ/значение. Как для ключей, так и для элементов допускаются значения типа null. Порядок хранения элементов в этой коллекции не совпадает с порядком их добавления. Порядок элементов в коллекции также может меняться во времени. HashMap обеспечивает постоянное время доступа для операций get и put.

Итерация по всем элементам коллекции пропорциональна ее емкости. Поэтому имеет смысл не делать размер коллекций чрезмерно большим, если достаточно часто придется осуществлять итерацию по элементам.

Методы HashMap не являются синхронизированными. Для того, чтобы обеспечить нормальную работу в многопоточном варианте, следует использовать либо внешнюю синхронизацию потоков, либо синхронизированный вариант коллекции.

public class Test { private class TestObject{ String text = ""; public TestObject(String text){ this.text = text; }; public String getText(){ return this.text; } public void setText(String text){ this.text = text; } } public Test() { } public static void main(String[] args) { Test t = new Test(); TestObject to = null; HashMap hm = new HashMap(); hm.put("Key1",t.new TestObject("Value 1")); hm.put("Key2",t.new TestObject("Value 2")); hm.put("Key3",t.new TestObject("Value 3")); to = (TestObject)hm.get("Key1"); System.out.println("Object value for Key1 = " + to.getText() + "\n"); System.out.println("Iteration over entrySet"); Map.Entry entry = null; Iterator it = hm.entrySet().iterator(); // Итератор для перебора всех точек входа в Map while(it.hasNext()){ entry = (Map.Entry)it.next(); System.out.println("For key = " + entry.getKey() + " value = " + ((TestObject)entry.getValue()).getText()); } System.out.println(); System.out.println("Iteration over keySet"); String key = ""; // Итератор для перебора всех ключей в Map it = hm.keySet().iterator(); while(it.hasNext()){ key = (String)it.next(); System.out.println( "For key = " + key + " value = " + ((TestObject)hm.get(key)).getText()); } }}

Пример 14.19.

Результатом будет:

Object value for Key1 = Value 1 Iteration over entrySetFor key = Key3 value = Value 3For key = Key2 value = Value 2For key = Key1 value = Value 1 Iteration over keySetFor key = Key3 value = Value 3For key = Key2 value = Value 2For key = Key1 value = Value 1

Пример 14.20.

java.util.TreeMap - расширяет класс AbstractMap и реализует интерфейс SortedMap. TreeMap содержит ключи в порядке возрастания. Используется либо натуральное сравнение ключей, либо должен быть реализован интерфейс Comparable. Реализация алгоритма поиска обеспечивает логарифмическую зависимость времени выполнения основных операций ( containsKey, get, put и remove ). Запрещено применение null значений для ключей. При использовании дубликатов ключей ссылка на объект, сохраненный с таким же ключом, будет утеряна. Например:

public class Test { public Test() { } public static void main(String[] args) { Test t = new Test(); TreeMap tm = new TreeMap(); tm.put("key","String1"); System.out.println(tm.get("key")); tm.put("key","String2"); System.out.println(tm.get("key")); }}

Результатом будет:

String1String2

Класс Collections

Класс Collections является классом-утилитой и содержит несколько вспомогательных методов для работы с классами, обеспечивающими различные интерфейсы коллекций. Например, для сортировки элементов списков, для поиска элементов в упорядоченных коллекциях и т.д. Но, пожалуй, наиболее важным свойством этого класса является возможность получения синхронизированных вариантов классов-коллекций. Например, для получения синхронизированного варианта Map можно использовать следующий подход:

HashMap hm = new HashMap();:Map syncMap = Collections.synchronizedMap(hm);:

Как уже отмечалось ранее, начиная с JDK 1.2, класс Vector реализует интерфейс List. Рассмотрим пример сортировки элементов, содержащихся в классе Vector.

public class Test { private class TestObject { private String name = ""; public TestObject(String name) { this.name = name; } } private class MyComparator implements Comparator { public int compare(Object l,Object r) { String left = (String)l; String right = (String)r; return -1 * left.compareTo(right); } } public Test() { } public static void main(String[] args) { Test test = new Test(); Vector v = new Vector(); v.add("bbbbb"); v.add("aaaaa"); v.add("ccccc"); System.out.println("Default elements order"); test.dumpList(v); Collections.sort(v); System.out.println("Default sorting order"); test.dumpList(v); System.out.println("Reverse sorting order with providing imlicit comparator"); Collections.sort(v,test.new MyComparator()); test.dumpList(v); } private void dumpList(List l) { Iterator it = l.iterator(); while(it.hasNext()) { System.out.println(it.next()); } }}

Пример 14.21.

Класс Properties

Класс Properties предназначен для хранения набора свойств (параметров). Методы

String getProperty(String key)String getProperty(String key, String defaultValue)

позволяют получить свойство из набора.

С помощью метода setProperty(String key, String value) это свойство можно установить.

Метод load(InputStream inStream) позволяет загрузить набор свойств из входного потока (потоки данных подробно рассматриваются в лекции 15). Как правило, это текстовый файл, в котором хранятся параметры. Параметры - это строки, которые представляют собой пары ключ/значение. Предполагается, что по умолчанию используется кодировка ISO 8859-1. Каждая строка должна оканчиваться символами \r,\n или \r\n. Строки из файла будут считываться до тех пор, пока не будет достигнут его конец. Строки, состоящие из одних пробелов, или начинающиеся со знаков ! или #, игнорируются, т.е. их можно трактовать как комментарии. Если строка оканчивается символом /, то следующая строка считается ее продолжением. Первый символ с начала строки, отличный от пробела, считается началом ключа. Первый встретившийся пробел, двоеточие или знак равенства считается окончанием ключа. Все символы окончания ключа при необходимости могут быть включены в название ключа, но при этом перед ними должен стоять символ \. После того, как встретился символ окончания ключа, все аналогичные символы будут проигнорированы до начала значения. Оставшаяся часть строки интерпретируется как значение. В строке, состоящей только из символов \t, \n, \r, \\, \", \', \ и \uxxxx, они все распознаются и интерпретируются как одиночные символы. Если встретится сочетание \ и символа конца строки, то следующая строка будет считаться продолжением текущей, также будут проигнорированы все пробелы до начала строки-продолжения.

Метод save(OutputStream inStream,String header) сохраняет набор свойств в выходной поток в виде, пригодном для вторичной загрузки с помощью метода load. Символы, считающиеся служебными, кодируются так, чтобы их можно было считать при вторичной загрузке. Символы в национальной кодировке будут приведены к виду \uxxxx. При сохранении используется кодировка ISO 8859-1. Если указан header, то он будет помещен в начало потока в виде комментария (т.е. с символом # в начале), далее будет следовать комментарий, в котором будет указано время и дата сохранения свойств в потоке.

В классе Properties определен еще метод list(PrintWriter out), который практически идентичен save. Отличается лишь заголовок, который изменить нельзя. Кроме того, строки усекаются по ширине. Поэтому данный метод для сохранения Properties не годится.

public class Test { public Test() { } public static void main(String[] args) { Test test = new Test(); Properties props = new Properties(); StringWriter sw = new StringWriter(); sw.write("Key1 = Value1 \n"); sw.write(" Key2 : Value2 \r\n"); sw.write(" Key3 Value3 \n "); InputStream is = new ByteArrayInputStream(sw.toString().getBytes()); try { props.load(is); } catch (IOException ex) { ex.printStackTrace(); } props.list(System.out); props.setProperty("Key1","Modified Value1"); props.setProperty("Key4","Added Value4"); props.list(System.out); }}

Пример 14.22.

Результатом будет:

-- listing properties --Key3=Value3 Key2=Value2 Key1=Value1 -- listing properties --Key4=Added Value4Key3=Value3 Key2=Value2 Key1=Modified Value1

Пример 14.23.








Дата добавления: 2016-03-22; просмотров: 695;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.01 сек.