集合とHashMapについて

プログラミングを最初に接触したときに初めて使用したデータ構造は配列であるべきで、配列は連続したメモリの総称であり、分解して見ると1つの変数である.配列のメモリは静的に割り当てられます.つまり、1つの配列にメモリを開いた後、サイズを変更することはできません.実は配列は変数(データ)と数字(インデックス)の関連で、連続するメモリは配列の検索を迅速に決定するが、削除、追加などの操作には非常に面倒である.その上でjavaの中の容器類:Map、Collection、Iteratorなどの接続口に触れ、javaのコア結合フレームワーク:Set、List、Mapについて、簡単にまとめると以下の通りである.
ListLinkedList:シーケンスアクセスを最適化し、キュー、双方向キュー、スタックの機能ArrayKList:配列で実現されたListを提供することができる.迅速なランダムアクセスが可能ですが、リストの真ん中に要素を挿入・削除するときは比較的遅いSetLinkedHashSetは内部でハッシュを使用してクエリー速度を向上させますが、チェーンテーブルで要素の挿入順序を保存するHashSetのように見えます.クエリー速度を最適化するために設計されたSetは、データ構造が「迅速な検索のために設計された」ハッシュ関数です.TreeSet:秩序あるSetで、その下層は木です.これにより、Setから秩序化されたシーケンスを抽出することができます.赤と黒のツリーのデータ構造を要素としてソートします.LinkedHashSet(JDK 1.4):内部でチェーンテーブルを使用するSetで、HashSetのクエリー速度もあれば、また、要素が追加された順序を保存することができます.(挿入順序)LinkedHashSetは内部でハッシュを使用してクエリー速度を向上させる.HashSetは最も速いクエリー速度を提供する.TreeSetは要素秩序を保持する.LinkedHashSetは要素の挿入順序を保持する.MapHashMap:ハッシュコードアルゴリズムを採用し、ハッシュコードアルゴリズム:1:ObjectクラスのhashCodeに関するキー値を迅速に検索する.オブジェクトのメモリアドレスが処理される後の構造は,オブジェクトごとにメモリアドレスが異なるため,ハッシュコードも異なる.2:StringクラスのhashCode.Stringクラスに含まれる文字列の内容に基づいて、特殊なアルゴリズムに基づいてハッシュコードが返され、文字列の内容が同じであれば、返されるハッシュコードも同じである.3:Integerクラス、返されるハッシュコードはIntegerオブジェクトに含まれるその整数の数値TreeMap:ツリーのデータ構造でキー値を並べ替えた
各タイプのデータ構造の内部データ保存方式を理解すると、その操作もわかります.例えば、配列で検索が速く、削除の追加が遅いことを知っています.チェーンテーブルでは削除の追加が速く、配列ほど速くないことを知っています.もちろん、処理数グループとチェーンテーブルのほかに、データ構造---mapがあります.キー値はデータを格納します.まずHashSetのコンストラクタを見てみましょう

public HashSet(int initialCapacity) { 
    map = new HashMap<E,Object>(initialCapacity); } 
public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity); }
 public HashSet(int initialCapacity) {
     map = new HashMap<E,Object>(initialCapacity); } 
public HashSet() { 
      map = new HashMap<E,Object>(); } 
  
  
 らかに、HashSetは  にHashMapの に  されているのではないでしょうか.では、HashMapはどのように  されているのでしょうか.
HashMapはAbstractMapクラスを  し、Map、Cloneable、Serializableインタフェースを  し、HashmMapでは の  を  しています.
  
static final int DEFAULT_INITIAL_CAPACITY = 16;
 static final int MAXIMUM_CAPACITY = 1 << 30; 
static final float DEFAULT_LOAD_FACTOR = 0.75f;
 transient Entry[] table;
 transient int size; 
final float loadFactor; 
transient volatile int modCount; 
  
