Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "analyzing Java Set collection". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

01. Abstract

"the Set interface is rarely used in actual development, but if you go out for an interview, it may still be an unavoidable topic.

To get back to the point, we won't say much nonsense. I believe friends who have used the Set collection class all know that the main characteristics of the Set collection are: non-repetition of elements, storage disorder.

What do you mean? You can understand that throwing things into a bottle is not marked how many things are put in, but one thing is that there will be no duplicates in the bottle.

If you think about it, you will find that these features of the Set collection lie between the List collection and the Map collection. Why do you say that? In the previous collection article, we learned that the List collection is characterized by orderly access, which is essentially an ordered array, with each element stored sequentially; the Map collection is mainly used to store key-value pairs, although the underlying layer is also stored in an array, but the subscript of the elements in the array is calculated by the hash algorithm, and the array subscript is unordered.

The Set collection, in terms of element storage, pays attention to the unique characteristics. If an element already exists in the collection, it will not store duplicate elements. At the same time, the collection stores elements, unlike the Map collection, which stores key-value pairs.

For a specific analysis, let's go slowly and open the Set collection. The main implementation classes are HashSet, LinkedHashSet, TreeSet, EnumSet (RegularEnumSet, JumboEnumSet), and so on. Summarize the Set API implementation classes, as shown below:

From the inheritance relationship in the figure, you can see that the main implementation classes of Set interface are AbstractSet, HashSet, LinkedHashSet, TreeSet, EnumSet (RegularEnumSet, JumboEnumSet), where AbstractSet and EnumSet belong to abstract classes, EnumSet is added in jdk1.5, except that EnumSet collection elements must be enumerated.

HashSet is a collection of unordered inputs and outputs. The elements in the collection are based on the key implementation of HashMap, and the elements cannot be repeated.

LinkedHashSet is a collection of ordered inputs and outputs. The elements in the set are based on the key implementation of LinkedHashMap, and the elements can not be repeated.

TreeSet is a sorted collection. The elements in the collection are based on the key implementation of TreeMap, and the same elements cannot be repeated.

EnumSet is a dedicated Set collection used with enumerated types, in which RegularEnumSet and JumboEnumSet cannot be instantiated separately and can only be generated by EnumSet. The same elements cannot be repeated.

Let's analyze each of the main implementation classes one by one!

02. HashSet

HashSet is a collection of unordered inputs and outputs. The underlying implementation is based on HashMap. HashSet uses key elements in HashMap to store elements. We can see this from the source code. Read the source code as follows:

Public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable {/ / HashMap variable private transient HashMap map; / * * HashSet initialization * / public HashSet () {/ / instantiate a HashMap map = new HashMap () by default;}}

Add method

Open the add () method of HashSet. The source code is as follows:

Public boolean add (E e) {/ / add the element return map.put (e, PRESENT) = = null;} to HashMap

The variable PRESENT is a non-empty object. The source code is as follows:

Private static final Object PRESENT = new Object ()

It can be analyzed that when add () is performed, it is equivalent to

HashMap map = new HashMap (); map.put (e, new Object ()); / / e represents the element to be added

In the previous collection article, we learned that when HashMap adds elements, it uses the equals () and hashCode () methods to determine whether the incoming key is the same. If it is the same, then HashMap thinks it is adding the same element, and vice versa.

From the source code analysis, we can see that HashSet uses this feature of HashMap to achieve the storage element subscript disorder, elements will not repeat the characteristics.

Remove method

The deletion method of HashSet, similarly, is also based on the underlying implementation of HashMap. The source code is as follows:

Public boolean remove (Object o) {/ / calls the remove method of HashMap, removing the element return map.remove (o) = = PRESENT;}

Query method

Instead of providing get methods like List and Map, HashSet uses iterators or for loops to traverse elements as follows:

Public static void main (String [] args) {Set hashSet = new HashSet (); System.out.println ("HashSet initial capacity size:" + hashSet.size ()); hashSet.add ("1"); hashSet.add ("2"); hashSet.add ("3"); hashSet.add ("3"); hashSet.add ("2"); hashSet.add (null) / / the same element automatically overrides System.out.println ("HashSet capacity size:" + hashSet.size ()); / / iterator traverses Iterator iterator = hashSet.iterator (); while (iterator.hasNext ()) {String str = iterator.next (); System.out.print (str + ",");} System.out.println ("\ n =") / / enhanced for loop for (String str: hashSet) {System.out.print (str + ",");}}

Output result:

HashSet initial capacity size: 0 HashSet capacity size: 4 null,1,2,3, = null,1,2,3

It is important to note that HashSet allows elements to be added as null.

03. LinkedHashSet

LinkedHashSet is an ordered set of inputs and outputs, inherited from HashSet, but the underlying implementation is based on LinkedHashMap.

If you don't already know the implementation process of LinkedHashMap, you can refer to the article on the implementation process of LinkedHashMap in the collection series.

Read the source code of LinkedHashSet. The class definition is as follows:

