Java HashSet にトラバーサル要素を追加する方法

HashSet クラス図

##HashSet の簡単な説明

1.

HashSet は Set インターフェイスを実装します

2.

HashSet 最下層は実際には HashMap

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

3 によって実装されています。

null を格納できますが、そこにのみ格納できます。 null

4.

HashSet は、要素が順序どおりであることを保証しません (つまり、要素が格納される順序が保証されません) hash に応じて、要素が取り出された順序と一致します) その後、インデックスの結果を決定します

5. 重複する要素はありません

HashSet基礎となるメカニズムの説明

HashSet 最下層 HashMap、HashMap 最下層は 配列リンクリスト赤黒ツリー

配列リンク リストの構造のシミュレーション

/**
 * 模拟 HashSet 数组+链表的结构
 */
public class HashSetStructureMain {
    public static void main(String[] args) {
        // 模拟一个 HashSet(HashMap) 的底层结构
        // 1. 创建一个数组，数组的类型为 Node[]
        // 2. 有些地方直接把 Node[] 数组称为 表
        Node[] table = new Node[16];
        System.out.println(table);
        // 3. 创建节点
        Node john = new Node("john", null);
        table[2] = jhon; // 把节点 john 放在数组索引为 2 的位置
        Node jack = new Node("jack", null);
        jhon.next = jack; // 将 jack 挂载到 jhon 的后面
        Node rose = new Node("rose", null);
        jack.next = rose; // 将 rose 挂载到 jack 的后面
        Node lucy = new Node("lucy", null);
        table[3] = lucy; // 将 lucy 放在数组索引为 3 的位置
        System.out.println(table);

    }
}

// 节点类 存储数据，可以指向下一个节点，从而形成链表
class Node{
    Object item; // 存放数据
    Node next; // 指向下一个节点
    public Node(Object item, Node next){
        this.item = item;
        this.next = next;
    }
}

HashSet 要素を追加する基礎となるメカニズム

HashSet 要素を追加する基礎となる実装

1.

HashSet 基礎となるメカニズムは HashMap

2 です。要素を追加するときは、最初に

を取得します。追加する 要素の hash 値を取得し、index 値

3. ストレージ データ テーブル (ノード配列)

table をクエリします。 追加する現在の 要素 に対応する index 値 が保存されているかどうかを確認します その他の要素

4。現在の

index 値に対応する位置は存在しません 他の要素、追加される現在の 要素は この に対応する位置に配置しますインデックス値

5. 現在の

index 値 に対応する位置が other elements に存在する場合は、 To be added element.equals (既存の要素) を比較し、結果が true の場合は追加を中止し、結果が false の場合は 追加する要素 は既存要素の後ろに配置 (既存要素.next = 追加する要素)

HashSet拡張メカニズム

1.

HashSet 最下層は HashMap です。初めて要素を追加するとき、table 配列は cap = 16, threshold# に展開されます##(臨界値) = cap *loadFactor(負荷係数 0.75) = 122.

table

配列が臨界値 12 に達すると、 に拡張されます。 cap * 2 = 32、新しいクリティカル値は 32 * 0.75 = 24 など、3. Java8 では、リンク リストの要素数が # の場合、 ##Arrived

TREEIFY_THRESHOLD (デフォルトは 8)、および table>>= MIN_TREEIFY_CAPACITY (デフォルトは 64) のサイズの場合、処理は続行されます Tree (赤黒ツリー)4. 展開するかどうかは、 サイズ > しきい値

に基づいて決定されます。つまり、展開するかどうかは、ファイルに格納されている内容に基づいて決まります。

HashMap table.length() が臨界値を超えているかどうかではなく、要素数 (size) が臨界値を超えているかどうか HashSet は要素のソース コードを追加します

/**
 * HashSet 源码分析
 */
public class HashSetSourceMain {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set = " + hashSet);

        // 源码分析
        // 1. 执行 HashSet()
        /**
         * public HashSet() { // HashSet 底层是 HashMap
         *         map = new HashMap<>();
         *     }
         */

        // 2. 执行 add()
        /**
         * public boolean add(E e) { // e == "java"
         *         // HashSet 的 add() 方法其实是调用 HashMap 的 put()方法
         *         return map.put(e, PRESENT)==null; // (static) PRESENT = new Object(); 用于占位
         *     }
         */

