Analyse détaillée du code source de la classe de collection Set in Java

L'éditeur suivant vous apportera une explication détaillée de l'analyse du code source de la classe de collection Set in Java. L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur pour jeter un œil

La collection Set, comme List, hérite de l'interface Collection. Les classes d'implémentation couramment utilisées incluent HashSet et TreeSet. Il convient de noter que HashSet est implémenté via HashMap et TreeSet est implémenté via TreeMap, donc ni HashSet ni TreeSet n'ont leur propre structure de données. Les détails peuvent être résumés comme suit :

• Les éléments de la collection Set ne peuvent pas. Duplication, c'est-à-dire que les éléments sont uniques

•HashSet est stocké par la valeur de hachage de l'élément, il n'est donc pas ordonné et autorise au plus un objet nul

•TreeSet est stocké par la taille de l'élément, il est donc ordonné et les objets nuls ne sont pas autorisés

•La collection Set n'a pas de méthode get, donc les éléments ne peuvent être parcourus que via des itérateurs (Iterator), et l'accès aléatoire n'est pas possible

1 .HashSet

Une partie du code source de HashSet est donnée ci-dessous pour comprendre son implémentation.

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

En observant le code source, nous savons que les données de HashSet sont stockées dans la carte d'objets d'instance de HashMap, et correspondent à la clé dans le map et Object La référence de type PRESENT est une valeur virtuelle correspondant à la valeur dans la map et n'a aucune signification pratique. En pensant à certaines caractéristiques de HashMap : stockage désordonné, valeur de clé unique, etc., nous pouvons naturellement comprendre les caractéristiques des éléments de la collection Set qui ne peuvent pas être répétés et les caractéristiques de stockage désordonnées de HashSet.

Ce qui suit est une compréhension de l'utilisation de base de HashSet du point de vue du code source :

•Constructeur (quatre types)

1.HashSet() Constructeur vide, initialise un HashMap vide

2.HashSet(Collection2d4902c92e1e7bfd574f59708c57776a c) Passer dans un sous-ensemble c, utilisé pour initialiser HashMap

3.HashSet(int initialCapacity, float loadFactor) Initialiser un HashMap vide et spécifier la capacité initiale et le facteur de charge

4.HashSet(int initialCapacity) Initialiser un vide HashMap, et précisez la capacité initiale

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

• Insérer un élément

1.add(E e ) Insérez l'élément spécifié (implémenté en appelant la méthode put de HashMap)

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

•Trouver l'élément

1. contain(Object o) Déterminer si l'ensemble contient l'élément spécifié (implémenté en appelant la méthode containKey de HashMap)

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

2 Puisqu'il n'y a pas de méthode get dans. la classe d'implémentation de HashSet, peut uniquement être parcourue séquentiellement via les itérateurs, mais n'est pas accessible de manière aléatoire (appelant l'implémentation de l'itérateur de keySet dans HashMap)

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

Exemple d'application :

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

•Modifier les éléments

Étant donné que la valeur de la clé dans HashMap ne peut pas être modifiée, HashSet ne peut pas modifier les éléments

•Supprimer l'élément

1.remove(Object o) Supprimer l'élément spécifié (implémenté en appelant la méthode Remove dans HashMap, la valeur de retour est vraie ou fausse)

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

2.clear() Effacer l'élément (implémenté en appelant la méthode clear dans HashMap, aucune valeur de retour)

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

2.TreeSet

TreeSet est la seule classe d'implémentation de l'interface SortedSet. Comme mentionné précédemment, TreeSet n'a pas sa propre structure de données mais est implémenté via TreeMap, donc TreeSet est également une structure de stockage basée sur des arbres binaires rouges et noirs, donc TreeSet n'autorise pas les objets nuls et est stocké dans l'ordre (ordre croissant par défaut) .

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

Le NavigableMap dans le code source ci-dessus est une interface héritée de SrotedMap, et sa classe d'implémentation est TreeMap, donc les données dans le TreeSet sont stockées via le TreeMap PRESENT est ici aussi une valeur virtuelle sans signification pratique.

Ce qui suit est une compréhension de l'utilisation de base de HashSet du point de vue du code source :

•Constructeur (quatre types)

1.TreeSet() Constructeur vide, initialise un TreeMap vide, classé par ordre croissant par défaut

2.TreeSet(Comparator

3.TreeSet(Collection2d4902c92e1e7bfd574f59708c57776a c) Passer dans un sous-ensemble c, utilisé pour initialiser l'objet TreeMap, l'ordre croissant par défaut

4.TreeSet(SortedSet1a4db2c2c2313771e5742b6debf617a1 s) transmet un sous-ensemble ordonné s pour initialiser l'objet TreeMap, à l'aide du comparateur de sous-ensemble

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

Exemples d'application

//自定义一个比较器，实现降序排列
  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

• Insérer un élément

1.add(E e) Insérer l'élément spécifié (implémenté en appelant la méthode put de TreeMap)

2.addAll(Collection2d4902c92e1e7bfd574f59708c57776a c ) Insérer un sous-ensemble 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

• Rechercher un élément

1.contains(Object o) Déterminer si l'objet spécifié est inclus dans la collection (implémenté en appelant la méthode containKey de TreeMap)

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的存储结构及基本用法介绍完毕。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!