Java面接問題のHashSetの実現原理は?
HashSetの実現原理は?
まず、Setの実装であることを知る必要があります.そのため、重複する要素がないことを保証します.一方Setで最も重要な操作は検索です.そして通常私たちは
高速検索に特化しているため、HashSetが実装されます.
HashSetはハッシュ関数を使用しており,その中の要素も無秩序である.中にはnullを許可する要素があります.
まず、実現原理についてまとめます.
(1)HashMapに基づいて実装され、デフォルトのコンストラクタは、初期容量16、負荷係数0.75のHashMapを構築する.HashMapオブジェクトをカプセル化してすべての集合要素を格納し、HashSetに格納されたすべての集合要素は実際にHashMapのkeyによって保存され、HashMapのvalueは静的ObjectであるPRESENTを格納します.
(2)あるクラスのオブジェクトをHashMapのkeyとしようとしたり,このクラスのオブジェクトをHashSetに保存しようとしたりすると,クラスのequals(Object obj)メソッドとhashCode()メソッドを書き換えることが重要であり,この2つのメソッドの戻り値は一致しなければならない:クラスの2つのhashCode()戻り値が同じであればequals()メソッド比較もtrueを返すべきです.一般に、hashCode()の戻り値の計算に関与するすべてのキー属性は、equals()比較の基準として使用されるべきである.
(3)HashSetの他の動作はHashMapに基づく.
ここでは、HashSetの実現原理について説明します.
これはHashMapに基づいて実現され、HashSetの下位層はHashMapを使用してすべての要素を保存するため、HashSetの実現は比較的簡単で、関連するHashSetの操作は、基本的に下位層HashMapの関連方法を直接呼び出して完成し、HashSetのソースコードは以下の通りである.
ありがとうございます.批判してください.
まず、Setの実装であることを知る必要があります.そのため、重複する要素がないことを保証します.一方Setで最も重要な操作は検索です.そして通常私たちは
高速検索に特化しているため、HashSetが実装されます.
HashSetはハッシュ関数を使用しており,その中の要素も無秩序である.中にはnullを許可する要素があります.
まず、実現原理についてまとめます.
(1)HashMapに基づいて実装され、デフォルトのコンストラクタは、初期容量16、負荷係数0.75のHashMapを構築する.HashMapオブジェクトをカプセル化してすべての集合要素を格納し、HashSetに格納されたすべての集合要素は実際にHashMapのkeyによって保存され、HashMapのvalueは静的ObjectであるPRESENTを格納します.
(2)あるクラスのオブジェクトをHashMapのkeyとしようとしたり,このクラスのオブジェクトをHashSetに保存しようとしたりすると,クラスのequals(Object obj)メソッドとhashCode()メソッドを書き換えることが重要であり,この2つのメソッドの戻り値は一致しなければならない:クラスの2つのhashCode()戻り値が同じであればequals()メソッド比較もtrueを返すべきです.一般に、hashCode()の戻り値の計算に関与するすべてのキー属性は、equals()比較の基準として使用されるべきである.
(3)HashSetの他の動作はHashMapに基づく.
ここでは、HashSetの実現原理について説明します.
これはHashMapに基づいて実現され、HashSetの下位層はHashMapを使用してすべての要素を保存するため、HashSetの実現は比較的簡単で、関連するHashSetの操作は、基本的に下位層HashMapの関連方法を直接呼び出して完成し、HashSetのソースコードは以下の通りである.
import java.util.AbstractSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Set;
import javax.swing.text.html.HTMLDocument.Iterator;
public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
// HashMap HashSet 。
private transient HashMap map;
// Object HashMap value, static final。
private static final Object PRESENT = new Object();
// , HashSet。
//
// HashMap, 16 0.75。
public HashSet() {
map = new HashMap();
}
// collection set。
//
// 0.75
// collection HashMap。
// @param c set collection。
public HashSet(Collection extends E> c) {
map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// initialCapacity loadFactor HashSet。
//
// HashMap。
// @param initialCapacity 。
// @param loadFactor 。
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap(initialCapacity, loadFactor);
}
// initialCapacity HashSet。
//
// loadFactor 0.75 HashMap。
// @param initialCapacity 。
public HashSet(int initialCapacity) {
map = new HashMap(initialCapacity);
}
// initialCapacity loadFactor 。
// , , LinkedHashSet 。
//
// LinkedHashMap 。
// @param initialCapacity 。
// @param loadFactor 。
// @param dummy 。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap(initialCapacity, loadFactor);
}
// set 。 。
//
// HashMap keySet key。
// HashSet , HashMap key ,
// value static final Object 。
// @return set Iterator。
public Iterator iterator() {
return map.keySet().iterator();
}
// set (set )。
//
// HashMap size() Entry , Set 。
// @return set (set )。
public int size() {
return map.size();
}
// set , true。
//
// HashMap isEmpty() HashSet 。
// @return set , true。
public boolean isEmpty() {
return map.isEmpty();
}
// set , true。
// , set (o==null ? e==null : o.equals(e))
// e , true。
//
// HashMap containsKey key。
// @param o set 。
// @return set , true。
public boolean contains(Object o) {
return map.containsKey(o);
}
// set , 。
// , set (e==null ? e2==null : e.equals(e2))
// e2, set e。
// set , set false。
//
// key HashMap。
// HashMap put() key-value , HashMap Entry key
// Entry key (hashCode() , equals true),
// Entry value Entry value, key ,
// HashSet , HashMap ,
// , Set 。
// @param e set 。
// @return set , true。
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// set , 。
// , set (o==null ? e==null : o.equals(e)) e,
// 。 set , true
// ( : set , true)。( , set )。
//
// HashMap remove Entry。
// @param o set 。
// @return set , true。
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
// set 。 , set 。
//
// HashMap clear Entry 。
public void clear() {
map.clear();
}
// HashSet : 。
// HashMap clone() , HashMap , HashSet 。
public Object clone() {
try {
HashSet newSet = (HashSet) super.clone();
newSet.map = (HashMap) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
ありがとうございます.批判してください.