Javaプログラミング思考学習クラス(4) 第17章 コンテナ徹底解説

1 セットとストレージの順序

• Setに追加された要素は、オブジェクトが確実にSet的元素必须定义equals()方法以确保对象的唯一性。

• hashCode()只有这个类被置于HashSet或者LinkedHashSet中时才是必需的。但是对于良好的编程风格而言，你应该在覆盖equals()方法时，总是同时覆盖hashCode()方法。

• 如果一个对象被用于任何种类的排序容器中，例如SortedSet（TreeSet是其唯一实现），那么它必须实现Comparable接口。

• 注意，SortedSet的意思是“按对象的比较函数对元素排序”，而不是指“元素插入的次序”。插入顺序用LinkedHashSet来保存。

2 队列

• 队了并发应用，Queue在Java SE5中仅有的两个实现是LinkiedList和PriorityQueue，它们仅有排序行为的差异，性能上没有差异。

• 优先级队列PriorityQueue的排列顺序也是通过实现Comparable而进行控制的。

3 Map

  映射表（也称为关联数组Associative Array）。

3.1 性能

  HashMap使用了特殊的值，称作散列码（hash code），来取代对键的缓慢搜索。散列码是“相对唯一”的、用以代表对象的int值，它是通过将该对象的某些信息进行转换而生成的。
hashCode()是根类Object中的方法，因此所有对象都能产生散列码。

  对Map中使用的键的要求与对Set中的元素的要求一样：

• 任何键都必须具有一个equals()方法；

• 如果键被用于散列Map，那么它必须还具有恰当的hashCode()方法；

• 如果键被用于TreeMap，那么它必须实现Comparable。

4 散列与散列码

  HashMap使用equals()判断当前的键是否与表中存在的键相同。
  默认的Object.equals()只是比较对象的地址。如果要使用自己的类作为HashMap的键，必须同时重写hashCode()和equals()。
  正确的equals()方法必须满足下列5个条件：

• 自反性。

• 对称性。

• 传递性。

• 一致性。

• 对任何不是null的x，x.equals(null)一定返回false。

4.1 散列概念

  使用散列的目的在于：想要使用一个对象来查找另一个对象。
  Map的实现类使用散列是为了提高查询速度。

散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于查询速度，因此解决方案之一就是保持键的排序状态，然后使用Collections.binarySearch()

ユニークなセックス

です。

hashCode()🎜このクラスは、HashSet または LinkedHashSet に配置される場合にのみ必要です。ただし、適切なプログラミング スタイルとして、equals() メソッドをオーバーライドするときは、常に hashCode() メソッドをオーバーライドする必要があります。 🎜🎜🎜 SortedSet (TreeSet が唯一の実装) など、オブジェクトが何らかの種類の 🎜🎜ソートコンテナ🎜🎜 で使用されている場合、その場合、🎜Comparable🎜 インターフェイスを実装する必要があります。 🎜🎜🎜🎜SortedSet🎜 は、「要素が挿入される順序」ではなく、「オブジェクトの 🎜🎜 比較関数🎜🎜に従って要素を並べ替える」ことを意味することに注意してください。 🎜🎜広告掲載オーダー🎜🎜は 🎜LinkedHashSet🎜 で保存されます。 🎜

2 Queue

🎜🎜🎜 Java SE5 での Queue の実装は、🎜LinkedList🎜 と 🎜 の 2 つだけです。 PriorityQueue🎜 と異なり、🎜並べ替え動作🎜が異なるだけで、パフォーマンスには違いはありません。 🎜🎜🎜優先キュー PriorityQueue の順序も、🎜Comparable🎜 を実装することによって制御されます。 🎜

3 マップ

🎜 — 🎜🎜マップ テーブル🎜🎜 (🎜連想配列🎜🎜連想配列🎜とも呼ばれます)。 🎜

3.1 パフォーマンス

