Detailed analysis of Set in Java collection class source code

The following editor will bring you a detailed explanation of Set in java collection class source code analysis. The editor thinks it’s pretty good, so I’ll share it with you now and give it as a reference. Let’s follow the editor to take a look.

Set collection, like List, inherits from Collection interface. Commonly used implementation classes include HashSet and TreeSet. It is worth noting that HashSet is implemented through HashMap and TreeSet is implemented through TreeMap, so neither HashSet nor TreeSet has its own data structure. The details can be summarized as follows:

•The elements in the Set collection cannot Duplication, that is, the element is unique

•HashSet is stored according to the hash value of the element, so it is unordered, and allows at most one null object

•TreeSet is stored according to the size of the element, so there is Sequential, and null objects are not allowed

•Set collection has no get method, so elements can only be traversed through iterators (Iterator), and random access is not possible

1 .HashSet

Part of the source code of HashSet is given below to understand its implementation.

static final long serialVersionUID = -5024744406713321676L;

 private transient HashMap<E,Object> map;

 // Dummy value to associate with an Object in the backing Map
 private static final Object PRESENT = new Object();

Observing the source code, we know that the data of HashSet is stored in the instance object map of HashMap, and corresponds to the key in the map, and the Object type The reference to PRESENT is a virtual value corresponding to the value in the map and has no practical meaning. Thinking of some features of HashMap: unordered storage, unique key values, etc., we can naturally understand the characteristics of Set collection elements that cannot be repeated and the unordered storage features of HashSet.

Let’s understand the basic usage of HashSet from the perspective of source code:

•Constructor (four types)

1.HashSet() Empty constructor, initializes an empty HashMap

2.HashSet(Collection c) Pass in a subset c, used to initialize HashMap

3.HashSet(int initialCapacity, float loadFactor) Initialize an empty HashMap and specify the initial capacity and load factor

4.HashSet(int initialCapacity) Initialize an Empty HashMap, and specify the initial capacity

public HashSet() {
  map = new HashMap<>();
 }

 public HashSet(Collection<? extends E> c) {
  map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
  addAll(c);
 }

 public HashSet(int initialCapacity, float loadFactor) {
  map = new HashMap<>(initialCapacity, loadFactor);
 }

 public HashSet(int initialCapacity) {
  map = new HashMap<>(initialCapacity);
 }

•Insert element

1.add(E e) Insert Specify the element (implemented by calling the put method of HashMap)

   Set<String> hashSet = new HashSet<String>();
   hashSet.add("D");
   hashSet.add("B");
   hashSet.add("C");
   hashSet.add("A");

•Find the element

1.contains(Object o) Judgment set Whether the specified element is included (implemented by calling the containsKey method of HashMap)

  public boolean contains(Object o) {
   return map.containsKey(o);
  }

2. Since there is no get method in the implementation class of HashSet, it can only be traversed sequentially through iterators , without random access (calling the iterator implementation of keySet in HashMap)

  public Iterator<E> iterator() {
   return map.keySet().iterator();
  }

Application example:

Set<String> hashSet = new HashSet<String>();
  hashSet.add("D");
  hashSet.add("B");
  hashSet.add("C");
  hashSet.add("A");
  for (Iterator iterator = hashSet.iterator(); iterator.hasNext();) {
   String string = (String) iterator.next();
   System.out.print(string+" ");
  }//D A B C

•Modify elements

Since the key value in HashMap cannot be modified, HashSet cannot modify elements

•Delete elements

1.remove(Object o) Delete the specified element (implemented by calling the remove method in HashMap, the return value is true or false)

  public boolean remove(Object o) {
   return map.remove(o)==PRESENT;
  }

2. clear() clears the element (implemented by calling the clear method in HashMap, no return value)

public void clear() {
   map.clear();
  }

2.TreeSet

TreeSet is the only implementation class of the SortedSet interface. As mentioned before, TreeSet does not have its own data structure but is implemented through TreeMap, so TreeSet is also a storage structure based on red and black binary trees, so TreeSet does not allow null objects and is stored in order (default ascending order).

private transient NavigableMap<E,Object> m;
 
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

The NavigableMap in the above source code is an interface inherited from SrotedMap, and its implementation class is TreeMap, so the data in the TreeSet is stored through the TreeMap, here The PRESENT is also a dummy value with no practical meaning.

Let’s understand the basic usage of HashSet from the perspective of source code:

•Constructor (four types)

1.TreeSet() Empty constructor, initializes an empty TreeMap, arranged in ascending order by default

2.TreeSet(Comparator comparator) Pass Enter a custom comparator, often used to implement descending order

3.TreeSet(Collection c) Pass in a subset c, used to initialize the TreeMap object, the default is ascending

4.TreeSet(SortedSet s) Pass in an ordered subset s, used to initialize the TreeMap object, using the subset comparator

public TreeSet() {
  this(new TreeMap<E,Object>());
 }

 public TreeSet(Comparator<? super E> comparator) {
  this(new TreeMap<>(comparator));
 }

 public TreeSet(Collection<? extends E> c) {
  this();
  addAll(c);
 }

 public TreeSet(SortedSet<E> s) {
  this(s.comparator());
  addAll(s);
 }

Application example

//自定义一个比较器，实现降序排列
  Set<Integer> treeSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  treeSet.add(200);
  treeSet.add(120);
  treeSet.add(150);
  treeSet.add(110);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110

ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  //传入一个子集，默认升序排列
  TreeSet<Integer> treeSet = new TreeSet<Integer>(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300

/*
   * 传入一个有序的子集，采用子集的比较器
   *  注意子集的类型必须是SortedSet及其子类或者实现类，否则将采用默认的比较器
   *  所以此处subSet的类型也可以是TreeSet。
   */
  
  SortedSet<Integer> subSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  subSet.add(200);
  subSet.add(120);
  subSet.add(150);
  subSet.add(110);
  for (Iterator iterator = subSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110 
  
  System.out.println();
  Set<Integer> treeSet = new TreeSet<Integer>(subSet);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//200 150 120 110 
  
  System.out.println();
  treeSet.add(500);
  treeSet.add(100);
  treeSet.add(105);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//500 200 150 120 110 105 100

• Inserting elements

1.add(E e) Insert the specified element (implemented by calling the put method of TreeMap)

2.addAll(Collection c) Insert a subset c

ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  Set<Integer> treeSet = new TreeSet<Integer>();
  
  //插入一个子集，默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300

•Find elements

1.contains(Object o) Determine whether the collection contains the specified object (call TreeMap containsKey method implementation)

2.与HashSet一样，TreeSet的实现类中没有get方法，所以只能通过迭代器依次遍历，而不能随机访问（调用TreeMap中keySet的迭代器实现）。

•修改元素

TreeSet不能进行修改元素的操作，原因与HashSet一样。

•删除元素

1.remove(Object o) 删除指定元素（调用TreeMap中的remove方法实现，返回true或者false）

  public boolean remove(Object o) {
   return m.remove(o)==PRESENT;
  }

2.clear() 清空元素（调用TreeMap中的clear方法实现，无返回值）

  public void clear() {
   m.clear();
  }

应用示例：

ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]
  
  Set<Integer> treeSet = new TreeSet<Integer>();
  
  //插入一个子集，默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300 
  
  System.out.println(treeSet.remove(100));//true
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//120 150 300 
  
  treeSet.clear();
  System.out.println(treeSet.size());//0

至此，HashSet和TreeSet的存储结构及基本用法介绍完毕。

The above is the detailed content of Detailed analysis of Set in Java collection class source code. For more information, please follow other related articles on the PHP Chinese website!