Summary overview of a collection of Java retrospectives
- 2020-04-01 01:53:58
- OfStack
Collections in Java are mainly concentrated in two parts, one is in the java.utill package and the other is in java.util.concurrent, which defines some collections that implement synchronization on the basis of the former.
This article focuses on the various collection objects under java.util. Collection objects in Java can be roughly divided into three classes: List, Set, and Map. The corresponding UML diagram is as follows (including most of the collection objects under java.util) :
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201305/201305080925201111.png ">
Description of the Collection
The List and Set in the Java Collection come out of the Collection. It is a good entry point to learn the Collection. It contains the operations that are usually required in the Collection:
Add element: add/addAll
Clear the collection: clear
Remove /removeAll
Determines whether the collection contains an element: contains/containsAll
Determines if the collection isEmpty: isEmpty
Calculate the number of elements in the set: size
Converts a collection to an array: toArray
Gets iterator: iterator
Let's look at a simple example where the following code returns a collection whose elements are randomly generated integers:
private static Collection initCollection()
{
Collection<Integer> collection = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0 ; i < 5; i++)
{
collection.add(new Integer(r.nextInt(100)));
}
return collection;
}
In the process of operating on the collection, traversal is a frequently used operation. We can traverse the collection in two ways:
1)
Iterator is used to traverse the collection. As described above in describing the Collection interface, all collections have an iterator that we can use to traverse the Collection.
private static void accessCollectionByIterator(Collection<Integer> collection)
{
Iterator<Integer> iterator = collection.iterator();
System.out.println("The value in the list:");
while(iterator.hasNext())
{
System.out.println(iterator.next());
}
}
2) Use foreach to traverse the collection.
private static void accessCollectionByFor(Collection<Integer> collection)
{
System.out.println("The value in the list:");
for(Integer value : collection)
{
System.out.println(value);
}
}
The List
A List in Java is an effective extension of an array. It is a structure that can hold elements of any type if you do not use generics, and only elements of the type specified by the generics if you use generics. In contrast to arrays, the capacity of a List can be dynamically expanded.
The elements in a List are repeatable, and the elements inside are "ordered". The "ordered" here does not mean sort, but we can specify the position of an element in the collection.
Common collection objects in a List include ArrayList, Vector, and LinkedList, where the first two are stored on an array and the second on a LinkedList. The Vector is thread-safe and the other two are not.
Null can be included in a List, even if generics are used.
The ArrayList is probably the most commonly used Collection object, and in the sample code above, we also used it to instantiate a Collection object, which we won't repeat here.
The Vector
The example of Vector is as follows. First, let's see how to generate and output a Vector:
private static void vectorTest1()
{
List<Integer> list = new Vector<Integer>();
for (int i = 0 ; i < 5; i++)
{
list.add(new Integer(100));
}
list.add(null);
System.out.println("size of vector is " + list.size());
System.out.println(list);
}
In its elements, it includes both duplicate elements and null. The output result is as follows:
size of vector is 6
[100, 100, 100, 100, 100, null]
The following example demonstrates some of the common methods in Vector:
private static void vectorTest2()
{
Vector<Integer> list = new Vector<Integer>();
Random r = new Random();
for (int i = 0 ; i < 10; i++)
{
list.add(new Integer(r.nextInt(100)));
}
System.out.println("size of vector is " + list.size());
System.out.println(list);
System.out.println(list.firstElement());
System.out.println(list.lastElement());
System.out.println(list.subList(3, 8));
List<Integer> temp = new ArrayList<Integer>();
for(int i = 4; i < 7; i++)
{
temp.add(list.get(i));
}
list.retainAll(temp);
System.out.println("size of vector is " + list.size());
System.out.println(list);
}
Its output is as follows:
size of vector is 10
[39, 41, 20, 9, 29, 32, 54, 12, 94, 82]
[9, 29, 32, 54, 12]
size of vector is 3
[29, 32, 54]
LinkedList
LinkedList USES a LinkedList to store data, and here's the sample code:
LinkedList The sample
private static void linkedListTest1()
{
LinkedList<Integer> list = new LinkedList<Integer>();
Random r = new Random();
for (int i = 0 ; i < 10; i++)
{
list.add(new Integer(r.nextInt(100)));
}
list.add(null);
System.out.println("size of linked list is " + list.size());
System.out.println(list);
System.out.println(list.element());
System.out.println(list.getFirst());
System.out.println(list.getLast());
System.out.println(list.peek());
System.out.println(list.peekFirst());
System.out.println(list.peekLast());
System.out.println(list.poll());
System.out.println(list.pollFirst());
System.out.println(list.pollLast());
System.out.println(list.pop());
list.push(new Integer(100));
System.out.println("size of linked list is " + list.size());
System.out.println(list);
}
The various methods commonly used on LinkedList are listed here, and as you can see from the method names, LinkedList can also be used to implement stacks and queues.
The output results are as follows:
size of linked list is 11
[17, 21, 5, 84, 19, 57, 68, 26, 27, 47, null]
null
null
null
size of linked list is 8
[100, 84, 19, 57, 68, 26, 27, 47]
The Set
A Set is similar to a List in that it is used to store a single element with an uncertain number of individual elements. But a Set cannot contain duplicate elements, and if two identical elements are inserted into a Set, the latter element will not be inserted.
Sets can be roughly divided into two categories: unsorted Set and sorted Set, unsorted Set includes HashSet and LinkedHashSet, and sorted Set mainly refers to TreeSet. Where a HashSet and a LinkedHashSet can contain null.
HashSet
A HashSet is a collection supported by a Hash table that is not thread-safe.
Let's look at the following example, which is basically the same as the first example of Vector:
private static void hashSetTest1()
{
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < 3; i++)
{
set.add(new Integer(100));
}
set.add(null);
System.out.println("size of set is " + set.size());
System.out.println(set);
}
Here, the HashSet contains both duplicate elements and null, which is different from Vector. The output result is as follows:
size of set is 2
[null, 100]
We can take a closer look at how a HashSet determines whether two elements are repeating. The equals method is also defined in Object. For the elements in HashSet, it determines whether the elements are equal according to the equals method. To prove this, we can define an "abnormal" type:
define MyInteger object
class MyInteger
{
private Integer value;
public MyInteger(Integer value)
{
this.value = value;
}
public String toString()
{
return String.valueOf(value);
}
public int hashCode()
{
return 1;
}
public boolean equals(Object obj)
{
return true;
}
}
As you can see, for MyInteger, for any two instances, we don't think it's equal.
The following is the corresponding test method:
private static void hashSetTest2()
{
Set<MyInteger> set = new HashSet<MyInteger>();
for (int i = 0; i < 3; i++)
{
set.add(new MyInteger(100));
}
System.out.println("size of set is " + set.size());
System.out.println(set);
}
Its output is as follows:
size of set is 3
[100, 100, 100]
As you can see, there are now "duplicate" elements in the HashSet, but they are not "identical" for MyInteger.
TreeSet
TreeSet is a Set that supports sorting, and its parent interface is SortedSet.
Let's first take a look at the basic operations of TreeSet:
private static void treeSetTest1()
{
TreeSet<Integer> set = new TreeSet<Integer>();
Random r = new Random();
for (int i = 0 ; i < 5; i++)
{
set.add(new Integer(r.nextInt(100)));
}
System.out.println(set);
System.out.println(set.first());
System.out.println(set.last());
System.out.println(set.descendingSet());
System.out.println(set.headSet(new Integer(50)));
System.out.println(set.tailSet(new Integer(50)));
System.out.println(set.subSet(30, 60));
System.out.println(set.floor(50));
System.out.println(set.ceiling(50));
}
Its output is as follows:
[8, 42, 48, 49, 53]
[53, 49, 48, 42, 8]
[8, 42, 48, 49]
[53]
[42, 48, 49, 53]
The elements in TreeSet generally implement the Comparable interface, and SortedList is stored in ascending order for an Integer by default, or we can customize Compare, for example, in descending order.
Next, we first redefine Integer:
define MyInteger2 object
class MyInteger2 implements Comparable
{
public int value;
public MyInteger2(int value)
{
this.value = value;
}
public int compareTo(Object arg0)
{
MyInteger2 temp = (MyInteger2)arg0;
if (temp == null) return -1;
if (temp.value > this.value)
{
return 1;
}
else if (temp.value < this.value)
{
return -1;
}
return 0;
}
public boolean equals(Object obj)
{
return compareTo(obj) == 0;
}
public String toString()
{
return String.valueOf(value);
}
}
Here is the test code:
private static void treeSetTest2()
{
TreeSet<Integer> set1 = new TreeSet<Integer>();
TreeSet<MyInteger2> set2 = new TreeSet<MyInteger2>();
Random r = new Random();
for (int i = 0 ; i < 5; i++)
{
int value = r.nextInt(100);
set1.add(new Integer(value));
set2.add(new MyInteger2(value));
}
System.out.println("Set1 as below:");
System.out.println(set1);
System.out.println("Set2 as below:");
System.out.println(set2);
}
The code runs as expected, as shown below:
Set1 as below:
[13, 41, 42, 45, 61]
Set2 as below:
[61, 45, 42, 41, 13]
The Map
Maps store "key-value pairs," and like sets, there are two types of maps in Java: sorted and unsorted, unsorted including HashMap, Hashtable, and LinkedHashMap, and sorted including TreeMap.
Not sorted Map
Both HashMap and Hashtable are stored in a Hashtable. HashMap is not thread-safe, and Hashtable is thread-safe. We can regard HashMap as a "simplified" version of Hashtable.
A HashMap can store null, either for Key or Value. A Hashtable cannot store null.
Whether a HashMap or a Hashtable, when we look at its constructor, we see that it can take two arguments: initialCapacity and loadFactor. By default, initialCapacity is 16 and loadFactor is 0.75. This is related to the number of elements that can be stored in the Hash table. When the number of elements exceeds the initialCapacity*loadFactor, the rehash method is triggered to expand the Hash table. If we need to insert too many elements into it, we need to adjust these two parameters appropriately.
Let's start with an example of HashMap:
private static void hashMapTest1()
{
Map<Integer,String> map = new HashMap<Integer, String>();
map.put(new Integer(1), "a");
map.put(new Integer(2), "b");
map.put(new Integer(3), "c");
System.out.println(map);
System.out.println(map.entrySet());
System.out.println(map.keySet());
System.out.println(map.values());
}
This outputs the element information in the HashMap, as shown below.
{1=a, 2=b, 3=c}
[1=a, 2=b, 3=c]
[1, 2, 3]
[a, b, c]
The following example demonstrates null:
private static void hashMapTest2()
{
Map<Integer,String> map = new HashMap<Integer, String>();
map.put(null, null);
map.put(null, null);
map.put(new Integer(4), null);
map.put(new Integer(5), null);
System.out.println(map);
System.out.println(map.entrySet());
System.out.println(map.keySet());
System.out.println(map.values());
}
The implementation results are as follows:
{null=null, 4=null, 5=null}
[null=null, 4=null, 5=null]
[null, 4, 5]
[null, null, null]
Next we demonstrate Hashtable, which is basically the same as the two examples above (the code is no longer expanded) :
Hashtable The sample
private static void hashTableTest1()
{
Map<Integer,String> table = new Hashtable<Integer, String>();
table.put(new Integer(1), "a");
table.put(new Integer(2), "b");
table.put(new Integer(3), "c");
System.out.println(table);
System.out.println(table.entrySet());
System.out.println(table.keySet());
System.out.println(table.values());
}
private static void hashTableTest2()
{
Map<Integer,String> table = new Hashtable<Integer, String>();
table.put(null, null);
table.put(null, null);
table.put(new Integer(4), null);
table.put(new Integer(5), null);
System.out.println(table);
System.out.println(table.entrySet());
System.out.println(table.keySet());
System.out.println(table.values());
}
The implementation results are as follows:
{3=c, 2=b, 1=a}
[3=c, 2=b, 1=a]
[3, 2, 1]
[c, b, a]
Exception in thread "main" java.lang.NullPointerException
at java.util.Hashtable.put(Unknown Source)
at sample.collections.MapSample.hashTableTest2(MapSample.java:61)
at sample.collections.MapSample.main(MapSample.java:11)
You can clearly see that when we tried to insert null into the hashtable, the null pointer exception was reported.
Sort the Map
Sorting Map mainly refers to TreeMap, whose time complexity is order log (n) when adding, deleting and checking elements. It's not thread-safe.
Its features are very similar to those of TreeSet, which I won't go into here.