Explication détaillée de Set, List et Map en Java pour le multi-usage et le multi-apprentissage

Pendant longtemps, la liste de données qui a été utilisée le plus fréquemment dans le code est principalement List, et ce sont toutes des ArrayList. Je pense que cette chose est suffisante. ArrayList est une classe d'outils d'empaquetage utilisée pour implémenter des tableaux dynamiques. De cette façon, vous pouvez extraire et extraire du code lors de l'écriture, ce qui est très pratique.

Je ne sais pas depuis quand des outils tels que HashMap et HashSet sont souvent apparus dans le code. Il faut dire qu'il y a plus de HashMap, et c'est une question d'entretien classique, donc j'y regarde généralement davantage. Lorsque vous commencez à l'utiliser, vous pouvez simplement le comprendre comme un tableau de correspondance clé-valeur. Il est plus pratique d'utiliser des clés pour rechercher des données. Après une meilleure compréhension, j'ai découvert

qu'il y avait encore un petit mystère dans cette chose, surtout après que la nouvelle version du JDK ait changé HashMap en arbre, le code est un peu compliqué.

Set était moins utilisé au début. J'ai juste accidentellement découvert un TreeSet dans un code et j'ai découvert que cette classe pouvait être utilisée sans problème, puis j'ai petit à petit découvert que c'était aussi un bon outil.

Après avoir écrit beaucoup de code, je ressens l'importance des bases, je vais donc écrire un court article ici pour organiser brièvement quelques connaissances sur les collections.

D'accord, organisons-le brièvement :

•Liste : c'est une liste, prend en charge les fonctions de tableaux et de listes chaînées, et est généralement linéaire
•Carte : c'est une cartographie table, Ce qui est stocké est la relation correspondante entre les clés et les valeurs
•Set : cela signifie ensemble, principalement utilisé pour la déduplication des données et le tri

Jetons un coup d'œil à List

List est une fenêtre utilisée pour stocker des données linéaires, telles que ArrayList pour les tableaux et LinkedList pour les listes chaînées.

ArrayList

Il s'agit d'une liste de tableaux, mais elle fournit la fonction d'expansion automatique et implémente l'interface List. Les opérations externes sont accessibles via les méthodes déclarées dans l'interface, ce qui est sûr et pratique. .

La clé d'ArrayList est l'expansion automatique. Lorsque l'objet est initialisé, vous pouvez définir la capacité initiale ou la capacité par défaut. Si la taille du tableau n'est pas particulièrement claire, vous n'avez pas besoin de spécifier la taille initiale. Si elle est claire, vous pouvez spécifier une taille pour réduire le décalage provoqué par l'expansion dynamique. En parlant de cela, parlons de la façon dont l'expansion est réalisée. Regardez le code suivant :

private void grow(int minCapacity) {
 
    // overflow-conscious code
 
    int oldCapacity = elementData.length;
 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
 
    if (newCapacity - minCapacity < 0)
 
      newCapacity = minCapacity;
 
    if (newCapacity - MAX_ARRAY_SIZE > 0)
 
      newCapacity = hugeCapacity(minCapacity);
 
    // minCapacity is usually close to size, so this is a win:
 
    elementData = Arrays.copyOf(elementData, newCapacity);
 
  }

grow est une méthode qui est déclenchée lorsque ArrayList ajoute des éléments ou effectue des vérifications simples. Processus principal :

1. Obtenez la longueur du tableau et décalez-la vers la droite, ce qui équivaut à oldCapacity/2, obtenez la nouvelle longueur

2. capacité, alors utilisez simplement le minimum easy

3. S'il est supérieur au maximum easy, prenez une valeur maximale. Une méthode hugeCapacity sera appelée ici, principalement pour comparer minCapacity avec MAX_ARRAY_SIZE Si minCapacity est supérieur à. MAX_ARRAY_SIZE, prenez Integer.MAX_VALUE, sinon prenez simplement MAX_ARRAY_SIZE. Ce qui est intéressant, c'est que MAX_ARRAY_SIZE prend Integer.MAX_VALUE - 8 ; je ne sais pas ce que cela signifie

4. une méthode de copie pour copier le numéro existant dans un nouveau tableau.

En raison de ce processus de copie, si le tableau est relativement grand, il y aura bien sûr des décalages si l'expansion est toujours déclenchée. Ainsi, si la valeur maximale est connue depuis le début et peut facilement atteindre cette valeur, alors spécifier la taille au début de l'initialisation aura un certain effet.

LinkedList

Il s'agit d'une classe d'outils pour les listes chaînées. L'avantage des listes chaînées est qu'elles sont plus rapides à ajouter et à supprimer, mais la recherche sera plus lente.

Quant au code, il ne semble y avoir rien de spécial. Il s'agit simplement d'une série de pointeurs liés entre eux. Bien sûr, les objets sont utilisés à la place en Java pour créer un objet Node lui-même. Noeud et le noeud suivant. Voici la structure de la liste chaînée :

private static class Node<E> {
 
   E item;
 
   Node<E> next;
 
   Node<E> prev;
 
 
 
   Node(Node<E> prev, E element, Node<E> next) {
 
     this.item = element;
 
     this.next = next;
 
     this.prev = prev;
 
   }
 
 }

Utilisez ensuite deux noeuds pour pointer vers la tête et la queue :

/**
 
   * Pointer to first node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (first.prev == null && first.item != null)
 
   */
 
  transient Node<E> first;
 
  
 
  /**
 
   * Pointer to last node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (last.next == null && last.item != null)
 
   */
 
  transient Node<E> last;

