HashMapソースのhash()関数解析(JDK 1.8)

転載は出典を明記してください.http://blog.csdn.net/anxpp/article/details/51234835あ、ありがとう!
    ハッシュされた容器を用いると,その高性能の主な影響因子の一つがhash値であることが分かった.
    HashMapでは、パフォーマンスを向上させるために、キーのオブジェクトとしてバケツに適切に割り当てるための合理的なhash関数を提供することを望んでいます.
    実際のHashMapでは,オブジェクトから取得したhash値を調整した.
    まずソースコードを見てみましょう.

  
  
  
  

   
   
   
   
 static final int hash(Object key) {
   
   
   
   
 int h;
   
   
   
   
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   
   
   
   
 }
  
  
  
  

    詳細な手順を次のように等価に変更できます.

  
  
  
  

   
   
   
   
static final int hash(Object key) {
   
   
   
   
 if(key == null)
   
   
   
   
 return 0;
   
   
   
   
 int h = key.hashCode();
   
   
   
   
 int temp = h >>> 16;
   
   
   
   
 int newHash = h ^ temp;
   
   
   
   
 return newHash;
   
   
   
   
 }
  
  
  
  

    コードプロシージャの直接翻訳は、Key値がnullの場合、0を返します.キー値が空でない場合は、元のhash値と元のhash値が符号なしに16ビット右にシフトした値がビット別または異なる結果を返します.
    ビット別または2つの数をバイナリで押すと、同じように0を取り、異なる場合は1を取ることを知っています.
    たとえば、0101^1110の結果は1011です.(以前デジタル回路の授業で習ったのを覚えています)異種のスピードはとても速いです.
    1つの数を16ビット右にシフトすると、16が低くなり、216未満の数となり、16を右にシフトすると結果は0になります(2の16回の方が右にシフトするとちょうど1になります).
    いずれの数も、0とビットを異にした結果はこの数自体である(よく検証されている).
    したがって、このhash()関数はnull以外のhash値に対して、216以上の場合にのみ値を再調整する.
    しかし、調整後のメリットは何ですか?
    まずputを見てみましょう.このhash値はどのように処理されていますか.

  
  
  
  

   
   
   
   
 public V put(K key, V value) {
   
   
   
   
 return putVal(hash(key), key, value, false, true);
   
   
   
   
 }
   
   
   
   
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   
   
   
   
 Node<K,V>[] tab; Node<K,V> p; int n, i;
   
   
   
   
 if ((tab = table) == null || (n = tab.length) == 0)
   
   
   
   
 n = (tab = resize()).length;
   
   
   
   
 if ((p = tab[i = (n - 1) & hash]) == null)
   
   
   
   
 tab[i] = newNode(hash, key, value, null);
   
   
   
   
 ......
   
   
   
   
 }
  
  
  
  

    バケツの位置を探すとき、このhash値は上tableとのzise-1で、初期は16で、私たちは16を例に挙げます.
    アルゴリズムはhashValue&size-1だと思っていますが、size-1=15のバイナリは1 1 1 1、つまり任意の16進0 xに似ていますか?0(バイナリの最後の4桁は0000)のhash値は、いずれも位置が0のバケツに格納され、1つのバケツの要素が多すぎると、必ず性能が低下しますが、このようなhash値が上記の関数で処理された結果を見てみましょう.

  
  
  
  

   
   
   
   
public class TestHashCodeMethod {
   
   
   
   
 public static void main(String args[]) throws Exception{
   
   
   
   
 final int max = Integer.MAX_VALUE >>> 4;
   
   
   
   
 Random random = new Random(System.currentTimeMillis());
   
   
   
   
 for(int i=0;i<20;i++){
   
   
   
   
 int hash = random.nextInt(max) << 4;
   
   
   
   
 int betterHash = hash ^ (hash >>> 16);
   
   
   
   
 System.out.print(toBinaryString(hash));
   
   
   
   
 System.out.println("-->" + toBinaryString(betterHash));
   
   
   
   
 }
   
   
   
   
 }
   
   
   
   
 //            ，   0
   
   
   
   
 final static char[] digits = {'0','1'};
   
   
   
   
 static String toBinaryString(int i) {
   
   
   
   
 char[] buf = new char[32];
   
   
   
   
 int pos = 32;
   
   
   
   
 int mask = 1;
   
   
   
   
 do {
   
   
   
   
 buf[--pos] = digits[i & mask];
   
   
   
   
 i >>>= 1;
   
   
   
   
 } while (pos > 0);
   
   
   
   
 return new String(buf, pos, 32);
   
   
   
   
 }
   
   
   
   
}
  
  
  
  

    結果hash関数の変換後の値を表示します.

  
  
  
  

   
   
   
   
00011000000100011111000101100000-->00011000000100011110100101110001
   
   
   
   
00110111100110001011010000100000-->00110111100110001000001110111000
   
   
   
   
01101110000011101111100011010000-->01101110000011101001011011011110
   
   
   
   
00000000000111110010101100010000-->00000000000111110010101100001111
   
   
   
   
00110101101001101000010010010000-->00110101101001101011000100110110
   
   
   
   
00101111111111001011000101010000-->00101111111111001001111010101100
   
   
   
   
01100101111101101110100110110000-->01100101111101101000110001000110
   
   
   
   
00000011101101101110000110100000-->00000011101101101110001000010110
   
   
   
   
00100011001101010011110010110000-->00100011001101010001111110000101
   
   
   
   
01101101111010000001111011110000-->01101101111010000111001100011000
   
   
   
   
01111001111100110101000101010000-->01111001111100110010100010100011
   
   
   
   
00111110101001111101100110100000-->00111110101001111110011100000111
   
   
   
   
01011001000001101010011001110000-->01011001000001101111111101110110
   
   
   
   
01101000101100101110101100100000-->01101000101100101000001110010010
   
   
   
   
01100110111011001111110001000000-->01100110111011001001101010101100
   
   
   
   
00100001100011000010110001100000-->00100001100011000000110111101100
   
   
   
   
01100010001010000110101111110000-->01100010001010000000100111011000
   
   
   
   
00000011001111101111111110110000-->00000011001111101111110010001110
   
   
   
   
00111110100100101011111110110000-->00111110100100101000000100100010
   
   
   
   
01000100000101011111111110000000-->01000100000101011011101110010101
  
  
  
  

    状況が好転したことに気づいたのか、もともと「0」バケツに置かれていたhash値の多くが、今ではほとんど他のバケツに合理的に割り当てられている.
    hashMapのバケツビットはoldCap<<1(すなわち原容量*2)で増加することが知られているので、最終的にこのhash値を格納するときは、一連のバイナリの「1」と演算され、容量はintタイプと定義され、javaのintタイプは4バイト、すなわち32ビットであるが、Integer.MAXは0 x 7 fffffffffff、すなわち231である - 1ほど大きい(最上位ビットがシンボルビットとして用いられるため)、16をとるのはトレードオフの方法であるが、もう一つの理由は、オブジェクト自体のhash値(もちろんint)に関係しているのかもしれない.
    では、この方法はこれだけ紹介されています.近いうちにHashMap全体のソースコードを解読し、共有し、最終的にはJavaのコンテナシステムを全体的に紹介するつもりです.
    前に2つのコンテナのソースコードの解読を送ったことがあります.ここではリンクを示します.
    JavaのLinkedListソースコード解読(JDK 1.8)
    JavaのArrayListソースコード解読(JDK 1.8)