        // 3. 执行 put()
        // hash(key) 得到 key(待存元素) 对应的hash值，并不等于 hashcode()
        // 算法是 h = key.hashCode()) ^ (h >>> 16
        /**
         * public V put(K key, V value) {
         *         return putVal(hash(key), key, value, false, true);
         *     }
         */

        // 4. 执行 putVal()
        // 定义的辅助变量：Node<K,V>[] tab; Node<K,V> p; int n, i;
        // table 是 HashMap 的一个属性，初始化为 null；transient Node<K,V>[] table;
        // resize() 方法，为 table 数组指定容量
        // p = tab[i = (n - 1) & hash] 计算 key的hash值所对应的 table 中的索引位置，将索引位置对应的 Node 赋给 p
        /**
         * final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
         *                    boolean evict) {
         *         Node<K,V>[] tab; Node<K,V> p; int n, i; // 辅助变量
         *         // table 就是 HashMap 的一个属性，类型是 Node[]
         *         // if 语句表示如果当前 table 是 null，或者 table.length == 0
         *         // 就是 table 第一次扩容，容量为 16
         *         if ((tab = table) == null || (n = tab.length) == 0)
         *             n = (tab = resize()).length;
         *         // 1. 根据 key，得到 hash 去计算key应该存放到 table 的哪个索引位置
         *         // 2. 并且把这个位置的索引值赋给 i；索引值对应的元素，赋给 p
         *         // 3. 判断 p 是否为 null
         *         // 3.1 如果 p 为 null，表示还没有存放过元素，就创建一个Node(key="java",value=PRESENT)，并把这个元素放到 i 的索引位置
         *         // tab[i] = newNode(hash, key, value, null);
         *         if ((p = tab[i = (n - 1) & hash]) == null)
         *             tab[i] = newNode(hash, key, value, null);
         *         else {
         *             Node<K,V> e; K k; // 辅助变量
         *             // 如果当前索引位置对应的链表的第一个元素和待添加的元素的 hash值一样
         *             // 并且满足下面两个条件之一：
         *             // 1. 待添加的 key 与 p 所指向的 Node 节点的key 是同一个对象
         *             // 2. 待添加的 key.equals(p 指向的 Node 节点的 key) == true
         *             // 就认为当前待添加的元素是重复元素，添加失败
         *             if (p.hash == hash &&
         *                 ((k = p.key) == key || (key != null && key.equals(k))))
         *                 e = p;
         *             // 判断 当前 p 是不是一颗红黑树
         *             // 如果是一颗红黑树，就调用 putTreeVal，来进行添加
         *             else if (p instanceof TreeNode)
         *                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         *             else {
         *                  // 如果 当前索引位置已经形成一个 链表，就使用 for 循环比较
         *                  // 将待添加元素依次和链表上的每个元素进行比较
         *                  // 1. 比较过程中如果出现待添加元素和链表中的元素有相同的，比较结束，出现重复元素，添加失败
         *                  // 2. 如果比较到链表最后一个元素，链表中都没出现与待添加元素相同的，就把当前待添加元素放到该链表最后的位置
         *                  // 注意：在把待添加元素添加到链表后，立即判断 该链表是否已经到达 8 个节点
         *                  // 如果到达，就调用 treeifyBin() 对当前这个链表进行数化(转成红黑树)
         *                  // 注意：在转成红黑树前，还要进行判断
         *                  // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         *                  //        resize();
         *                  // 如果上面条件成立，先对 table 进行扩容
         *                  // 如果上面条件不成立，才转成红黑树
         *                 for (int binCount = 0; ; ++binCount) {
         *                     if ((e = p.next) == null) {
         *                         p.next = newNode(hash, key, value, null);
         *                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
         *                             treeifyBin(tab, hash);
         *                         break;
         *                     }
         *                     if (e.hash == hash &&
         *                         ((k = e.key) == key || (key != null && key.equals(k))))
         *                         break;
         *                     p = e;
         *                 }
         *             }
         *             // e 不为 null ，说明添加失败
         *             if (e != null) { // existing mapping for key
         *                 V oldValue = e.value;
         *                 if (!onlyIfAbsent || oldValue == null)
         *                     e.value = value;
         *                 afterNodeAccess(e);
         *                 return oldValue;
         *             }
         *         }
         *         ++modCount;
         *         // 扩容：说明判断 table 是否扩容不是看 table 的length
         *         // 而是看 整个 HashMap 的 size(即已存元素个数)
         *         if (++size > threshold)
         *             resize();
         *         afterNodeInsertion(evict);
         *         return null;
         *     }
         */
    }
}

