HashMap

より継承

public class HashMap<K,V> extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable 

メンバー変数

 /**
 * The default initial capacity - MUST be a power of two.
 */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 /**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
 static final int MAXIMUM_CAPACITY = 1 << 30;
 /**
 * The load factor used when none specified in constructor.
 */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 /**
 * The bin count threshold for using a tree rather than list for a
 * bin. Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
 static final int TREEIFY_THRESHOLD = 8;
 /**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
 static final int UNTREEIFY_THRESHOLD = 6;
 /**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
 static final int MIN_TREEIFY_CAPACITY = 64;
 
 
 transient Node<K,V>[] table;
 /**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
 transient Set<Map.Entry<K,V>> entrySet;
 /**
 * The number of key-value mappings contained in this map.
 */
 transient int size;
 /**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash). This field is used to make iterators on Collection-views of
 * the HashMap fail-fast. (See ConcurrentModificationException).
 */
 transient int modCount;
 /**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
 // (The javadoc description is true upon serialization.
 // Additionally, if the table array has not been allocated, this
 // field holds the initial array capacity, or zero signifying
 // DEFAULT_INITIAL_CAPACITY.)
 int threshold;
 /**
 * The load factor for the hash table.
 *
 * @serial
 */
 final float loadFactor;

Q:赤黒木に変換する前のMapのバケット数が8以上なのはなぜですか？

赤黒木の平均探索長はlog(n)、長さが8の場合、平均探索長はlog(8)=3、連鎖表の平均探索長はn/2、長さが8の場合、平均探索長は8/2=4、これは木に変換する必要があります。木構造への変換と木の生成にかかる時間はそれほど短くありません。

コンストラクター

 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);
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
 }
 //入力パラメータより大きく、最も近い2の整数乗の数
static final int tableSizeFor(int cap) {
 int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
 }
 //Integer
 public static int numberOfLeadingZeros(int i) {
 // HD, Count leading 0's
 if (i <= 0)
 return i == 0 ? 32 : 0;
 int n = 31;
 if (i >= 1 << 16) { n -= 16; i >>>= 16; }
 if (i >= 1 << 8) { n -= 8; i >>>= 8; }
 if (i >= 1 << 4) { n -= 4; i >>>= 4; }
 if (i >= 1 << 2) { n -= 2; i >>>= 2; }
 return n - (i >>> 1);
 }
 
 
 
 public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 
 public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }
 
 public HashMap(Map<? extends K, ? extends V> m) {
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 putMapEntries(m, false);
 }
 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
 int s = m.size();
 if (s > 0) {
 if (table == null) { // pre-size
 float ft = ((float)s / loadFactor) + 1.0F;
 int t = ((ft < (float)MAXIMUM_CAPACITY) ?
 (int)ft : MAXIMUM_CAPACITY);
 if (t > threshold)
 threshold = tableSizeFor(t);
 }
 else if (s > threshold)
 resize();
 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
 K key = e.getKey();
 V value = e.getValue();
 putVal(hash(key), key, value, false, evict);
 }
 }
 }

データ操作

HashMapは、摂動関数を介してキーのhashCodeを介してハッシュ値を取得し、＆ハッシュを介して、現在の要素の場所を決定するために、要素の存在の現在の場所であれば、判断要素とハッシュ値に堆積される要素とキーが同じであるかどうか、同じ単語は、直接のカバレッジは、同じではない場合は、競合を解決するためにzipメソッドを介して。いわゆる摂動関数は、HashMapのハッシュメソッドを指します。摂動関数としても知られているハッシュメソッドの使用は、いくつかの不十分な実装hashCode()メソッドを防ぐためです。 言い換えれば、摂動関数の使用は、衝突の数を減らすことができます。

エレメントの追加