ここで、デフォルトのサイズは16、    は1<<30、マウントファクタは0.75 fであり、Entry[]は、Keyオブジェクトをhash  で  した に  したインデックスである.
  
  
  
コンストラクタを てみましょう.
 //   1
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        init();
     	
    }
//   2
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    	    }
//   3
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
            }
//   4
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
           }
     
コンストラクタ1を  する  、
while (capacity < initialCapacity) capacity <<= 1;  
 
            Map      ，HashMap   Entry[]             2     ，       ？      HashMap       Entry       
 
 
 
int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); static int indexFor(int h, int length) { return h & (length-1); } 
 
 
 i            ，       Hash      -1     ，    length-1    ，            HashMap   。  length 2     ，  length        ：10000000......（   0），  length-1  1111......（   1），    length-1           ，          ，         。
 
 
 
 
 
 
 
    2      1    ，   3       ，   4         HashMap     HashMap。
 
      HashMap    ，            ，  HashMap      ？       ，HashMap  ：
 
 
public V put(K key, V value) {
 if (key == null) 
return putForNullKey(value);
 int hash = hash(key.hashCode());
 int i = indexFor(hash, table.length); 
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
V oldValue = e.value; 
e.value = value;
 e.recordAccess(this);
 return oldValue; }
 }
 modCount++;
 addEntry(hash, key, value, i);
 return null; 
} 
private V putForNullKey(V value) { 
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); 
return oldValue;
 } 
} modCount++;
 addEntry(0, null, value, 0);
 return null;
 } 

void addEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<K,V>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } 

  
  
HashMapはkeyがnullのときのvalueを  することができ、  putForNullKeyはこれを  しています.キーのインデックスを  した 、 しいEntryオブジェクトを  してキーとvalue を  し、table[i]の  に  します.ハッシュが  している  は、 い を き えて します.しかし、HashMapにデータを  し けると、   に  したサイズを えることになります.この  、どのように  しますか?もちろんrehashです.メソッドaddEntryにこんな  があります
if (size++ >= threshold) resize(2 * table.length);//resizeメソッドは、void resize(int newCapacity){Entry[]oldTable=table;int oldCapacity=oldTable.length;if(oldCapacity==MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int)(newCapacity * loadFactor); }  
 
   ，  threshold = (int)(capacity * loadFactor)                       ，                ，             
 
 
 
 
 
 
 
 
 
 
 
 
                     。
 
            ？  get  
 
 
public V get(Object key) {
 if (key == null) 
return getForNullKey(); 
int hash = hash(key.hashCode());
 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { 
Object k; 
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 
return e.value;
 } 
return null;
 } 

  
keyがnullの  は  で  し、nullの  はhash を  せず、テーブルのhash   にチェーンが けられている  は、このチェーンの に かって している じkeyまで いてvalue を します.
では、HashMapはどのようにデータを  したのでしょうか.
  
  
  
  
  
final Entry<K,V> removeEntryForKey(Object key) {
 int hash = (key == null) ? 0 : hash(key.hashCode());
 int i = indexFor(hash, table.length);
 Entry<K,V> prev = table[i]; 
Entry<K,V> e = prev; 
while (e != null) {
 Entry<K,V> next = e.next;
 Object k; 
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { 
modCount++; 
size--;
 if (prev == e) 
table[i] = next; 
else 
prev.next = next; 
e.recordRemoval(this); 
return e; }
 prev = e; 
e = next; 
} 
return e;
}
  
もちろん、チェーンテーブル のノードを  するのはチェーンテーブルの  ですが、テーブル のデータを  すると、 の りのチェーンをテーブルの いた  に けます. の  cloneやclearなどは  ですが、putやgetの  がポイントです.
システムが  するHashMapについては、 なプロセスとデータ  が  されているが、  な では  されていないことが い.
1,hash()  
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }  
このようなアルゴリズムはなぜハッシュ  を   に らすことができるのか.
2. の のサイズを  することは  を  する  の  ですか?