java - HashSet の基礎となる DataStructure

Question

ArrayList の基礎となる dataStructure は配列、LinkedList の場合は Link オブジェクト、HashMap または HashTable の場合は LinkedList または Tree の配列、HashSet で使用されるデータ構造は何か

Answer 1

Javadocによると、HashSet のバッキング データ構造は HashMap です。

JDK 1.6 コードはこれを検証します。

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

Answer 2

ハッシュの単純な考え方は、次のように計算された位置インデックスで要素を配列に格納することです。

• 要素のデータを処理して整数値を生成することにより、要素の element_hash_code を取得します (要素を「ハッシュする」という考えは、大まかに「それをすりつぶす」ことを意味します)
• 単純な mod 操作を使用して、配列の範囲にマップします

したがって、これらは配列またはリンクされたリストで実行できます。

JavaHashSetでは、HashMap内部的に

ソースコードから

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

Answer 3

HashSet は、データを格納するために HashMap を内部的に使用します。そして、HashMap は Entry オブジェクトの配列だと思います。

HashMap の内部構造を理解するための関連記事:

https://stackoverflow.com/questions/11596549/how-does-javas-hashmap-work-internally

Answer 4

HashMap および HashSet (HashMap に基づく) の基礎となるデータ構造は、ハッシュ テーブルhttp://en.wikipedia.org/wiki/Hash_tableです。HashMap ソース コードでは、エントリの配列のように見えます

Entry<K,V>[] table;

... 

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
...