🎜 HashMap は、🎜🎜ハッシュ コード🎜🎜 (ハッシュ コード) と呼ばれる特別な値を使用して、キーの低速検索を置き換えます。ハッシュ コードは、オブジェクトを表すために使用される 🎜🎜 "比較的ユニークな" 🎜🎜 int 値であり、オブジェクトに関する 🎜 特定の情報を変換することによって生成されます。 🎜hashCode() はルートクラス Object のメソッドであるため、すべてのオブジェクトがハッシュ コードを生成できます。 🎜🎜 マップで使用されるキーの要件は、セット内の要素の要件と同じです。 🎜🎜🎜🎜どのキーにも 🎜equals()🎜 メソッドが必要です。 li>🎜 🎜キーがハッシュされたマップに使用される場合は、適切な 🎜hashCode()🎜 メソッドも必要です 🎜🎜🎜 キーが 🎜TreeMap code>🎜 の場合、🎜Comparable🎜 を実装する必要があります。 🎜

4 ハッシュとハッシュ コード

🎜 HashMap は 🎜equals()🎜 を使用して、現在のキーが存在するキーと同じかどうかを判断します表にある。 🎜 🎜デフォルトの Object.equals() はオブジェクトのアドレスを比較するだけです 🎜。 🎜独自のクラスを HashMap のキーとして使用したい場合🎜🎜、hashCode() と equals() の両方を同時にオーバーライドする必要があります🎜🎜。 🎜 正しい equals() メソッドは、次の 5 つの条件を満たしている必要があります: 🎜🎜🎜🎜再帰性。 🎜🎜🎜対称性。 🎜🎜🎜推移性。 🎜🎜🎜一貫性。 🎜🎜🎜 null ではない x の場合、x.equals(null) は false を返さなければなりません。 🎜

4.1 ハッシュの概念

🎜 ハッシュを使用する目的は次のとおりです: 🎜あるオブジェクトを使用して別のオブジェクトを見つけたい🎜。 🎜 Map の実装クラスはハッシュを使用して🎜🎜クエリ速度を向上🎜🎜します。 🎜

🎜🎜ハッシュの価値は速度です🎜: 🎜ハッシュによりクエリが高速になります🎜。ボトルネックは🎜🎜クエリ速度🎜🎜にあるため、解決策の 1 つは、キーを並べ替えたままにし、Collections.binarySearch() を使用してクエリを実行することです。 🎜🎜🎜🎜ハッシュ化はさらに一歩進んで、鍵をどこかに保存して🎜🎜すぐに見つけられるようにします。一連の要素を格納する最も高速なデータ構造は配列であるため、キー情報を表すために配列を使用します (キーそのものではなく、キー情報を意味していることに注意してください)。しかし、配列はその容量を調整できないため、問題が発生します。マップに不確実な数の値を保存したいのですが、キーの数が配列の容量によって制限されている場合はどうなるでしょうか。 🎜

答えは次のとおりです: 配列にはキー自体は格納されません。代わりに、キー オブジェクトから数値が生成され、配列の 添字 として使用されます。この数値はハッシュコードで、Objectで定義されたhashCode()hashCode()方法（在计算机科学的术语中称为散列函数）生成。

为解决数组容量固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突，即散列码不必是独一无二的。因此，数组多大就不重要了，任何键总能在数组中找到它的位置。

4.2 理解散列

  综上，散列就是将一个对象生成一个数字保存下来（作为数组的下标），然后在查找这个对象时直接找到这个数字就可以了，所以散列的目的是为了提高查找速度，而手段是将一个对象生成的数字与其关联并保存下来（通过数组，称为散列表）。这个生成的数字就是散列码。而生成这个散列码的方法称为散列函数（hashCode()）。

4.3 HashMap查询过程（快速原因）

  因此，HashMap中查询一个key的过程就是：

• 首先计算散列码

• 然后使用散列码查询数组（散列码作变数组下标）

• 如果没有冲突，即生成这个散列码的对象只有一个，则散列码对应的数组下标的位置就是这个要查找的元素

• 如果有冲突，则散列码对应的下标所在数组元素保存的是一个list，然后对list中的值使用equals()方法进行线性查询。

  因此，不是查询整个list，而是快速地跳到数组的某个位置，只对很少的元素进行比较。这便是HashMap会如此快速的原因。

4.4 简单散列Map的实现

• 散列表中的槽位（slot）通常称为桶位（bucket）

