HashMap原始碼來自：android-25/java/util/HashMap
一、構造方法
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 引數默認為 4,0.75f
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 4 < MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
// 4 = DEFAULT_INITIAL_CAPACITY
else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
threshold = initialCapacity;
init();
}
ps：
init()為空方法；構造方法中只是做了HashMap陣列容量欄位的一個簡單限制，最大為MAXIMUM_CAPACITY，最小為DEFAULT_INITIAL_CAPACITY
二、添加元素 put(K key, V value)
添加資料時，若出現沖突，
Java是通過 陣列+鏈表 的形式解決沖突，效果如下圖所示：
- HashMap中有一個默認長度為16的table陣列，當陣列的容量達到默認長度的0.75倍時，則擴容兩倍；
- 其中table陣列的每一項資料結構如下：
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key; // key
V value; // value
HashMapEntry<K,V> next; // 鏈表的下一項
int hash; // key 的hash值
}
下面通過跟中原始碼查看：
table陣列初始化
介紹put(K key, V value)方法前，先簡單介紹table陣列初始化
// 添加key value
public V put(K key, V value) {
// 如果table串列為null，則用過inflateTable方法初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
...
return null;
}
// 初始化table陣列
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 這里計算一個2的n次方的陣列容量，默認為2的4次方，為16
int capacity = roundUpToPowerOf2(toSize);
// 計算陣列容量的0.75倍，超過陣列容量0.75倍時，陣列需要擴容
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
// 陣列容量的0.75倍
threshold = (int) thresholdFloat;
// 初始化陣列,默認容量capacity為16
table = new HashMapEntry[capacity];
}
ps：
這里默認初始化了一個陣列容量為16的table陣列，其中關于roundUpToPowerOf2(toSize)為什么為2的n次方的問題，在下邊進行介紹
put(K key, V value)
// 添加key value
public V put(K key, V value) {
// 如果table串列為null，則用過inflateTable方法初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// key 為null，則添加key為null的value
if (key == null)
return putForNullKey(value);
// 根據key獲取hash值
// Jenkins hash演算法，可參考以下鏈接：
// https://en.wikipedia.org/wiki/Jenkins_hash_function
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// h & (length-1) 取余太消耗性能，這里通過位運算達到同樣的效果
// 獲取該key在table 陣列的index
int i = indexFor(hash, table.length);
// 回圈table[i]對應的鏈表
// 如果 hash值相同 && key相同，則替換對應value，并回傳老的value值
// 注：這里只是回圈table[i]位置的鏈表，對于table陣列未做回圈
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果 hash值相同 && key相同，則替換對應value，并回傳老的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = https://www.cnblogs.com/xiaxveliang/p/e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 以下兩種情況，則需要通過createEntry方法來看了
// hash相同 && key不同
// hash不同 && key不同
addEntry(hash, key, value, i);
return null;
}
ps：
以上介紹了添加資料時，“如果 hash值相同 && key相同，則替換對應value，并回傳老的value值”，但對于“hash相同 && key不同”與“hash不同 && key不同”情況，則需要在createEntry中進行說明
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當陣列的占用量，達到陣列長度的0.75倍時，則需要擴容，擴展后的容量為原容量的2倍
// 陣列擴容首先創建一個長度為原陣列兩倍的陣列，然后將老的陣列資料賦值給新陣列的對應項專案
// 陣列擴容的代碼，這里不再說明
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// hash相同 && key不同
// hash不同 && key不同
createEntry(hash, key, value, bucketIndex);
}
// hash相同 && key不同
// hash不同 && key不同
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出table[bucketIndex]陣列的原有值，可能為null，可能為HashMapEntry
// 若為null,則直接將value放在table[bucketIndex]位置就ok了
// 若不為null,則將新陣列放到table[bucketIndex]位置，老陣列放到新資料鏈表的next欄位
// hash沖突就是這樣解決了，可以看到確實與上圖一致，為陣列+鏈表的方式解決沖突
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
ps：
通過createEntry方法，我們看到HashMap中通過陣列+鏈表方式解決了Hash沖突，呼應了上圖
roundUpToPowerOf2(toSize)為什么為2的n次方
打個比方：
- 當陣列長度為15時，添加陣列時
h & (length-1)計算成為hash&14（0x1110）,那么最后一位永遠是0，從而造成table陣列中 1（0x0001），3（0x0011），5（0x0101），7（0x0111），9（0x1001），11（0x1011）等位置永遠不可以存放資料，從而造成空間浪費； - 更糟的是這種情況中，陣列可以使用的位置比陣列長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率，
ps：
關于 roundUpToPowerOf2(toSize)為什么為2的n次方問題，詳細可查看
http://blog.csdn.net/yyh352091626/article/details/60866689?locationNum=4&fps=1
========== THE END ==========
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/28328.html
標籤：Android
下一篇：Only fullscreen opaque activities can request orientation 原因及解決方案