HashSet は要素の基礎となるメカニズムを横断します

HashSet は要素の基礎となるメカニズムを横断します

1.

HashSet

基礎となるメカニズムis

HashMap, HashSet イテレータは HashMap 2.HashSet.iterator()

によっても実装され、実際には呼び出されます

HashMap KeySet().iterator()

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

3.KeySet()

メソッドは

KeySet オブジェクトを返します。 KeySet は HashMap

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new KeySet();
        keySet = ks;
    }
    return ks;
}

4 の内部クラスです。KeySet().iterator()

メソッドは

KeyIterator# を返します## オブジェクト、KeyIterator は HashMap の内部クラスです。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class='brush:php;toolbar:false;'>public final Iterator&lt;K&gt; iterator() { return new KeyIterator(); }</pre><div class="contentsignin">ログイン後にコピー</div></div>5.KeyIterator は

HashIterator## の内部クラスを継承します。 #(

HashMap クラス) クラスを作成し、Iterator インターフェイスを実装します。つまり、KeyIterator と HashIterator が実際に実装するクラスです Iterator

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}

6. Iterator iterator = HashSet.iterator; を実行すると、要素ノード

が ## に格納されました。 #it​​erator オブジェクト。どうやってやったのですか?

手順 4 に戻り、
• KeySet().iterator()

  メソッドは

  KeyIterator
オブジェクト
• を返します。

• new KeyIterator() 调用 KeyIterator 的无参构造器

• 在这之前，会先调用其父类 HashIterator 的无参构造器

• 因此，分析 HashIterator 的无参构造器就知道发生了什么

/**
*         Node<K,V> next;        // next entry to return
*         Node<K,V> current;     // current entry
*         int expectedModCount;  // for fast-fail
*         int index;             // current slot
* HashIterator() {
*             expectedModCount = modCount;
*             Node<K,V>[] t = table;
*             current = next = null;
*             index = 0;
*             if (t != null && size > 0) { // advance to first entry
*                 do {} while (index < t.length && (next = t[index++]) == null);
*             }
*         }
*/

• next、current、index 都是 HashIterator 的属性

• Node<K,V>[] t = table; 先把 Node 数组 talbe 赋给 t

• current = next = null; current、next 都置为 null

• index = 0; index 置为 0

• do {} while (index < t.length && (next = t[index++]) == null); 这个 do-while 会在 table 中遍历 Node 结点

• 一旦 (next = t[index++]) == null 不成立 时，就说明找到了一个 table 中的 Node 结点

• 将这个节点赋给 next，并退出当前 do-while 循环

• 此时 Iterator iterator = HashSet.iterator; 就执行完了

• 当前 iterator 的运行类型其实是 HashIterator，而 HashIterator 的 next 中存储着从 table 中遍历出来的一个 Node 结点

7.执行 iterator.hasNext

此时的 next 存储着一个 Node，所以并不为 null，返回 true

public final boolean hasNext() {
    return next != null;
}

8.执行 iterator.next()

I.Node<K,V> e = next; 把当前存储着 Node 结点的 next 赋值给了 e

II.(next = (current = e).next) == null 判断当前结点的下一个结点是否为 null

• (a). 如果当前结点的下一个结点为 null，就执行 do {} while (index < t.length && (next = t[index++]) == null);，在 table 数组中遍历，寻找 table 数组中的下一个 Node 并赋值给 next

• (b). 如果当前结点的下一个结点不为 null，就将当前结点的下一个结点赋值给 next，并且此刻不会去 table 数组中遍历下一个 Node 结点

III.将找到的结点 e 返回

IV.之后每次执行 iterator.next() 都像 (a)、(b) 那样去判断遍历，直到遍历完成

HashSet 遍历元素源码

/**
 * HashSet 源码分析
 */