• 为使散列均匀，桶的数量通常使用质数（JDK5中是质数，JDK7中已经是2的整数次方了）。
  

  事实证明，质数实际上并不是散列桶的理想容量。近来，（通过广泛的测试）Java的散列函数都使用2的整数次方。对现代处理器来说，除法与求余数是最慢的操作。使用2的整数次方长度的散列表，可用掩码代替除法。因为get()是使用最多的操作，求余数的%操作是其开销最大的部分，而使用2的整数次方可以消除此开销（也可能对hashCode()有些影响）。

• get()方法按照与put()方法相同的方式计算在buckets数组中的索引，这很重要，因为这样可以保证两个方法可以计算出相同的位置。

package net.mrliuli.containers;

import java.util.*;public class SimpleHashMap<K, V> extends AbstractMap<K, V> {    // Choose a prime number for the hash table size, to achieve a uniform distribution:
    static final int SIZE = 997;    // You can&#39;t have a physical array of generics, but you can upcast to one:
    @SuppressWarnings("unchecked")
    LinkedList<MapEntry<K,V>>[] buckets = new LinkedList[SIZE];

    @Override    public V put(K key, V value){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null){
            buckets[index] = new LinkedList<MapEntry<K,V>>();
        }

        LinkedList<MapEntry<K,V>> bucket = buckets[index];
        MapEntry<K,V> pair = new MapEntry<K,V>(key, value);

        boolean found = false;
        V oldValue = null;
        ListIterator<MapEntry<K,V>> it = bucket.listIterator();        while(it.hasNext()){
            MapEntry<K,V> iPair = it.next();            if(iPair.equals(key)){
                oldValue = iPair.getValue();
                it.set(pair); // Replace old with new
                found = true;                break;
            }
        }        if(!found){
            buckets[index].add(pair);
        }        return oldValue;
    }

    @Override    public V get(Object key){        int index = Math.abs(key.hashCode()) % SIZE;        if(buckets[index] == null) return null;        for(MapEntry<K,V> iPair : buckets[index]){            if(iPair.getKey().equals(key)){                return iPair.getValue();
            }
        }        return null;
    }

    @Override    public Set<Map.Entry<K,V>> entrySet(){
        Set<Map.Entry<K,V>> set = new HashSet<Map.Entry<K, V>>();        for(LinkedList<MapEntry<K,V>> bucket : buckets){            if(bucket == null) continue;            for(MapEntry<K,V> mpair : bucket){                set.add(mpair);
            }
        }        return set;
    }    public static void main(String[] args){
        SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();        for(String s : "to be or not to be is a question".split(" ")){
            m.put(s, s);
            System.out.println(m);
        }
        System.out.println(m);
        System.out.println(m.get("be"));
        System.out.println(m.entrySet());
    }
}

4.5 覆盖hashCode()

  设计`hashCode()`时要考虑的因素：

• 最重要的因素：无论何时，对同一相对象调用hashCode()都应该生成同样的值。

• 此外，不应该使hashCode()依赖于具有唯一性的对象信息，尤其是使用this的值，这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的键，使之与put()中原始的键值对中的键相同。即应该使用对象内有意义的识别信息。也就是说，它必须基于对象的内容生成散列码。

• 但是，通过hashCode() equals()必须能够完全确定对象的身份。

• 因为在生成桶的下标前，hashCode()还需要进一步处理，所以散列码的生成范围并不重要，只要是int即可。

• 好的hashCode()应该产生分布均匀的散列码。

《Effective Java™ Programming Language Guide (Addison-Wesley, 2001)》为怎样写出一个像样的hashCode()给出了一个基本的指导：

1. 给int变量result赋予一个非零值常量，如17メソッド(コンピュータサイエンス用語では

   🎜と呼ばれます)によって決定され、クラスのハッシュ関数🎜🎜によってオーバーライドされる可能性があります)生成された。 🎜🎜固定配列容量の問題を解決するために、異なるキーが同じ添字を生成することができます。とはいえ、🎜衝突🎜が発生する可能性はあります。つまり、🎜🎜ハッシュコードは一意である必要はありません🎜🎜。したがって、配列の大きさに関係なく、どのキーも常に配列内でその場所を見つけます。 🎜

