Home >Java >javaTutorial >Java collection framework architecture details
Recently I saw a very good description of the collection framework in a J2EE book. I filtered it and posted it to share with everyone. The collection framework provides interfaces and classes for managing object collections. It includes interfaces, classes, algorithms, The following is a description of its various components.
Collection interface
Collection is the most basic collection interface. A Collection represents a group of Objects, that is, the elements of the Collection. Some Collections allow identical elements and others do not. Some sort and others don't. The Java SDK does not provide classes that directly inherit from Collection. The classes provided by the Java SDK are all "sub-interfaces" that inherit from Collection, such as List and Set.
All classes that implement the Collection interface must provide two standard constructors: the parameterless constructor is used to create an empty Collection, and the constructor with a Collection parameter is used to create a new Collection. This new Collection has the same elements as the passed Collection. The latter constructor allows the user to copy a Collection.
How to traverse each element in Collection? Regardless of the actual type of Collection, it supports an iterator() method, which returns an iterator that can be used to access each element in the Collection one by one. Typical usage is as follows:
Iterator it = collection.iterator(); // 获得一个迭代子 while(it.hasNext()) { Object obj = it.next(); // 得到下一个元素 }
The two interfaces derived from the Collection interface are List and Set.
List interface
List is an ordered Collection. Using this interface can accurately control the insertion position of each element. Users can access elements in the List using the index (the position of the element in the List, similar to an array subscript), which is similar to Java's array.
Unlike the Set mentioned below, List allows the same elements.
In addition to the iterator() method necessary for the Collection interface, List also provides a listIterator() method, which returns a ListIterator interface. Compared with the standard Iterator interface, ListIterator has some more methods such as add(). Allows adding, deleting, setting elements, and traversing forward or backward.
Commonly used classes that implement the List interface are LinkedList, ArrayList, Vector and Stack.
LinkedList class
LinkedList implements the List interface and allows null elements. In addition, LinkedList provides additional get, remove, and insert methods at the head or tail of LinkedList. These operations allow LinkedList to be used as a stack, queue, or deque.
Note that LinkedList has no synchronization method. If multiple threads access a List at the same time, they must implement access synchronization themselves. One solution is to construct a synchronized List when creating the List:
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList class
ArrayList implements a variable-sized array . It allows all elements, including null. ArrayList is not synchronized.
The running time of the size, isEmpty, get, and set methods is constant. However, the cost of the add method is an amortized constant, and adding n elements requires O(n) time. Other methods have linear running time.
Each ArrayList instance has a capacity (Capacity), which is the size of the array used to store elements. This capacity increases automatically as new elements are added, but the growth algorithm is not defined. When you need to insert a large number of elements, you can call the ensureCapacity method to increase the capacity of the ArrayList before inserting to improve insertion efficiency.
Like LinkedList, ArrayList is also unsynchronized.
Vector class
Vector is very similar to ArrayList, but Vector is synchronized. Although the Iterator created by Vector has the same interface as the Iterator created by ArrayList, because Vector is synchronized, when an Iterator is created and is being used, another thread changes the state of the Vector (for example, adding or removing some element), ConcurrentModificationException will be thrown when calling the Iterator method, so the exception must be caught.
Stack class
Stack inherits from Vector and implements a last-in-first-out stack. Stack provides 5 additional methods that allow Vector to be used as a stack. The basic push and pop methods, as well as the peek method, get the element on the top of the stack, the empty method tests whether the stack is empty, and the search method detects the position of an element in the stack. Stack is an empty stack after it is created.
Set interface
Set is a Collection that does not contain repeated elements, that is, any two elements e1 and e2 have e1.equals(e2)=false, and Set has at most one null element.
Obviously, the Set constructor has a constraint that the passed-in Collection parameter cannot contain duplicate elements.
Please note: Mutable Objects must be handled with care. If a mutable element in a Set changes its state causing Object.equals(Object)=true, it will cause some problems.
Map interface
Please note that Map does not inherit the Collection interface. Map provides key to value mapping. A Map cannot contain the same key, and each key can only map one value. The Map interface provides three kinds of set views. The content of the Map can be regarded as a set of key sets, a set of value sets, or a set of key-value mappings.
Hashtable class
Hashtable inherits the Map interface and implements a hash table of key-value mapping. Any non-null object can be used as key or value.
Use put(key, value) to add data and get(key) to remove data. The time cost of these two basic operations is constant.
Hashtable adjusts performance through two parameters: initial capacity and load factor. Usually the default load factor 0.75 achieves a better balance between time and space. Increasing the load factor can save space but the corresponding search time will increase, which will affect operations like get and put.
A simple example of using Hashtable is as follows. Put 1, 2, and 3 into the Hashtable, and their keys are "one", "two", and "three" respectively:
Hashtable numbers = new Hashtable(); numbers.put(“one”, new Integer(1)); numbers.put(“two”, new Integer(2)); numbers.put(“three”, new Integer(3));
要取出一个数,比如2,用相应的key:
Integer n = (Integer)numbers.get(“two”);
System.out.println(“two = ” + n);
由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置,因此任何作为key的对象都必须实现hashCode和equals方法。hashCode和equals方法继承自根类Object,如果你用自定义的类当作key的话,要相当小心,按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同,如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。
如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),要避免这种问题,只需要牢记一条:要同时复写equals方法和hashCode方法,而不要只写其中一个。
Hashtable是同步的。
HashMap类
HashMap和Hashtable类似,不同之处在于HashMap是非同步的,并且允许null,即null value和null key。,但是将HashMap视为Collection时(values()方法可返回Collection),其迭代子操作时间开销和HashMap的容量成比例。因此,如果迭代操作的性能相当重要的话,不要将HashMap的初始化容量设得过高,或者load factor过低。
WeakHashMap类
WeakHashMap是一种改进的HashMap,它对key实行“弱引用”,如果一个key不再被外部所引用,那么该key可以被GC回收。
总结
如果涉及到堆栈,队列等操作,应该考虑用List,对于需要快速插入,删除元素,应该使用LinkedList,如果需要快速随机访问元素,应该使用ArrayList。
如果程序在单线程环境中,或者访问仅仅在一个线程中进行,考虑非同步的类,其效率较高,如果多个线程可能同时操作一个类,应该使用同步的类。
要特别注意对哈希表的操作,作为key的对象要正确复写equals和hashCode方法。
尽量返回接口而非实际的类型,如返回List而非ArrayList,这样如果以后需要将ArrayList换成LinkedList时,客户端代码不用改变。这就是针对抽象编程。
更多java集合框架的体系结构详细说明相关文章请关注PHP中文网!