HashMap 的性能因數 1. 容量：表示桶位的數量。 2. 初始容量: 表在創建是所擁有的桶位數。 如果你知道將要在HashMap存儲多少項，創建一個初始容量合適的HashMap將可以避免自動再散列的開銷 /** * The default initial capacity - MUST be ... ...
HashMap 的性能因數
1. 容量：表示桶位的數量。
2. 初始容量: 表在創建是所擁有的桶位數。
- 如果你知道將要在HashMap存儲多少項，創建一個初始容量合適的HashMap將可以避免自動再散列的開銷
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //預設大小
3. 尺寸： 表中當前存儲的項數。
4. 負載因數：尺寸/容量。 負載因數小的表衝突的可能性小，插入和查找的速度也相對較快（但會減慢使用迭代器進行遍歷的過程）。HashMap和HashSet都具有允許你指定負載因數的構造器，表示當負載情況達到負載因數的水平時，容器將自動增加容量。實現方法是使容量加倍，並將現有對象分配到新的桶位集中。
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap構造器
HashMap(int initialCapacity, float loadFactor), initialCapacity為初始容量， loadFactor為負載因數
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // 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); // tableSizeFor(initialCapacity) 會返回x（x表示2的整數次冪）
//threshold是一個闕值，它等於 負載因數*尺寸， 當然這裡暫時等於容量
//當調用resize函數後才開始真正分配空間（槽位），這時才賦給threshold真正意義上的值
}
來看看tableSizeFor的實現(個人絕對想不到這麼高大上的方法)
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1; //這裡是因為考慮到cap為2的整數次冪的情況
//1. 假設此時n的二進位最高位1在第i位（最低位為第0位）
n |= n >>> 1;
//2. 此時n的二進位第i, i-1位都為1
n |= n >>> 2;
//3. 此時n的二進位第i, i-1, i-2, i-3位都為1
n |= n >>> 4;
//4. 此時n的二進位第i, i-1, i-2, i-3, i-4, i-5, i-6, i-7位都為1(當然，嚴謹點應該再假設i>7)
n |= n >>> 8;
//5.---------
n |= n >>> 16;
//6.---------
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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); // 沒反生衝突，直接放入第i個槽位
else {
//執行到這裡，表示發生衝突了
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //如果key相等，直接把新value覆蓋原value
else if (p instanceof TreeNode) //判斷當前解決衝突所用的數據結構是不是TreeNode（紅黑樹）
//這是當衝突過多（某個槽位衝突數超過TREEIFY_THRESHOLD=8）時，
//HashMap的優化方式
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 執行到這裡說明當前解決衝突所用結構是鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 衝突數超過TREEIFY_THRESHOLD
// 用紅黑樹代替鏈表
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { //如果map存在與新key相等的key，直接把新value覆蓋原value
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) //判斷當前尺寸是否大於闕值（即負載是否大於負載因數）
resize();
afterNodeInsertion(evict);
return null;
}
博客園(FOREVER_ENJOY)：http://www.cnblogs.com/zyx1314/p/5359434.html
本文版權歸作者所有；歡迎轉載！請註明文章作者和原文連接
