Summary overview based on a collection of Java reviews

Author：Eve Cole Update Time：2024-11-18 12:48:01

Collections in Java are mainly concentrated in two parts, one is in the java.util package, and the other is in java.util.concurrent. The latter is based on the former and defines some collections that implement synchronization functions.

This article mainly focuses on various collection objects under java.util. Collection objects in Java can be roughly divided into three categories: List, Set and Map. The corresponding UML diagram is as follows (including most collection objects under java.util):

Collection overview

Both List and Set in Java collections come from Collection. It is a good entry point for learning collections. It includes operations that are usually required in collections:

Add elements: add/addAll
Clear the collection: clear
Remove elements: remove/removeAll
Determine whether the collection contains an element: contains/containsAll
Determine whether the collection is empty: isEmpty
Calculate the number of elements in a collection: size
Convert a collection to an array: toArray
Get iterator: iterator

Let's look at a simple example. The following code will return a collection whose elements are randomly generated integers:

Copy the code code as follows:

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 collections, traversal is a frequently used operation. We can traverse collections in two ways:

1) Use iterators to traverse the collection. As mentioned when describing the Collection interface above, all collections will have an iterator that we can use to traverse the collection.

Copy the code code as follows:

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.

Copy the code code as follows:

private static void accessCollectionByFor(Collection<Integer> collection)
{
System.out.println("The value in the list:");
for(Integer value : collection)
{
System.out.println(value);
}
}

List

List in Java is an effective extension of array. It is a structure that can hold elements of any type if generics are not used. If generics are used, it can only hold elements of the type specified by the generics. Compared with arrays, the capacity of List can be dynamically expanded.

The elements in the List can be repeated, and the elements inside are "ordered". The "ordered" here does not mean sorting, but means that we can specify the position of an element in the collection.

Commonly used collection objects in List include: ArrayList, Vector and LinkedList, the former two are stored based on arrays, and the latter are stored based on linked lists. Among them, Vector is thread-safe, and the other two are not thread-safe.

List can contain null, even if generics are used.

ArrayList may be the most commonly used collection object. In the above example code, we also use it to instantiate a Collection object, so we won’t go into details here.
Vector

An example of Vector is as follows. First we look at how to generate and output Vector:

Copy the code code as follows:

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);
}

Its elements include both repeated elements and null. The output results are as follows:

Copy the code code as follows:

size of vector is 6
[100, 100, 100, 100, 100, null]

The following example demonstrates some common methods in Vector:

Copy the code code as follows:

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:

Copy the code code 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 linked lists to store data. Its sample code is as follows:

Copy the code code as follows:

LinkedList example
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);
}

Here are the commonly used methods of LinkedList. As you can see from the method names, LinkedList can also be used to implement stacks and queues.

The output is as follows:

Copy the code code as follows:

size of linked list is 11
[17, 21, 5, 84, 19, 57, 68, 26, 27, 47, null]

null

size of linked list is 8
[100, 84, 19, 57, 68, 26, 27, 47]

Set

Set is similar to List, both are used to store a single element, and the number of individual elements is uncertain. But Set cannot contain duplicate elements. If two identical elements are inserted into Set, the latter element will not be inserted.

Set 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. Among them, HashSet and LinkedHashSet can contain null.
HashSet

HashSet is a collection backed by a Hash table, which is not thread-safe.

Let's look at the following example, which is basically the same as the first example with Vector:

Copy the code code as follows:

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, HashSet contains both repeated elements and null. Unlike Vector, the output here is as follows:

Copy the code code as follows:

size of set is 2
[null, 100]

We can take an in-depth look at how HashSet determines whether two elements are duplicates. The equals method is also defined in Object. For the elements in the HashSet, it is judged whether the elements are equal based on the equals method. In order to prove this, we can define an "abnormal" type:

Copy the code code as follows:

Define MyInteger object

classMyInteger
{
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;
}
}

It can be seen that for MyInteger, for any two instances, we consider it to be unequal.

The following is the corresponding test method:

Copy the code code as follows:

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:

Copy the code code as follows:

size of set is 3
[100, 100, 100]

As you can see, there are now "duplicate" elements in the HashSet, but for MyInteger, they are not "the same".
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:

Copy the code code as follows:

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:

Copy the code code 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. By default, for Integer, SortedList is stored in ascending order. We can also customize the Compare method, such as storing in descending order.

Next, we first redefine Integer:

Copy the code code as follows:

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:

Copy the code code as follows:

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 result of running the code is as expected, as shown below:

Copy the code code as follows:

Set1 as below:
[13, 41, 42, 45, 61]
Set2 as below:
[61, 45, 42, 41, 13]

Map

Map stores "key-value pairs". Similar to Set, there are two types of Maps in Java: sorted and unsorted. Unsorted include HashMap, Hashtable and LinkedHashMap, and sorted include TreeMap.
Unsorted Map

Both HashMap and Hashtable are stored in the form of Hash tables. HashMap is not thread-safe, but Hashtable is thread-safe. We can regard HashMap as a "simplified" version of Hashtable.

HashMap can store null, whether for Key or Value. Hashtable cannot store null.

Regardless of HashMap or Hashtable, if we observe its constructor, we will find that it can have two parameters: initialCapacity and loadFactor. By default, initialCapacity is equal to 16 and loadFactor is equal to 0.75. This is related to the number of elements that can be stored in the Hash table. When the number of elements exceeds initialCapacity*loadFactor, the rehash method will be 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 first look at an example of HashMap:

Copy the code code as follows:

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 will output the element information in the HashMap, as shown below.

Copy the code code as follows:

{1=a, 2=b, 3=c}
[1=a, 2=b, 3=c]
[1, 2, 3]
[a, b, c]

The following example demonstrates null:

Copy the code code as follows:

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 execution results are as follows:

Copy the code code 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 above two examples (the code will not be expanded):

Copy the code code as follows:

Hashtable example
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 execution results are as follows:

Copy the code code 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)

It can be clearly seen that when we try to insert null into the hashtable, a null pointer exception is reported.
SortMap

Sorting Map mainly refers to TreeMap, which has a time complexity of O(log(n)) when adding, deleting, and searching elements. It is not thread safe.

Its characteristics are very similar to TreeSet, so I won’t go into details here.