Regardez. lors d'une opération d'ajout :

/**
 
   * Links e as last element.
 
   */
 
  void linkLast(E e) {
 
    final Node<E> l = last;
 
    final Node<E> newNode = new Node<>(l, e, null);
 
    last = newNode;
 
    if (l == null)
 
      first = newNode;
 
    else
 
      l.next = newNode;
 
    size++;
 
    modCount++;
 
  }

Le passé est :

1. Récupérez le dernier nœud et mettez-le dans l

2. Créez un nouveau nœud et récupérez le. données dans ce nœud. Le processus de création sera Le précédent du nouveau nœud pointe vers l, connectant ainsi la chaîne

3 Puis pointez en dernier vers ce nouveau nœud

Ensuite, jugez si l. est nul. S'il est nul, cela signifie qu'il s'agit d'une liste chaînée vide. Le nouveau nœud est le premier élément, il doit donc d'abord pointer vers newNode

5. vers newNode

6. Supprimer le compteur cumulatif

L'opération est également une opération de déplacement dirigée par le Node avant et après le Node.

Jetons un coup d'œil à Map

Map est une application qui crée une table de mappage entre les clés et les valeurs. Les principales classes d'implémentation sont : HashMap, HashTable, TreeMap

<. 🎜>HashMap et HashTable

Celui qui utilise l'algorithme de hachage pour le mappage clé-valeur est HashMap. HashTable est une classe thread-safe avec synchronisation. La principale différence entre eux est la suivante. Le principe est également similaire, les deux sont mis en œuvre grâce à la combinaison de chaînes à godets. Les compartiments sont utilisés pour stocker les clés et, en raison des collisions de hachage, les valeurs doivent être stockées dans une liste chaînée.

•L'importance des buckets réside dans leur haute efficacité, qui peut être localisée en une seule étape grâce au calcul de hachage

•L'importance des listes chaînées réside dans l'accès aux données hachées en double

Le principe spécifique a été précédemment écrit dans une "Notes d'étude" : Hashtable et HashMap》

C'est juste que le HashMap du JDK1.8 a changé la structure de stockage et a adopté une structure arborescente rouge-noir Cela peut résoudre le problème de la liste chaînée. l'efficacité de la recherche, n'est-ce pas ? Il n’y a pas d’étude détaillée.

TreeMap

看过TreeMap的代码后发现还是使用的树结构，红黑树。由于红黑树是有序的，所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。

因为采用了树结构存储那么添加和删除数据时会麻烦一些，看一下put的代码：

public V put(K key, V value) {
 
    Entry<K,V> t = root;
 
    if (t == null) {
 
      compare(key, key); // type (and possibly null) check
 
  
 
      root = new Entry<>(key, value, null);
 
      size = 1;
 
      modCount++;
 
      return null;
 
    }
 
    int cmp;
 
    Entry<K,V> parent;
 
    // split comparator and comparable paths
 
    Comparator<? super K> cpr = comparator;
 
    if (cpr != null) {
 
      do {
 
        parent = t;
 
        cmp = cpr.compare(key, t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    else {
 
      if (key == null)
 
        throw new NullPointerException();
 
      @SuppressWarnings("unchecked")
 
        Comparable<? super K> k = (Comparable<? super K>) key;
 
      do {
 
        parent = t;
 
        cmp = k.compareTo(t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    Entry<K,V> e = new Entry<>(key, value, parent);
 
    if (cmp < 0)
 
      parent.left = e;
 
    else
 
      parent.right = e;
 
    fixAfterInsertion(e);
 
    size++;
 
    modCount++;
 
    return null;
 
  }

1、先是检查根节点是否存在，不存在说明是第一条数据，直接作为树的根

2、判断是否存在比较器，如果存在则使用比较器进行查找数据的存放位置，如果比较器返回结果小于0取左，大于0取右，否则直接替换当前节点的值

3、如果不存在比较器则key直接与节点的key比较，比较和前面方法一样

4、接下来就是在找到的parent上创建一个子节点，并放入左或者右子节点中

5、fixAfterInsertion是对节点进行着色

6、累加器处理

在remove操作时也会有点麻烦，除了删除数据外，还要重新平衡一下红黑树。

另外，TreeMap实现了NavigableMap接口，所以也提供了对数据集合的一些返回操作。

最后看看Set

Set主要是两类应用：HashSet和TreeSet。

HashSet

字面意思很明确，使用了Hash的集合。这种集合的特点就是使用Hash算法存数据，所以数据不重复，存取都相对较快。怎么做到的呢？

public boolean add(E e) {
 
    return map.put(e, PRESENT)==null;
 
  }

原来是存在一个map对象中，再看map是个啥？

private transient HashMap<E,Object> map;

是个HashMap，了解HashMap的就明白，这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的，所以在HashMap中只会存在一份。

了解了这点其他的东西就非常明白了。

TreeSet

这个集合是用于对集合进行排序的，也就是除了带有排重的能力外，还可以自带排序功能。只不过看了TreeSet的代码发现，其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。

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

所以，这里可能更关注的是TreeSet是如何排重呢？看一下add的方法吧：

public boolean add(E e) {
 
    return m.put(e, PRESENT)==null;
 
  }

和HashSet有点类似，都是基于Map的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了，希望大家多多支持PHP中文网~

更多多用多学之Java中的Set,List,Map详解相关文章请关注PHP中文网！