Javaのデータ構造に関するクラス実装原理,例えばLinkedList,ArrayList,HashMap,TreeMap

5634 ワード

HashMapは秩序があるのではないでしょうか.
いいえ
hashmapのhashcode()生成規則は、次のとおりです.
equals()とhashcode()を理解する必要があります.まず、equalsと==の違いを理解します.
1、基本データ型比較==とEqualsは両方の値が等しいかどうかを比較します.等しくtrueでなければfalseです.2、参照対象比較==とEqualsは、比較スタックメモリのアドレスが等しいかどうかを示します.等しくtrueでなければfalseです.3、equals()はいくつかの注意点を提供します:1、stringは特殊な参照タイプです.2つの文字列の比較では、==とEqualsの両方が文字列が同じかどうかにかかわらず、2、2つのstringオブジェクトを作成すると、メモリのアドレスが異なり、同じ値を割り当てることができます.文字列の内容は同じです.引用アドレスは必ずしも同じではないが、逆に肯定的である.3、基本データ型比較(stringを除く)==とEqualsの両方が比較値である.equals()は、通常、オブジェクトが自分で書き換えを定義する必要があります.equalsと==具体的には、以下を参照してください.http://blog.csdn.net/tcytcy123/article/details/50836323 次はequals()のObjectでの実装です
 public static boolean equals(Object a, Object b) {
        return (a == b) || (a != null && a.equals(b));
    }

これはequals()のHashMapでの実現である
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry,?> e = (Map.Entry,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }

2つのケースが等しいと判断します.1つは呼び出しの同じオブジェクト、2つはkey 1です.あるランタイム期間において、オブジェクトの(フィールドの)変化がequalsメソッドの決定結果に影響しない限り、この期間においてhashCodeが何回呼び出されても、同じハッシュコードを返さなければなりません.
第2:equals呼び出しによりtrueを返す2つのオブジェクトのhashCodeは必ず同じである.
第三に、equaslによってfalseを返す2つのオブジェクトのハッシュコードは、異なる必要はありません.すなわち、hashCodeメソッドの戻り値は、同じ場合を許可します.
要約すると、等価な(equalsを呼び出してtrueを返す)オブジェクトは、同じハッシュコードを生成する必要があります.等価でないオブジェクトは、生成されたハッシュコードが異なることを要求しない.では、どのmapが秩序化されていますか?
TreeMapとLinkedHashMap.
TreeMapとLinkedHashMapはどのようにしてその順序を保証しますか?
hashMapストレージ構造には、key,value,next linkedHashMapが含まれています.http://www.cnblogs.com/whgk/p/6169622.html
LinkedHashMapは、Comparatorインタフェースを実装し、comparare()を書き換える方法で比較します.たとえば、次のようになります.
public static void main(String[] args) {
        TreeSet ts = new TreeSet(new PersonComparator());

        ts.add(new Person(1, "Json", 20));
        ts.add(new Person(2, "Peter", 22));
        ts.add(new Person(1, "Divid", 25));
        ts.add(new Person(3, "Aglia", 27));
        ts.add(new Person(3, "Alex", 23));
        ts.add(new Person(3, "Molic", 22));

        Map map = new HashMap();

        for (Iterator iterator = ts.iterator(); iterator.hasNext();) {
            Person p = (Person) iterator.next();
            map.put(p.getName(), p);
            System.out.println(p.getName() + "|" + p.getLevel() + "|"
                    + p.getAge());
        }
    }
}

class PersonComparator implements Comparator<Person> {

    @Override
    public int compare(Person p1, Person p2) {
        if (p1.getLevel() == p2.getLevel()) {
            return p1.getAge() - p2.getAge();
        }

        return p1.getLevel() - p2.getLevel();
    }

まとめ:まず2つともmapなので、keyで値を取るのは間違いなく違いありません.違いは、Iteratorで遍歴したときにLinkedHashMapが記録した挿入順を保存し、先に挿入した先遍歴からTreeMapまではデフォルトでは昇順で並べ替えられていますが、並べ替えの比較器を指定することもできます.遍歴するときは昇順に遍歴する.例えば、aはLinkedHashMap、bはTreeMapである.a.put(“2”,”ab”); a.put(“1”,”bc”); b.put(“2”,”ab”); b.put(“1”,”bc”); ではaを巡るときは、keyが2であることを先に巡ります.2が先に入るからです.bを遍歴するときは、まず「1」まで遍歴します.順序は1から2ですから.