Detaillierte Erläuterung von Set, List und Map in Java für Mehrfachnutzung und Mehrfachlernen

Die Datenlisten, die in Codes seit langem häufiger verwendet werden, sind hauptsächlich Listen, und sie sind alle ArrayLists. Ich denke, dass es ausreicht, dieses Ding zu haben. ArrayList ist eine Verpackungstoolklasse, die zum Implementieren dynamischer Arrays verwendet wird. Auf diese Weise können Sie beim Schreiben von Code ein- und aussteigen und iterieren, was sehr praktisch ist.

Ich weiß nicht, seit wann Toolklassen wie HashMap und HashSet oft im Code auftauchten. Es sollte gesagt werden, dass es mehr HashMap gibt und es sich um eine klassische Interviewfrage handelt, daher werde ich sie mir öfter ansehen. Wenn Sie es zum ersten Mal verwenden, können Sie es einfach als Schlüssel-Wert-Korrespondenztabelle verstehen. Es ist bequemer, Schlüssel zum Suchen von Daten zu verwenden. Nach weiterem Verständnis stellte ich

fest, dass diese Sache immer noch ein wenig rätselhaft ist, insbesondere nachdem die neue Version von JDK HashMap in einen Baum geändert hat, ist der Code etwas kompliziert.

Set wurde zunächst weniger verwendet. Ich habe zufällig ein TreeSet in einem Code entdeckt und festgestellt, dass diese Klasse reibungslos verwendet werden kann, und dann habe ich langsam festgestellt, dass es sich auch um ein gutes Werkzeug handelt.

Nachdem ich viel Code geschrieben habe, spüre ich, wie wichtig die Grundlagen sind, deshalb werde ich hier einen kurzen Artikel schreiben, um kurz etwas Wissen über Sammlungen zu organisieren.

Okay, lass es uns kurz organisieren:

•Liste: Es ist eine Liste, unterstützt die Funktionen von Arrays und verknüpften Listen und ist im Allgemeinen linear
•Map: Es ist eine Zuordnung Tabelle, Was gespeichert wird, ist die entsprechende Beziehung zwischen Schlüsseln und Werten
•Set: Es bedeutet Set, wird hauptsächlich zum Deduplizieren von Daten und Sortieren verwendet

Werfen wir einen Blick auf die Liste

List ist ein Fenster zum Speichern linearer Daten, z. B. ArrayList für Arrays und LinkedList für verknüpfte Listen.

ArrayList

Dies ist eine Array-Liste, die jedoch die Funktion der automatischen Erweiterung bietet und die List-Schnittstelle implementiert. Der Zugriff auf externe Operationen erfolgt über die in der Schnittstelle deklarierten Methoden, was sicher und praktisch ist .

Der Schlüssel zu ArrayList ist die automatische Erweiterung. Wenn das Objekt initialisiert wird, können Sie die Anfangskapazität oder die Standardkapazität festlegen. Wenn die Array-Größe nicht besonders klar ist, müssen Sie die Anfangsgröße nicht angeben. Wenn sie klar ist, können Sie eine Größe angeben, um die durch die dynamische Erweiterung verursachte Verzögerung zu verringern. Apropos: Schauen wir uns den folgenden Code an:

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 ist eine Methode, die ausgelöst wird, wenn ArrayList Elemente hinzufügt oder einige einfache Prüfungen durchführt. Hauptprozess:

1. Ermitteln Sie die Länge des Arrays und verschieben Sie es nach rechts, was oldCapacity/2 entspricht. Ermitteln Sie die neue Länge

2. Wenn diese Länge kleiner als das Minimum ist Kapazität, dann verwenden Sie einfach die minimale einfache

3. Wenn sie größer als die maximale einfache ist, wird hier eine HugeCapacity-Methode aufgerufen, hauptsächlich um minCapacity mit MAX_ARRAY_SIZE zu vergleichen MAX_ARRAY_SIZE, nimm Integer.MAX_VALUE, sonst nimmst du einfach MAX_ARRAY_SIZE. Das Interessante ist, dass MAX_ARRAY_SIZE Integer.MAX_VALUE - 8 benötigt. Der letzte Schritt ist der Aufruf eine Kopiermethode zum Kopieren der vorhandenen Nummer in ein neues Array.

Wenn das Array aufgrund dieses Kopiervorgangs relativ groß ist, kommt es natürlich zu Verzögerungen, wenn die Erweiterung immer ausgelöst wird. Wenn also der Maximalwert von Anfang an bekannt ist und problemlos auf diesen Wert anwachsen kann, hat die Angabe der Größe zu Beginn der Initialisierung einen gewissen Effekt.

LinkedList

Dies ist eine Toolklasse für verknüpfte Listen. Der Vorteil verknüpfter Listen besteht darin, dass sie schneller hinzugefügt und gelöscht werden können, die Suche jedoch langsamer ist.

Was den Code betrifft, scheint es sich nur um eine Reihe miteinander verknüpfter Zeiger zu handeln. Natürlich verwendet Java stattdessen Objekte, um ein Knotenobjekt zu erstellen Der nächste Knoten. Dies ist die Struktur der verknüpften Liste:

Dann verwenden Sie zwei Knoten, um auf den Kopf und das Ende zu zeigen:

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

Sehen Sie sich an Operation hinzufügen:

/**
 
   * 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;

Die Vergangenheit ist:

/**
 
   * 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++;
 
  }

1 Holen Sie sich den letzten Knoten und fügen Sie ihn in l ein.

2. Erstellen Sie einen neuen Knoten und rufen Sie die Daten ab Dieser Knoten. Der Erstellungsprozess zeigt auf l und verbindet somit die Kette

3. Dann wird auf den neuen Knoten verwiesen

4 . Wenn es null ist, bedeutet dies, dass es sich um eine leere verknüpfte Liste handelt. Das erste Element muss also auch auf newNode zeigen.

5 Wenn es nicht leer ist, zeigen Sie als nächstes auf newNode

6. Den kumulativen Zähler löschen

Der Vorgang ist auch ein Verschiebungsvorgang, der vom Knoten vor und nach dem Knoten gesteuert wird.

Werfen wir einen Blick auf Map

Map ist eine Anwendung, die eine Zuordnungstabelle zwischen Schlüsseln und Werten erstellt. Die wichtigsten Implementierungsklassen sind: HashMap, HashTable, TreeMap

HashMap und HashTable

Diejenige, die einen Hash-Algorithmus für die Schlüsselwertzuordnung verwendet, ist HashMap, eine threadsichere Klasse mit Synchronisierung. Der Hauptunterschied zwischen ihnen ist dieser. Auch das Prinzip ist ähnlich, beides wird durch die Kombination von Eimer + Kette umgesetzt. Buckets werden zum Speichern von Schlüsseln verwendet. Aufgrund von Hash-Kollisionen müssen Werte in einer verknüpften Liste gespeichert werden.

•Die Bedeutung von Buckets liegt in der hohen Effizienz, die in einem Schritt durch Hash-Berechnung ermittelt werden kann

•Die Bedeutung verknüpfter Listen liegt im Zugriff auf doppelt gehashte Daten

Das spezifische Prinzip wurde zuvor in „Study Notes“ geschrieben: Hashtable und HashMap》

Es ist nur so, dass die HashMap von JDK1.8 die Speicherstruktur geändert und eine rot-schwarze Baumstruktur übernommen hat. Dies könnte das Problem der verknüpften Liste lösen Sucheffizienz, oder? Eine detaillierte Studie gibt es nicht.

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中文网！