HashSetとHashMap、Hashtable

10038 ワード

(最近先生が私たちにjavaでLRUアルゴリズムを実現するように言って、二重チェーンテーブルでやる、LinkHashMapでやるということを知りましたが、自分はjavaのいくつかの大きな集合フレームワークに慣れていないので、勉強の過程でHashMapとHashSetを知って、簡単なメモを取りましょう)
HashMap
HashMapは秩序化された集合であり、keyとvalueを含む属性値のペアを持つ集合である.キーワードキーは重複しない唯一のもので、クエリーが速くなります.
 
HashMapの例には、初期容量とロードファクタの2つのパラメータがあります.容量はハッシュ・テーブルのバケツの数であり、初期容量はハッシュ・テーブルの作成時の容量にすぎない.ロードファクタは、ハッシュ・テーブルが容量が自動的に増加する前に、マルチフルに達することができるスケールです.ハッシュ・テーブルのエントリ数がロード・ファクタと現在の容量の積を超えた場合、rehashメソッドを呼び出すことで容量を2倍にします.  通常、デフォルトのロードファクタ(.75)は、時間および空間コストのトレードオフを求めます.ロードファクタが高すぎると、スペースオーバーヘッドが削減されますが、クエリーコストも増加します(多くのHashMapクラスの操作では、getやput操作を含めて、この点が反映されています).初期容量を設定するときは、rehash操作回数を最小限に抑えるために、マッピングに必要なエントリ数とそのロード係数を考慮する必要があります.初期容量が最大エントリ数をロードファクタで割った場合、rehash操作は発生しません.
HashSet
 
HashSet(ハッシュリスト)はHashMapのvalueを削除するようなもので、はっきり言ってkeyが1つしかないHashMapの集合です.Setインタフェースが実装され、要素に重複値が表示されないことを意味します.HashSetにはadd,remove,contains,sizeメソッドがあり,get()メソッドはないがiterator()で実現でき,反復に要する時間はHashSetインスタンスのサイズ(要素の数)に比例する.HashSetについては、HashMapに基づいて実装される.
次はHashSetのソースコードです.
public class HashSet<E> extends AbstractSet<E> 
     implements Set<E>, Cloneable, java.io.Serializable 
 { 
     //    HashMap   key    HashSet      
     private transient HashMap<E,Object> map; 
     //         Object      HashMap   value 
     private static final Object PRESENT = new Object(); 
     ... 
     //     HashSet,         HashMap 
     public HashSet() 
     { 
         map = new HashMap<E,Object>(); 
     } 
     //      initialCapacity、loadFactor    HashSet 
     //              HashMap 
     public HashSet(int initialCapacity, float loadFactor) 
     { 
         map = new HashMap<E,Object>(initialCapacity, loadFactor); 
     } 
     public HashSet(int initialCapacity) 
     { 
         map = new HashMap<E,Object>(initialCapacity); 
     } 
     HashSet(int initialCapacity, float loadFactor, boolean dummy) 
     { 
         map = new LinkedHashMap<E,Object>(initialCapacity 
             , loadFactor); 
     } 
     //    map   keySet        key 
     public Iterator<E> iterator() 
     { 
         return map.keySet().iterator(); 
     } 
     //    HashMap   size()      Entry    ,     Set       
     public int size() 
     { 
         return map.size(); 
     } 
     //    HashMap   isEmpty()     HashSet     ,
     //   HashMap    ,    HashSet    
     public boolean isEmpty() 
     { 
         return map.isEmpty(); 
     } 
     //    HashMap   containsKey          key 
     //HashSet           HashMap   key     
     public boolean contains(Object o) 
     { 
         return map.containsKey(o); 
     } 
     //         HashSet  ,          key    HashMap 
     public boolean add(E e) 
     { 
         return map.put(e, PRESENT) == null; 
     } 
     //    HashMap   remove        Entry,      HashSet       
     public boolean remove(Object o) 
     { 
         return map.remove(o)==PRESENT; 
     } 
     //    Map   clear        Entry,      HashSet      
     public void clear() 
     { 
         map.clear(); 
     } 
     ... 
 }

Hashtable
他にもHashtableがありますが、ネット上ではこの3つの違いは面接でよく遭遇すると言われていますが、ほほほ、今までHashtableに遭遇することは少ないようですが、HashMapは新しいフレームワークの中でHashTableの代わりに使われるクラスだからですか?HashtableはDictionaryのサブクラスであり、メソッドは同期化され、null値は許可されない(keyもvalueも不可)、HashMaはMapインタフェースの実装クラスであり、メソッドは非同期でnull値の出現を許可する.
いくつかの簡単なテストプログラムは、取り外して、理解しやすいです.
public static void main(String[] args) {
  Hashtable<Integer, String> table = new Hashtable<Integer, String>();
  table.put(1, "1");
  //table.put(2, null);   //Hashtable    null   null     
  
for(int i=0;i<table.size();i++){
   System.out.println(table.get(1));
  }
  System.out.println("#############");
  HashMap<Integer, String> map = new HashMap<Integer, String>();
  map.put(1, "2");
  map.put(2, "3");
  map.put(null,null);      //HashMap   null , key     null,         ,
  for(int i=0;i<map.size();i++){
   System.out.println(map.get(1));
  }
  
  System.out.println("#############");
//HashSet               get()    
  HashSet<Integer> s = new HashSet<Integer>();
  s.add(Integer.valueOf(1));
  s.add(Integer.valueOf(1));
  for(Integer i:s){
   System.out.println(i);
  }
 }

(コードソースはhttp://blog.sina.com.cn/s/blog_4586764e0100ivup.html)
Googleはこの3つの違いを検索して、2つのトップ記事を見て、後でまた帰って見なければならないと思います.
http://blog.csdn.net/zwjlpeng/article/details/9746425
http://www.cnblogs.com/dyllove98/p/3236988.html