Public class LinkedHashSet extends HashSet implements Set, Cloneable, java.io.Serializable {public LinkedHashSet () {/ / call HashSet's method super (16, .75f, true);}}

Query the source code and the method called by super. The source code is as follows:

HashSet (int initialCapacity, float loadFactor, boolean dummy) {/ / initialize a LinkedHashMap map = new LinkedHashMap (initialCapacity, loadFactor);}

Add method

Instead of overriding the add method, LinkedHashSet directly calls the add () method of HashSet, because the implementation class of map is LinkedHashMap, so here you add an element to LinkedHashMap, which is equivalent to add ().

HashMap map = new LinkedHashMap (); map.put (e, new Object ()); / / e represents the element to be added

Remove method

LinkedHashSet does not override the remove method, but directly calls the delete method of HashSet. Because LinkedHashMap does not override the remove method, the remove method of HashMap is also called. The source code is as follows:

Public boolean remove (Object o) {/ / calls the remove method of HashMap, removing the element return map.remove (o) = = PRESENT;}

Query method

Similarly, LinkedHashSet does not provide a get method, but uses an iterator or for loop to traverse the element as follows:

Public static void main (String [] args) {Set linkedHashSet = new LinkedHashSet (); System.out.println ("linkedHashSet initial capacity size:" + linkedHashSet.size ()); linkedHashSet.add ("1"); linkedHashSet.add ("2"); linkedHashSet.add ("3"); linkedHashSet.add ("3"); linkedHashSet.add ("2"); linkedHashSet.add (null); linkedHashSet.add (null) System.out.println ("linkedHashSet capacity size:" + linkedHashSet.size ()); / / iterator traverses Iterator iterator = linkedHashSet.iterator (); while (iterator.hasNext ()) {String str = iterator.next (); System.out.print (str + ",");} System.out.println ("\ n =") / / enhanced for loop for (String str: linkedHashSet) {System.out.print (str + ",");}}

Output result:

Initial capacity size of linkedHashSet: 0 linkedHashSet capacity size: 4 1, 2, 5, 3, zero, = 1, 1, 2, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 5, 4, 4, 4, 4, 4, 4, 1, 5, 5, 4, 4, 4, 4

It can be seen that compared with HashSet, LinkedHashSet has orderly input and output of LinkedHashSet.

04. TreeSet

TreeSet is a sorted set, which implements the interfaces of NavigableSet, SortedSet and Set, while the bottom layer is implemented based on TreeMap. TreeSet uses the key element in TreeMap to store elements, which we can also see from the source code. Read the source code. The class definition is as follows:

Public class TreeSet extends AbstractSet implements NavigableSet, Cloneable, java.io.Serializable {/ / TreeSet use the NavigableMap interface as variables private transient NavigableMap m; / * * object initialization * / public TreeSet () {/ / instantiate a TreeMap object this (new TreeMap ()) by default;} / / the method called by object initialization TreeSet (NavigableMap m) {this.m = m }}

When the new TreeSet () object is instantiated, the meaning can be simplified as follows:

NavigableMap m = new TreeMap ()

Because TreeMap implements the NavigableMap interface, there is no problem.

Public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable {. }

Add method

Open the add () method of TreeSet. The source code is as follows:

Public boolean add (E e) {/ / add the element return m.put (e, PRESENT) = = null;} to TreeMap

The variable PRESENT is also a non-empty object. The source code is as follows:

Private static final Object PRESENT = new Object ()

It can be analyzed that when add () is performed, it is equivalent to

TreeMap map = new TreeMap (); map.put (e, new Object ()); / / e represents the element to be added

The main function of the TreeMap class is that the added collection elements are sorted according to the rules of one. By default, they are sorted in the natural order. Of course, you can also customize the sorting. For example, the test method is as follows:

Public static void main (String [] args) {Map initMap = new TreeMap (); initMap.put ("4", "d"); initMap.put ("3", "c"); initMap.put ("1", "a"); initMap.put ("2", "b"); / / default natural sort, key is ascending System.out.println ("default sort result:" + initMap.toString ()) / Custom sorting. Pass Comparator internal object Map comparatorMap = new TreeMap (new Comparator () {@ Override public int compare (String o1, String o2)) {/ / flashback to sort return o2.compareTo (o1) from big to small according to key size in TreeMap initialization phase; comparatorMap.put ("4", "d") ComparatorMap.put ("3", "c"); comparatorMap.put ("1", "a"); comparatorMap.put ("2", "b"); System.out.println ("Custom sort result:" + comparatorMap.toString ());}

Output result:

Default sort result: {1cm a, 2m b, 3 °c, 4 °d} Custom sort result: {4 °d, 3 °c, 2 °b, 1 °a}

I believe that friends who have used TreeMap must know that TreeMap will automatically sort the key according to certain rules. TreeSet uses the feature of TreeMap to achieve the added set of elements, and the result is sorted when it is output.

If you haven't seen the implementation of the source code TreeMap, you can refer to the introduction to the implementation of TreeMap in the collection series, or read the jdk source code.

Remove method

The deletion method of TreeSet, similarly, is also based on the underlying implementation of TreeMap. The source code is as follows:

Public boolean remove (Object o) {/ / calls the remove method of TreeMap, removing the element return m.remove (o) = = PRESENT;}

Query method

Instead of overriding the get method, TreeSet uses an iterator or for loop to traverse the element as follows:

Public static void main (String [] args) {Set treeSet = new TreeSet (); System.out.println ("treeSet initial capacity size:" + treeSet.size ()); treeSet.add ("1"); treeSet.add ("4"); treeSet.add ("3"); treeSet.add ("8"); treeSet.add ("5"); System.out.println ("treeSet capacity size:" + treeSet.size ()) / / iterator traverses Iterator iterator = treeSet.iterator (); while (iterator.hasNext ()) {String str = iterator.next (); System.out.print (str + ",");} System.out.println ("\ n ="); / / enhanced for loop for (String str: treeSet) {System.out.print (str + ",");}}

Output result:

Initial capacity size of treeSet: 0 treeSet capacity size: 5 1, 3, 4, 5, 8, = 1, 3, 4, 5, 8

Custom sorting

There are two ways to use custom sorting. The first is to implement the Comparable interface in the element classes that need to be added, and override the compareTo method to compare elements and achieve custom sorting.

Method one

/ * create entity class Person to implement Comparable interface * / public class Person implements Comparable {private int age; private String name; public Person (String name, int age) {this.name = name; this.age = age;} @ Override public int compareTo (Person o) {/ / override compareTo method, custom sorting algorithm return this.age-o.age } @ Override public String toString () {return name+ ":" + age;}}

Create a Person entity class, implement the Comparable interface, and override the compareTo method. The custom sorting test method is implemented through the variable age as follows:

Public static void main (String [] args) {Set treeSet = new TreeSet (); System.out.println ("treeSet initial capacity size:" + treeSet.size ()); treeSet.add (new Person ("Li Yi", 18)); treeSet.add (new Person ("Li er", 17)); treeSet.add (new Person ("Li San", 19)); treeSet.add ("Li Si", 21)) TreeSet.add (new Person ("Li Wu", 20)); System.out.println ("treeSet capacity size:" + treeSet.size ()); System.out.println ("sort results customized by age:"); / / iterator traversing Iterator iterator = treeSet.iterator (); while (iterator.hasNext ()) {Person person = iterator.next () System.out.print (person.toString () + ",");}}

Output result:

TreeSet initial capacity size: 0 treeSet capacity size: 5 according to age, custom sorting results: Li 2: 17, Li Yi: 18, Li San: 19, Li Wu: 20, Li Si: 21

Method two

The second method is that in the initialization phase of TreeSet, Person does not need to implement the Comparable interface, but initializes the Comparator interface as a parameter in the form of an inner class, as follows:

Public static void main (String [] args) {/ / Custom sorting Set treeSet = new TreeSet (new Comparator () {@ Override public int compare (Person o1, Person O2) {if (o1 = = null | | O2 = = null) {/ / do not compare return 0 } / / sort from small to large return o1.getAge ()-o2.getAge ();}}); System.out.println ("treeSet initial capacity size:" + treeSet.size ()); treeSet.add (new Person ("Li Yi", 18)); treeSet.add (new Person ("Li er", 17)) TreeSet.add (new Person ("Li San", 19); treeSet.add (new Person ("Li Si", 21)); treeSet.add (new Person ("Li Wu", 20)); System.out.println ("treeSet capacity size:" + treeSet.size ()); System.out.println ("Custom sorting results by age:"); / / iterator traversing Iterator iterator = treeSet.iterator () While (iterator.hasNext ()) {Person person = iterator.next (); System.out.print (person.toString () + ",");}}

Output result:

TreeSet initial capacity size: 0 treeSet capacity size: 5 according to age, custom sorting results: Li 2: 17, Li Yi: 18, Li San: 19, Li Wu: 20, Li Si: 21

It should be noted that TreeSet cannot be added as an empty element, otherwise a null pointer error will be reported!

05. EnumSet

EnumSet is a dedicated Set collection used with enumerated types and inherits from the AbstractSet abstract class. Unlike HashSet, LinkedHashSet, and TreeSet, EnumSet elements must be of type Enum, and all elements must come from the same enumerated type. The source code of EnumSet definition is as follows:

Public abstract class EnumSet extends AbstractSet implements Cloneable, java.io.Serializable {. }

EnumSet is a virtual class, and you can't get an object directly through instantiation. Instead, you can only return an instance of the EnumSet implementation class through the static methods it provides.

There are two implementation classes for EnumSet, namely RegularEnumSet and JumboEnumSet, both of which inherit from EnumSet.

EnumSet will decide which implementation class to return based on the number of elements in the enumerated type. If the number of elements in the EnumSet element is less than or equal to 64, the RegularEnumSet instance will be returned; when the number of EnumSet elements is greater than 64, the JumboEnumSet instance will be returned.

As we can see from the source code, the source code is as follows:

Public static EnumSet noneOf (Class elementType) {Enum [] universe = getUniverse (elementType); if (universe = = null) throw new ClassCastException (elementType + "not an enum"); / / return RegularEnumSet if (universe.length) when the number of elements is less than or equal to 64

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.