多用途・多学習のためのJavaのSet、List、Mapの詳細説明

長い間、コード内で頻繁に使用されるデータリストは主に List であり、それらはすべて ArrayList で十分だと感じています。 ArrayList は、動的配列を実装するために使用されるパッケージ化ツール クラスです。これにより、コードを作成するときに、取り出したり繰り返したりすることができ、非常に便利です。

いつから HashMap や HashSet などのツール クラスがコードに頻繁に登場するようになったのかはわかりません。 HashMap はさらに多くあり、これは面接の古典的な質問なので、もっと頻繁に見るつもりです。初めて使用するときは、単純にキーと値の対応表として理解すると、データを検索するときにキーを使用する方が便利です。さらに理解すると、これにはまだ少し謎があることがわかりました。特に、JDK の新しいバージョンで HashMap がツリーに変更された後は、コードが少し複雑です。

Set は最初はあまり使われませんでしたが、コード内で偶然 TreeSet を見つけて、このクラスがスムーズに使えることに気づき、それから徐々にこれも良いツールであることに気づきました。

コードをたくさん書いてみて基礎の重要性を感じたので、コレクションに関する知識を簡単に整理するためにここに短い記事を書きます。

それでは、簡単に整理してみましょう:

•リスト: リストであり、配列とリンクされたリストの機能をサポートし、一般に線形です

•マップ: キーとキー間の対応関係を格納するマッピングテーブルです。値

•Set: セットを意味し、主にデータの重複排除と並べ替えに使用されます


まず List を見てみましょう

List は、次のような線形データを格納するために使用されるウィンドウです: 配列の ArrayList と配列の ArrayList LinkedList の LinkedListリスト。

ArrayList

これは配列リストですが、自動展開の機能を提供し、Listインターフェースを実装しており、インターフェースで宣言されたメソッドを通じて外部操作にアクセスできるため、安全で便利です。

ArrayList の重要な点は、オブジェクトが初期化されるときに、初期容量またはデフォルト容量を設定できることです。配列のサイズが特に明確でない場合は、初期サイズを指定する必要はありません。明確な場合は、動的拡張による遅延を軽減するためにサイズを指定できます。そういえば、拡張がどのように行われるかについて話しましょう。次のコードを見てください。

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 は、ArrayList が要素またはいくつかの簡単なチェックを追加するときにトリガーされるメソッドです。主なプロセス:

1. 配列の長さを取得して右にシフトし、oldCapacity/2 に相当し、新しい長さを取得します

2. 長さが最小容量より小さい場合は、最小値を使用します。 Easy

3 . 最大値より大きい場合は、ここで hugeCapacity メソッドが呼び出され、主に minCapacity と MAX_ARRAY_SIZE が大きい場合は Integer.MAX_VALUE を取得します。 MAX_ARRAY_SIZE 興味深いのは、MAX_ARRAY_SIZE が .MAX_VALUE - 8 であることです。これが何を意味するのかわかりません。最後のステップは、既存の数値を新しい配列にコピーすることです。

このコピープロセスのため、配列が比較的大きい場合、展開が常にトリガーされると当然遅延が発生します。したがって、最大値が最初からわかっていて、この値まで簡単に増加できる場合は、初期化の開始時にサイズを指定すると、ある程度の効果が得られる可能性があります。

LinkedList

これはリンク リストのツール クラスです。リンク リストの利点は、追加と削除が高速であることですが、検索は遅くなります。

コードに関しては、何も特別なことはないようです。もちろん、Java は、代わりにオブジェクトを使用して、前のノードと次のノードを指します。これはリンクされたリストの構造です:

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

次に、2 つのノードを使用して先頭と末尾を指します:

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

追加操作を見てください:

/**
 
   * 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.最後のノードを l に置きます

2. 新しいノードを作成し、このノードにデータをフェッチします。作成プロセスでは、新しいノードの prev を l にポイントし、チェーンを接続します

3。 new Node

4. 次に、l が null であるかどうかを判断します。null の場合は、新しいノードが最初の要素であることを意味するため、空でない場合は、最初に newNode

5 をポイントする必要があります。 , l の次を newNode に向けます

6. 累積カウンタを削除します

この操作は、前後の Node によって指示される移動操作でもあります。

Mapをもう一度見てみましょう

Mapは、キーと値の間のマッピングテーブルを作成するアプリケーションです。主な実装クラスは、HashMap、HashTable、TreeMap

HashMap、HashTable

です。ハッシュアルゴリズムを使用するクラスです。キーと値のマッピングの場合は HashMap ですが、HashTable は同期を備えたスレッドセーフなクラスです。これらの主な違いは次のとおりです。原理も同様で、どちらもバケット + チェーンの組み合わせによって実装されます。バケットはキーの保存に使用されますが、ハッシュの衝突のため、値はリンクされたリストに保存する必要があります。

•バケットの意味は、ハッシュ計算により1ステップで特定できる高効率です

•リンクリストの意味は、繰り返しハッシュ化されたデータを保存および取得することです

具体的な原理は以前に書かれています「勉強ノート：ハッシュテーブル」とHashMap」

読んでみてください。 JDK1.8のHashMapは、記憶構造を変更し、赤黒ツリー構造を採用しました。これにより、リンクリストの検索効率の問題が解決される可能性がありますよね?詳細な研究はありません。

ツリーマップ

看过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实现了NavigableMapb77a8d9c3c319e50d4b02a976b347910接口，所以也提供了对数据集合的一些返回操作。

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