HashMap,Hashtable,HashSetの3種類のhash集合の違い

7430 ワード

転載:http://www.cnblogs.com/lzrabbit/p/3721067.html#h1
HashMapとHashtableの違い
両者の最も主要な違いは、Hashtableがスレッドセキュリティであるのに対し、HashMapは非スレッドセキュリティHashtableの実現方法にsynchronizedキーワードを追加してスレッドの同期を確保しているため、HashMapの性能は比較的高く、私たちが普段使用する際に特にHashMapを使用する必要がなければ、マルチスレッド環境でHashMapを使用するにはCollectionsを使用する必要がある.SynchronizedMap()メソッドは、スレッドセキュリティの集合(Collections.synchronizedMap()実装原理は、CollectionsがMapインタフェースを実装するSynchronizedMapの内部クラスを定義することである.このクラスは、メソッドを呼び出すときにsynchronizedを使用してスレッドの同ステップを保証する.もちろん、実際に動作するのは、私たちが入力したHashMapのインスタンスであり、簡単にはCollectionsである.synchronizedMap()メソッドでは、HashMapの操作時にsynchronizedを自動的に追加してスレッド同期を実現します.他のCollectionsと同様です.synchronizedXXメソッドも同様の原理です)HashMapはnullをkeyとして使用することができるが、Hashtableはnullをkeyとして使用することを許さない.HashMapはnull値をkeyとしてサポートするが、うっかり使用してしまったため、問題が発生すると、HashMapがnullをkeyとしている場合、常にtable配列の最初のノードにが格納される
HashMapはMapインタフェースの実装であり、HashTableはMapインタフェースとDictionary抽象クラスを実装する.
HashMapの初期容量は16で、Hashtableの初期容量は11で、両者の充填因子はデフォルトで0.75 HashMap拡張時が現在の容量の倍増である:capacity*2、Hashtable拡張時が容量の倍増+1である:capacity*2+1両者がhashを計算する方法は異なるHashtable計算hashはkeyのhashcodeを直接用いてtable配列の長さを直接型取りする
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap計算hashはkeyのhashcodeに対して二次hashを行い,より良いハッシュ値を求め,table配列長をタッチした.
static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 static int indexFor(int h, int length) {
        return h & (length-1);
    }


 
HashMapとHashtableの下位実装はいずれも配列+チェーンテーブル構造実装である.
HashSetとHashMap、Hashtableの違い
HashMapとHashtableのほかに、hash集合HashSetがあります.違いはHashSetがkey value構造ではなく、重複しない要素を格納するだけで、簡略化版のHashMapに相当し、HashMapのkeyを含むだけです.
ソースコードを確認することで、HashSetの内部はHashMapで実現されていますが、HashSetの中のHashMapのすべてのvalueは同じObjectなので、HashSetも非スレッドで安全です.HashSetとHashtableの違いについては、HashSetは簡略化されたHashMapなので、以下はHashSetのいくつかの主な方法の実現です.
  private transient HashMap map;
private static final Object PRESENT = new Object();
public HashSet() { map = new HashMap(); } public boolean contains(Object o) { return map.containsKey(o); } public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); }