public V put(K key, V value) {
 return putVal(hash(key), key, value, false, true);
 }
 //hash値の高さは16ビットである。 + （ハイ16ビット^(下位16ビット）ヌルハッシュ値ビット0
 static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }
 
 **
 * キーの値を計算し、次に添え字を計算する
 * キーが衝突していなければ、そのままバケツに入れ、衝突があれば、連鎖表の形で後ろに追加し、連鎖表の長さが8より大きければ、連鎖表を赤黒木に変換し、赤黒木の長さが6より小さければ、連鎖表に戻す
 * ノードがすでに存在する場合は置き換える
 * バケツいっぱい、スレホールドより大きい、拡大する。
 * @param hash キーから計算されるハッシュ値
 * @param key 収納するキー
 * @param value 保存される値
 * @param onlyIfAbsent 現在の位置にすでに値が存在する場合、それを置き換えるかどうか、falseなら置き換える、trueなら置き換えない
 * @param evict テーブルが作成モードかどうか、falseなら作成モード。
 */
 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node<K,V>[] tab; Node<K,V> p; int n, i;
 //コレクションが空の場合は、Nodeを生成するために展開する必要がある。<K,V> [] table 配列、デフォルトのサイズは16
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 //添え字を計算する 要素pを取得し、pがnull、つまり存在しない場合はキー値を格納する。
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 //この添え字には値があり、衝突が起こる
 else {
 Node<K,V> e; K k;
 //キーの値が元の添え字のバケツの値と同じなら、バケツの値をeとして保存する。
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 //元のバケツの空でないノードpが赤黒木の場合、赤黒木が追加されるのと同じ方法でキー値を追加する
 else if (p instanceof TreeNode)
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 //pを連鎖表とする
 else {
 //チェーンテーブルを順次反復する
 for (int binCount = 0; ; ++binCount) {
 //pの次の要素eが空なら追加し、連鎖表の長さが7以上なら赤黒木に変換してループを終了する。
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 //キーの値がチェーンテーブルのノードの値と同じなら、その値をeとしてバケットに保存し、ループを終了する。
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
 //enot nullはコレクションにキーが存在することを示す 古い値の値を返す
 
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 //linkedHahMap
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
 //サイズがしきい値より大きければ拡大する。
 if (++size > threshold)
 resize();
 afterNodeInsertion(evict);
 return null;
 }

拡張

 final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table;
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 int oldThr = threshold;
 int newCap, newThr = 0;
 
 if (oldCap > 0) {
 	//古い容量が最大容量値より大きい場合、次の拡張キューの値が最大整数値となり、古いバケット配列が返される。
 if (oldCap >= MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return oldTab;
 }
 //新キャパシティは旧キャパシティである*2，最大容量より少なく、古い容量が初期デフォルト容量より大きい場合。 
 //旧クエの新クエ値*2
 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
 oldCap >= DEFAULT_INITIAL_CAPACITY)
 newThr = oldThr << 1; // double threshold
 }
 //旧容量が0の場合 旧キューが0より大きい場合 新容量は旧キューである
 else if (oldThr > 0) // initial capacity was placed in threshold
 newCap = oldThr;
 //古い容量が0の場合 古いキューが0の場合 容量とキューはデフォルトである
 else { // zero initial threshold signifies using defaults
 newCap = DEFAULT_INITIAL_CAPACITY;
 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 //新しいキューは、新しい容量が古いキューである場合に0となり、そうでない場合はすべてnewThrが0となる。
 if (newThr == 0) {
 float ft = (float)newCap * loadFactor;
 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
 (int)ft : Integer.MAX_VALUE);
 }
 threshold = newThr;
 @SuppressWarnings({"rawtypes","unchecked"})
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 if (oldTab != null) {
 	//バケツの配列を順番に繰り返し、古いバケツから新しいバケツに値をコピーする。
 for (int j = 0; j < oldCap; ++j) {
 Node<K,V> e;
 if ((e = oldTab[j]) != null) {
 oldTab[j] = null;
 //バケツの中に矛盾する要素がないことを示し、新しい添え字を計算する
 if (e.next == null)
 newTab[e.hash & (newCap - 1)] = e;
 //赤黒ツリーの場合は、別にコピーする。この方法は、主にテーブルを連結する場合に対処する
 else if (e instanceof TreeNode)
 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
 
 
 //連鎖するテーブルなら、resize()が核心部分だ。
 else { // preserve order
 Node<K,V> loHead = null, loTail = null;
 Node<K,V> hiHead = null, hiTail = null;
 Node<K,V> next;
 do {
 next = e.next;
 //説明.hash & (newCap -1)= j,添え字に変更はない
 //jdk1.7はヘッダー挿入法
 if ((e.hash & oldCap) == 0) {
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 }
 //説明.hash & (newCap -1) = j + oldCap
 //なぜならnewキャップだからだ == oldCap*2
 //旧キャップが8で、"新 "キャップが16だとする。
 //もし.hash xxx1101の場合、e.hash & (odlCap -1) j== xxx0101
 //e.hash & (newCap -1) == xxx1101 == j + oldCap
 else {
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
 if (loTail != null) {
 loTail.next = null;
 newTab[j] = loHead;
 }
 if (hiTail != null) {
 hiTail.next = null;
 newTab[j + oldCap] = hiHead;
 }
 }
 }
 }
 }
 return newTab;
 }

赤と黒のツリーはできたら作ります。