HashSet、LinkdHashSet、TreeSetおよびComprableとCompratorについて
8024 ワード
一、HashSetとLinkdHashSetの基礎
1.Setの要素が下に格納されている位置は無秩序である。2.Setの要素は重複してはいけない。
6.Linked HashSetはHashSetのサブクラスであり、hashCodeの値に基づいて要素の格納位置を決定するとともに、リンクを使用して要素の前後方向の索引を作成し、要素の語順を維持します。これにより、要素は挿入順に保存されます。7.そのため、Linked HashSetの挿入性能はHashSetよりやや低いが、Setのすべての要素に反復的にアクセスする時には良い性能がある。
二、HashSetの底辺実現について hash Setの最下層にはhashMapが使用されており、ユーザがHashSetのインスタンスを作成すると、HashMapタイプのメンバー変数が作成される。HashSetの例の動作は、実はすべてHashMapメンバー変数に対して動作しています。下記のソースコードの通りです。
1.Linked HashSetはHashSetのサブクラスとして、新しい方法を追加していません。4つの構成方法のみが提供され、内部は親クラスHashSetのbootlean識別子を呼び出す構成方法である。
四、TreeSetについて
1.TreeSetに記憶されている要素は自動的にサイズ順に並べられます。String、包装類などはデフォルトでは小さい時から大きい順です。文字列の昇順)2.TreeSetに保存されている要素は自動的にサイズを比較しますので、TreeSetに保存されている要素は同じ種類でなければなりません。また、カスタムクラスは、comprableインターフェースを実現する必要があります。またはTreeSet(Comprator comprator)構造を使用して、保存されているタイプの外部コンパレータに入る必要があります。そうでないと、TreeSetにこのクラスのオブジェクトを追加すると、Class CastException(タイプ変換異常)を報告します。
3.カスタムクラスでcomprableインターフェースのcompreTo()を書き換える場合は、カスタムクラスのある属性に従って並べ替えるように指定できます。
1.TreeSet内部にNavigableMapタイプのインターフェース変数が定義されています。ビルダーを呼び出してTreeSetを生成する場合は、TreeMapオブジェクトを実装し、NavigableMapインターフェース変数に戻します。そのため、TreeSetの最下階ではTreeMapを使ってデータを記憶していますが、HashSetの最下階ではHashMapを使っています。
Comprableは、Comprableインターフェースを実現することによって内部にオブジェクトは自分との比較をサポートしていませんが、2つのオブジェクトを比較する必要がある場合は、Compratorインターフェースを実現する外部コンパレータを構築することができます。たとえば、このクラスのオブジェクトをSetに保存する必要がある場合。 オブジェクトはComprableインターフェースを実現しましたが、開発者は Comprableインターフェースを実現する方式はCompratorインターフェースの結合性を実現するより強いです。比較アルゴリズムを修正するなら、Comprableインターフェースの実現クラスを修正しますが、Compratorを実現するクラスは外部で比較します。実現類に対してはいかなる修正も必要ありません。 は、具体的な場面で最適なコンパレータを選択する。
1.Setの要素が下に格納されている位置は無秩序である。2.Setの要素は重複してはいけない。
String str1 = new String("abc");
String str2 = new String("abc");
// 。 new , , 。 str1 str2
// String Object hashcode() , hash , ,hash 。
3.したがって、HashSetに預け入れを要求するカスタムオブジェクトは、hashCode()とequal()を書き換える方法であり、Setの要素の重複性を保証する。HashSetにオブジェクトを追加すると、まずオブジェクトのhashcode()メソッドを呼び出し、オブジェクトのshsh値を計算します。このhash値は、オブジェクトのHashSetの位置を決定します。この位置以前にオブジェクトがなかったら、オブジェクトはこの位置に直接保存されます。この位置にオブジェクトがある場合は、equal()方法で2つのオブジェクトが同じかどうかを比較します。同じ場合、後のオブジェクトは追加できません。hashCodeの比較を保証したほうがいいと要求された結果はequalと比較した結果と一致します)class Person{
int age;
String name;
// hashCode ( IDE )
public int hashCode(){
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
}
4.ハッシュアルゴリズムを使用して、比較の複雑さを低減し、ハッシュアルゴリズムを使用しないと、HashSetに要素を格納する度に、HashSetに既存のすべての要素と比較し、複雑すぎる。5.HashSetはhashアルゴリズムでセット内の要素を記憶するので、アクセスと検索の性能が優れています。ただし、要素の並び順は保証できません。6.Linked HashSetはHashSetのサブクラスであり、hashCodeの値に基づいて要素の格納位置を決定するとともに、リンクを使用して要素の前後方向の索引を作成し、要素の語順を維持します。これにより、要素は挿入順に保存されます。7.そのため、Linked HashSetの挿入性能はHashSetよりやや低いが、Setのすべての要素に反復的にアクセスする時には良い性能がある。
二、HashSetの底辺実現について
private transient HashMap map;//HashMap
private static final Object PRESENT = new Object();//map value Object
// map
public HashSet() {
map = new HashMap<>();
}
// HashSet map
//map.put() key value, null, map k-v ,set.add , true。
// , value PRESENT, set.add , false, map k-v 。
//( map key-value , k-v )
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
// ,HashSet , map keySet 。HashSet map key 。
public Iterator iterator() {
return map.keySet().iterator();
}
// HashSet API
三、Linked HashSetの底辺実現について1.Linked HashSetはHashSetのサブクラスとして、新しい方法を追加していません。4つの構成方法のみが提供され、内部は親クラスHashSetのbootlean識別子を呼び出す構成方法である。
//LinkedHashSet 。
public LinkedHashSet() {
super(16, .75f, true);
}
//hashSet , LinkedHashMap 。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
2.したがって、Linked Hash Setの要素は、その内部に記憶されているLinked HashMapの実例的な属性であることがわかる。四、TreeSetについて
1.TreeSetに記憶されている要素は自動的にサイズ順に並べられます。String、包装類などはデフォルトでは小さい時から大きい順です。文字列の昇順)2.TreeSetに保存されている要素は自動的にサイズを比較しますので、TreeSetに保存されている要素は同じ種類でなければなりません。また、カスタムクラスは、comprableインターフェースを実現する必要があります。またはTreeSet(Comprator comprator)構造を使用して、保存されているタイプの外部コンパレータに入る必要があります。そうでないと、TreeSetにこのクラスのオブジェクトを追加すると、Class CastException(タイプ変換異常)を報告します。
3.カスタムクラスでcomprableインターフェースのcompreTo()を書き換える場合は、カスタムクラスのある属性に従って並べ替えるように指定できます。
public class People implements Comparable<People>{
private String name;
private int age;
// compareTo() , , 。
// , compareTo() , compareTo() hashCode() equal() 。
@Override
public int compareTo(People o) {
int result = this.name.compareTo(o.name);// name
return result;
}
五、TreeSetの底辺実現について1.TreeSet内部にNavigableMapタイプのインターフェース変数が定義されています。ビルダーを呼び出してTreeSetを生成する場合は、TreeMapオブジェクトを実装し、NavigableMapインターフェース変数に戻します。そのため、TreeSetの最下階ではTreeMapを使ってデータを記憶していますが、HashSetの最下階ではHashMapを使っています。
private transient NavigableMap m;// NavigableMap
//TreeSet , TreeMap NavigableMap
TreeSet(NavigableMap m) {
this.m = m;
}
//
public TreeSet() {
this(new TreeMap());
}
// ,TreeSet , API
public TreeSet(Comparator super E> comparator) {
this(new TreeMap<>(comparator));
}
六、ComprableとCompratorComprableは、Comprableインターフェースを実現することによって内部に
compareTo()
方法を書き換えることによって、このクラスの2つのオブジェクトをどのように比較するかを定義する内部比較器と考えられてもよい。Compratorは、汎用インターフェースComprator<T>を実現することによって、2つのTクラスを比較する対象を定義する外部比較器と考えられてもよい。Comprator<T>インターフェースを実現するクラスは、T類の専門的なコンパレータ類であり、T類の外部コンパレータであると考えられます。compare(T o1, T o2)
方法における比較方式は自分が望むものではないと考えています。Compratorインターフェースを実現する外部比較器を構築することができます。