public class HashSetSourceMain {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("java");
        hashSet.add("php");
        hashSet.add("java");
        System.out.println("set = " + hashSet);
        // HashSet 迭代器实现原理
        // HashSet 底层是 HashMap，HashMap 底层是 数组 + 链表 + 红黑树
        // HashSet 本身没有实现迭代器，而是借由 HashMap 来实现的
        // 1. hashSet.iterator() 实际上是去调用 HashMap 的 keySet().iterator()
        /**
         * public Iterator iterator() {
         *         return map.keySet().iterator();
         *     }
         */
        // 2. KeySet() 方法返回一个 KeySet 对象，而 KeySet 是 HashMap 的一个内部类
        /**
         * public Set keySet() {
         *         Set ks = keySet;
         *         if (ks == null) {
         *             ks = new KeySet();
         *             keySet = ks;
         *         }
         *         return ks;
         *     }
         */
        // 3. KeySet().iterator() 方法返回一个 KeyIterator 对象，KeyIterator 是 HashMap的一个内部类
        /**
         * public final Iterator<K> iterator()     { return new KeyIterator(); }
         */
        // 4. KeyIterator 继承了 HashIterator(HashMap的内部类) 类，并实现了 Iterator 接口
        // 即 KeyIterator、HashIterator 才是真正实现 迭代器的类
        /**
         * final class KeyIterator extends HashIterator
         *         implements Iterator {
         *         public final K next() { return nextNode().key; }
         *     }
         */
        // 5. 当执行完 Iterator iterator = hashSet.iterator(); 后
        // 此时的 iterator 对象中已经存储了一个元素节点
        // 怎么做到的？
        // 回到第 3 步，KeySet().iterator() 方法返回一个 KeyIterator 对象
        // new KeyIterator() 调用 KeyIterator 的无参构造器
        // 在这之前，会先调用 KeyIterator 父类 HashIterator 的无参构造器
        // 因此分析 HashIterator 的无参构造器就知道发生了什么
        /**
         *         Node next;        // next entry to return
         *         Node current;     // current entry
         *         int expectedModCount;  // for fast-fail
         *         int index;             // current slot
         * HashIterator() {
         *             expectedModCount = modCount;
         *             Node<K,V>[] t = table;
         *             current = next = null;
         *             index = 0;
         *             if (t != null && size > 0) { // advance to first entry
         *                 do {} while (index < t.length && (next = t[index++]) == null);
         *             }
         *         }
         */
        // 5.0 next, current, index 都是 HashIterator 的属性
        // 5.1 Node<K,V>[] t = table; 先把 Node 数组 table 赋给 t
        // 5.2 current = next = null; 把 current 和 next 都置为 null
        // 5.3 index = 0; index 置为 0
        // 5.4 do {} while (index < t.length && (next = t[index++]) == null);
        // 这个 do{} while 循环会在 table 中 遍历 Node节点
        // 一旦 (next = t[index++]) == null 不成立时，就说明找到了一个 table 中的节点
        // 将这个节点赋给 next，并退出当前 do while循环
        // 此时 Iterator iterator = hashSet.iterator(); 就执行完了
        // 当前 iterator 的运行类型其实是 HashIterator，而 HashIterator 的 next 中存储着从 table 中遍历出来的一个 Node节点
        // 6. 执行 iterator.hasNext()
        /**
         * public final boolean hasNext() {
         *             return next != null;
         *         }
         */
        // 6.1 此时的 next 存储着一个 Node，所以并不为 null，返回 true
        // 7. 执行 iterator.next()，其实是去执行 HashIterator 的 nextNode()
        /**
         * final Node nextNode() {
         *             Node[] t;
         *             Node<K,V> e = next;
         *             if (modCount != expectedModCount)
         *                 throw new ConcurrentModificationException();
         *             if (e == null)
         *                 throw new NoSuchElementException();
         *             if ((next = (current = e).next) == null && (t = table) != null) {
         *                 do {} while (index < t.length && (next = t[index++]) == null);
         *             }
         *             return e;
         *         }
         */
        // 7.1 Node<K,V> e = next; 把当前存储着 Node 节点的 next 赋值给了 e
        // 7.2 (next = (current = e).next) == null
        // 判断当前节点的下一个节点是否为 null
        // a. 如果当前节点的下一个节点为 null
        // 就执行 do {} while (index < t.length && (next = t[index++]) == null);
        // 再 table 数组中 遍历，寻找 table 数组中的下一个 Node 并赋值给 next
        // b. 如果当前节点的下一个节点不为 null
        // 就将当前节点的下一个节点赋值给 next，并且此刻不会去 table 数组中遍历下一个 Node 节点
        // 7.3 将找到的节点 e 返回
        // 7.4 之后每次执行 iterator.next()，都像 a、b 那样去判断遍历，直到遍历完成
        Iterator iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
    }
}

以上がJava HashSet にトラバーサル要素を追加する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。