4.2 ハッシュについて理解する

🎜 まとめると、🎜🎜hash🎜🎜とは、オブジェクトから数値を生成して（配列の添字として）保存し、その後、その数値を直接検索することです。オブジェクトの数値を見つけるだけなので、ハッシュ化の🎜目的🎜は検索速度を向上させることであり、🎜手段🎜は、オブジェクトによって生成された数値をそれに関連付けて保存することです(🎜🎜ハッシュテーブルと呼ばれる配列を介して)。 🎜🎜）。この生成された番号が🎜🎜ハッシュコード🎜🎜です。このハッシュコードを生成するメソッドを🎜🎜ハッシュ関数🎜🎜 (hashCode()) と呼びます。 🎜

4.3 HashMap クエリ プロセス (簡単な理由)

🎜 したがって、HashMap 内の key をクエリするプロセスは次のようになります。 🎜

• 🎜最初にハッシュ コードを計算します🎜
• 🎜次に、ハッシュ コードを使用して配列をクエリします (ハッシュ コードは変数配列の添字として使用されます)🎜
• 🎜If 競合がない場合、つまり、このハッシュ コードを生成するオブジェクトが 1 つだけ存在する場合、ハッシュ コードに対応する配列添字の位置が検索対象の要素になります🎜
• 🎜競合がある場合、ハッシュ コードに対応する配列添字の位置は、ターゲットが配置されている配列要素を list に保存し、equals() メソッドを使用して、<code>list 内の値に対して線形クエリを実行します。 🎜

🎜 したがって、list 全体をクエリする代わりに、🎜配列内の特定の位置に素早くジャンプし🎜、比較するのは🎜少数の要素🎜だけです。これが、HashMap が非常に🎜速い🎜理由です。 🎜

4.4 単純なハッシュ マップの実装

• 🎜ハッシュ テーブル内の 🎜slot 🎜 (スロット) は、通常 🎜バケット 🎜(バケット)🎜
• 🎜ハッシュを偶数にするために、バケットの数は通常🎜素数🎜を使用します (🎜JDK5では素数ですが、JDK7ではすでに2の整数乗です🎜) 。
  🎜

  素数は実際にはハッシュ バケットの理想的な容量ではないことが判明しました。最近、Java のハッシュ関数は (広範なテストを通じて) 🎜2 の 🎜 乗を使用しています。除算と剰余は、最新のプロセッサでは最も遅い演算です。長さ 2 の整数乗のハッシュ テーブルを使用すると、除算を 🎜🎜mask🎜🎜 で置き換えることができます。 get() は最も一般的に使用される操作であるため、% 剰余を求める操作は最もコストがかかる部分であり、2 の整数乗を使用すると、このオーバーヘッドを排除できます (hashCode() にも多少の影響を与える可能性があります)。

• 🎜get() メソッドは put() メソッドと同じ方法でバケット配列のインデックスを計算します。これは、両方のメソッドが同じ場所を確実に計算できるようにするため重要です。 🎜。 🎜

package net.mrliuli.containers;

import java.util.*;public class Synchronization {    public static void main(String[] args){
        Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());        Set<String> s = Collections.synchronizedSet(new HashSet<String>());        Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
        Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
        Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
    }
}

4.5 hashCode() のオーバーライド

🎜 `hashCode()` を設計する際に考慮すべき要素: 🎜

• 🎜最も重要な要素: 🎜同じフェーズオブジェクトで hashCode() を呼び出すと、🎜🎜常に同じ値 🎜🎜 が生成される必要があります。 🎜
• 🎜さらに、hashCode() は、一意のオブジェクト情報に依存するように作成すべきではありません。特に this の値を使用すると、非常に悪い hashCode() しか生成されない可能性があります。これは、put() の元のキーと値のペアのキーと同じ新しいキーを生成できないためです。つまり、オブジェクト内の 🎜🎜意味のある 🎜🎜 識別情報を使用する必要があります。つまり、オブジェクトの🎜内容🎜に基づいてハッシュ コードを生成する必要があります。 🎜
• 🎜 ただし、オブジェクトの ID は hashCode()equals() を通じて完全に決定する必要があります。 🎜
• 🎜 hashCode() はバケットの添え字を生成する前にさらに処理が必要なため、ハッシュ コードの生成範囲は int であれば問題ありません。 🎜
• 🎜 適切な hashCode() は、均等に分散されたハッシュ コードを生成する必要があります。 🎜

🎜「Effective Java™ Programming Language Guide (Addison-Wesley、2001)」には、適切な hashCode() の書き方に関する基本的なガイドが記載されています: 🎜

1. 🎜ゼロ以外の値の定数を int 変数 result に代入します (17 など)。 🎜

2. 为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c：

域类型	计算
boolean	c=(f?0:1)
byte、char、short或int	c=(int)f
long	c=(int)(f^(f>>>32))
float	c=Float.floatToIntBits(f);
double	long l = Double.doubleToLongBits(f);
Object,其equals()调用这个域的equals()	c=f.hashCode()
数组	对每个元素应用上述规则

3. 合并计算散列码：result = 37 * result + c;
4. 返回result。
5. 检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。

5 选择不同接口的实现

5.1 微基准测试的危险（Microbenchmarking dangers）

已证明0.0是包含在Math.random()的输出中的，按照数学术语，即其范围是[0,1)。

5.2 HashMap的性能因子

  HashMap中的一些术语：

• 容量（Capacity）：表中的桶位数（The number of buckets in the table）。

• 初始容量（Initial capacity）：表在创建时所拥有的桶位数。HashMap和HashSet都具有允许你指定初始容量的构造器。

• 尺寸（Size）：表中当前存储的项数。

• 负载因子（Loadfactor）：尺寸/容量。空表的负载因子是0，而半满表的负载因子是0.5，依此类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是最理想的（但是会减慢使用迭代器进行遍历的过程）。HashMap和HashSet都具有允许你指定负载因子的构造器，表示当负载情况达到该负载的水平时，容器将自动增加其容量（桶位数），实现方式是使容量大致加倍，并重新将现有对象分布到新的桶位集中（这被称为再散列）。

HashMap使用的默认负载因子是0.75（只有当表达到四分之三满时，才进行再散列），这个因子在时间和空间代价之间达到了平衡。更高的负载因子可以降低表所需的空间，但会增加查找代价，这很重要，因为查找是我们在大多数时间里所做的操作（包括get()和put()）。

6 Collection或Map的同步控制

  Collections类有办法能够自动同步整个容器。其语法与“不可修改的”方法相似：

package net.mrliuli.containers;

import java.util.*;public class Synchronization {    public static void main(String[] args){
        Collection<String> c = Collections.synchronizedCollection(new ArrayList<String>());
        List<String> list = Collections.synchronizedList(new ArrayList<String>());        Set<String> s = Collections.synchronizedSet(new HashSet<String>());        Set<String> ss = Collections.synchronizedSortedSet(new TreeSet<String>());
        Map<String, String> m = Collections.synchronizedMap(new HashMap<String, String>());
        Map<String, String> sm = Collections.synchronizedSortedMap(new TreeMap<String, String>());
    }
}

6.1 快速报错（fail-fast）

  Java容器有一种保护机制能够防止多个进行同时修改同一个容器的内容。Java容器类类库采用快速报错（fail-fast）机制。它会探查容器上的任何除了你的进程所进行的操作以外的所有变化，一旦它发现其他进程修改了容器，就会立刻抛出ConcurrentModificationException异常。这就是“快速报错”的意思——即，不是使用复杂的算法在事后来检查问题。

package net.mrliuli.containers;
import java.util.*;public class FailFast {    public static void main(String[] args){
        Collection<String> c = new ArrayList<>();
        Iterator<String> it = c.iterator();
        c.add("An Object");        try{
            String s = it.next();
        }catch(ConcurrentModificationException e){
            System.out.println(e);
        }
    }
}

相关文章：

Java编程思想学习课时（三）第15章-泛型

Java编程思想学习课时（五）第18章-Java IO系统

以上がJavaプログラミング思考学習クラス(4) 第17章 コンテナ徹底解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。